Fictitious Play with Maximin Initialization
Fictitious play has recently emerged as the most accurate scalable algorithm for approximating Nash equilibrium strategies in multiplayer games. We show that the degree of equilibrium approximation error of fictitious play can be significantly reduced by carefully selecting the initial strategies. We present several new procedures for strategy initialization and compare them to the classic approach, which initializes all pure strategies to have equal probability. The best-performing approach, called maximin, solves a nonconvex quadratic program to compute initial strategies and results in a nearly 75% reduction in approximation error compared to the classic approach when 5 initializations are used.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play
This paper investigates the sublinear regret guarantees of two non-no-regret algorithms in zero-sum games: Fictitious Play, and Online Gradient Descent with constant stepsizes. In general adversarial online learning sett…
Empirical Analysis of Fictitious Play for Nash Equilibrium Computation in Multiplayer Games
While fictitious play is guaranteed to converge to Nash equilibrium in certain game classes, such as two-player zero-sum games, it is not guaranteed to converge in non-zero-sum and multiplayer games. We show that fictiti…
counterfactualSampled Fictitious Play is Hannan Consistent
Fictitious play is a simple and widely studied adaptive heuristic for playing repeated games. It is well known that fictitious play fails to be Hannan consistent. Several variants of fictitious play including regret matc…
Deep Fictitious Play for Stochastic Differential Games
In this paper, we apply the idea of fictitious play to design deep neural networks (DNNs), and develop deep learning theory and algorithms for computing the Nash equilibrium of asymmetric $N$-player non-zero-sum stochast…
Deep LearningGPULearning TheoryA Generalized Extensive-Form Fictitious Play Algorithm
We introduce a simple extensive-form algorithm for finding equilibria of two-player, zero-sum games. The algorithm is realization equivalent to a generalized form of Fictitious Play. We compare its performance to that of…
Form