From First-Order to Second-Order Rationality: Advancing Game Convergence with Dynamic Weighted Fictitious Play

2024/02/19 by Qi Ju, Ju, Qi, Falin Hei +6
Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2402.12164

openalex publication_date 2024/02/19 · openalex created_date 2024/02/21 · openalex updated_date 2026/07/28

Abstract

Constructing effective algorithms to converge to Nash Equilibrium (NE) is an important problem in algorithmic game theory. Prior research generally posits that the upper bound on the convergence rate for games is O(T^-1/2). This paper introduces a novel perspective, positing that the key to accelerating convergence in game theory is rationality. Based on this concept, we propose a Dynamic Weighted Fictitious Play (DW-FP) algorithm. We demonstrate that this algorithm can converge to a NE and exhibits a convergence rate of O(T^-1) in experimental evaluations.

Related

• Convergence Analysis and Acceleration of Fictitious Play for General Mean-Field Games via the Best Response
• Exponential Lower Bounds for Fictitious Play in Potential Games
• On the Convergence of Fictitious Play: A Decomposition Approach
• On the Exponential Rate of Convergence of Fictitious Play in Potential Games
• From Weak Learning to Strong Learning in Fictitious Play Type Algorithms