Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.07989 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918089758605312 |
|---|---|
| author | Yu, Jiajia Cheng, Xiuyuan Liu, Jian-Guo Zhao, Hongkai |
| author_facet | Yu, Jiajia Cheng, Xiuyuan Liu, Jian-Guo Zhao, Hongkai |
| contents | A mean-field game (MFG) seeks the Nash Equilibrium of a game involving a continuum of players, where the Nash Equilibrium corresponds to a fixed point of the best-response mapping. However, simple fixed-point iterations do not always guarantee convergence. Fictitious play is an iterative algorithm that leverages a best-response mapping combined with a weighted average. Through a thorough study of the best-response mapping, this paper develops a simple and unified convergence analysis, providing the first explicit convergence rate for the fictitious play algorithm in MFGs of general types, especially non-potential MFGs. We demonstrate that the convergence and rate can be controlled through the weighting parameter in the algorithm, with linear convergence achievable under a general assumption. Building on this analysis, we propose two strategies to accelerate fictitious play. The first uses a backtracking line search to optimize the weighting parameter, while the second employs a hierarchical grid strategy to enhance stability and computational efficiency. We demonstrate the effectiveness of these acceleration techniques and validate our convergence rate analysis with various numerical examples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_07989 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Convergence Analysis and Acceleration of Fictitious Play for General Mean-Field Games via the Best Response Yu, Jiajia Cheng, Xiuyuan Liu, Jian-Guo Zhao, Hongkai Optimization and Control A mean-field game (MFG) seeks the Nash Equilibrium of a game involving a continuum of players, where the Nash Equilibrium corresponds to a fixed point of the best-response mapping. However, simple fixed-point iterations do not always guarantee convergence. Fictitious play is an iterative algorithm that leverages a best-response mapping combined with a weighted average. Through a thorough study of the best-response mapping, this paper develops a simple and unified convergence analysis, providing the first explicit convergence rate for the fictitious play algorithm in MFGs of general types, especially non-potential MFGs. We demonstrate that the convergence and rate can be controlled through the weighting parameter in the algorithm, with linear convergence achievable under a general assumption. Building on this analysis, we propose two strategies to accelerate fictitious play. The first uses a backtracking line search to optimize the weighting parameter, while the second employs a hierarchical grid strategy to enhance stability and computational efficiency. We demonstrate the effectiveness of these acceleration techniques and validate our convergence rate analysis with various numerical examples. |
| title | Convergence Analysis and Acceleration of Fictitious Play for General Mean-Field Games via the Best Response |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2411.07989 |