On the Convergence of Fictitious Play: A Decomposition Approach
Authors: Yurong Chen, Xiaotie Deng, Chenchen Li, David Mguni, Jun Wang, Xiang Yan, Yaodong Yang
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | By first conducting experiments on mixtures of normalized harmonic games and normalized potential games, we find out that if they are components of a zero-sum game, then FP converges on any linear combination of them. The changes of NE which FP converges to with λ changing from 0 to 1 is shown in Figure 2. In Figure 2a, the strategy trajectories are presented in the mixed strategy simplex: each vertex of the triangle is an action vi. We draw mixed strategy p = (p1, p2, p3) 3 on the convex combination of the vertices, P3 i=1 pivi. The green dots represent the strategy trajectory of player 1, and the blue dots that of player 2. The star sign denotes the strategies when λ = 1. We set the step length to be 0.001. For each λ, we run FP starting from (v1, v1) for 500,000 rounds. The strategy trajectories of both players start at the center of a strategy simplex, i.e. the uniform equilibrium of harmonic games [Candogan et al., 2011]. As λ increases, the strategies move towards the boundaries, and their supports become small. When λ is large enough, they reach a pure NE (nodes with stars), which is typical of potential games, and no longer moves. Figure 2b shows the changes of player 1 s strategies in line chart. We utilize the algorithm by Heyman [2019] to decide when will G(λ) S(Z). When λ < 5 6, The competitive part takes over, G(λ) S(Z). When λ > 5 6, G(λ) S(I). When λ = 5 6, G(λ) S(Z) S(I) but belongs to D instead. We draw the point λ = 5 6 on Figure 2b. One can find out that when λ is less than but close to 5 6, the equilibrium for FP to converge to already becomes pure and never moves even when λ exceeds 5 6. When λs in the above examples reach the threshold, the games enter D instead of S(Z) S(I). We argue that games in D show the same dynamic patterns with games in S(Z) S(I). |
| Researcher Affiliation | Collaboration | 1Center on Frontiers of Computing Studies, School of Computer Science, Peking University 2Business Growth BU, JD.com 3Huawei R&D 4UCL 5Huawei TCS Lab 6Institute for AI, Peking University |
| Pseudocode | No | The paper does not contain any explicit pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the described methodology. |
| Open Datasets | No | The paper does not use standard public datasets with access information for training or evaluation. It conducts theoretical analysis and simulations based on game theory concepts like the Shapley game. |
| Dataset Splits | No | The paper does not provide specific dataset split information (e.g., percentages, counts) for training, validation, or testing. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., CPU, GPU models, memory, cloud instances) used for running its analyses or simulations. |
| Software Dependencies | No | The paper does not provide specific software dependencies or versions (e.g., programming languages, libraries, solvers with version numbers) used for its analysis or simulations. |
| Experiment Setup | Yes | For each λ, we run FP starting from (v1, v1) for 500,000 rounds. The strategy trajectories of both players start at the center of a strategy simplex, i.e. the uniform equilibrium of harmonic games [Candogan et al., 2011]. As λ increases, the strategies move towards the boundaries, and their supports become small. When λ is large enough, they reach a pure NE (nodes with stars), which is typical of potential games, and no longer moves. Figure 2b shows the changes of player 1 s strategies in line chart. We utilize the algorithm by Heyman [2019] to decide when will G(λ) S(Z). ... We set the step length to be 0.001. |