529. A Novel Class of Games with the Continuous-Time Fictitious Play Property via Geometrical Approach
Invited abstract in session MA-53: Algorithmic Game Theory and Its Applications, stream Game Theory and Mathematical Economics.
Monday, 8:30-10:00Room: Liberty Moot Court
Authors (first author is the speaker)
| 1. | Zhouming Wu
|
| Academy of Mathematics and Systems Science, Chinese Academy of Sciences | |
| 2. | YIFEN MU
|
| Academy of Mathematics and Systems Science, Chinese Academy of Sciences | |
| 3. | Xiaoguang Yang
|
| Institute of Systems Science, Academy of Mathematics and Systems Science, Chinese Academy of Sciences |
Abstract
Fictitious play (FP) is the earliest and most fundamental learning dynamics for computing Nash Equilibrium (NE) and it has been receiving significant research attention over the years. A central question in this field is identifying games in which FP converges, often referred to as games with Fictitious Play Property (FPP). In this work, we introduce a novel class of games with FPP: 3 by 3 games without Internal Indifferent Points (IIP). Our approach is based on a geometric analysis that leverages the locations of NEs and the partitioning of best-response regions within the strategy simplex of the player, while the indifferent point is a novel geometric object of a game at which the actions of each player will yield the same “payoff”. Specifically, we consider the continuous counterpart of FP, and develop a new projection mapping that reduces a high-dimensional dynamical system to a planar system. To address the non-smoothness inherent in the dynamical system, we propose a redefinition of the concepts of saddle NEs and sink NEs. These specific NEs are shown to exist and partition the projected space into two distinct regions thus can help us prove the convergence of dynamics. Additionally, we demonstrate that our projection technique can be generalized to higher-dimensional and degenerate games. By constructing a 3×3 game without IIP which is not quasi-supermodular, we show that this game class is indeed novel and different from the identified class in the literature.
Keywords
- Game Theory
- Machine Learning
- Dynamical Systems
Status: accepted
Back to the list of papers