On the Convergence of Fictitious Play: A Decomposition Approach

• URL: http://arxiv.org/abs/2205.01469v1
• Date: Tue, 3 May 2022 13:04:09 GMT
• Title: On the Convergence of Fictitious Play: A Decomposition Approach
• Authors: Yurong Chen, Xiaotie Deng, Chenchen Li, David Mguni, Jun Wang, Xiang Yan, Yaodong Yang
• Abstract summary: We extend the convergence results of Fictitious Play (FP) to the combinations of such games and beyond. We develop a linear relationship unifying cooperation and competition in the sense that these two classes of games are mutually transferable. We analyze a non-convergent example of FP, the Shapley game, and develop sufficient conditions for FP to converge.
• Score: 17.607284715519587
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fictitious play (FP) is one of the most fundamental game-theoretical learning frameworks for computing Nash equilibrium in $n$-player games, which builds the foundation for modern multi-agent learning algorithms. Although FP has provable convergence guarantees on zero-sum games and potential games, many real-world problems are often a mixture of both and the convergence property of FP has not been fully studied yet. In this paper, we extend the convergence results of FP to the combinations of such games and beyond. Specifically, we derive new conditions for FP to converge by leveraging game decomposition techniques. We further develop a linear relationship unifying cooperation and competition in the sense that these two classes of games are mutually transferable. Finally, we analyze a non-convergent example of FP, the Shapley game, and develop sufficient conditions for FP to converge.

Related papers

• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  We introduce NeuPL-JPSRO, a neural population learning algorithm that benefits from transfer learning of skills and converges to a Coarse Correlated (CCE) of the game. Our work shows that equilibrium convergent population learning can be implemented at scale and in generality.
  arXiv  Detail & Related papers  (2024-01-10T12:56:24Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller. Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
  arXiv  Detail & Related papers  (2023-12-19T11:34:10Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  Two-team zero-sum games are defined as multi-player games where players are split into two competing sets of agents. We focus on the solution concept of Nash equilibria (NE) We show that computing NE for this class of games is $textithard$ for the complexity class $mathrm$.
  arXiv  Detail & Related papers  (2021-11-07T21:15:35Z)
• Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality [21.94743452608215]
  We study smooth Q-learning, a prototypical learning model that captures the balance between game rewards and exploration costs. We show that Q-learning always converges to the unique quantal-response equilibrium (QRE), the standard solution concept for games under bounded rationality.
  arXiv  Detail & Related papers  (2021-06-24T11:43:38Z)
• Operator Splitting for Learning to Predict Equilibria in Convex Games [26.92001486095397]
  We introduce Nash Fixed Point Networks (N-FPNs), a class of neural networks that naturally output equilibria. N-FPNs are compatible with the recently developed Jacobian-Free Backpropagation technique for training implicit networks. Our experiments show N-FPNs are capable of scaling to problems orders of magnitude larger than existing learned game solvers.
  arXiv  Detail & Related papers  (2021-06-02T02:55:46Z)
• Scaling up Mean Field Games with Online Mirror Descent [55.36153467919289]
  We address scaling up equilibrium computation in Mean Field Games (MFGs) using Online Mirror Descent (OMD) We show that continuous-time OMD provably converges to a Nash equilibrium under a natural and well-motivated set of monotonicity assumptions. A thorough experimental investigation on various single and multi-population MFGs shows that OMD outperforms traditional algorithms such as Fictitious Play (FP)
  arXiv  Detail & Related papers  (2021-02-28T21:28:36Z)
• Convergence of Deep Fictitious Play for Stochastic Differential Games [6.875312133832078]
  Recently proposed machine learning algorithm, deep fictitious play, provides a novel efficient tool for finding Markovian Nash equilibrium of large $N$ asymmetric differential games. By incorporating the idea of fictitious play, the algorithm decouples the game into $N$ sub-optimization problems. We show that the strategy based on DFP forms an $eps$-Nash equilibrium.
  arXiv  Detail & Related papers  (2020-08-12T18:27:13Z)
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
  We characterize the finite-time last-iterate convergence rate for joint OGD learning on $lambda$-cocoercive games. We show, via a novel double-stopping time technique, that this adaptive algorithm achieves same finite-time last-iterate convergence rate as non-adaptive counterpart.
  arXiv  Detail & Related papers  (2020-02-23T01:46:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.