Zero-Sum Fictitious Play Cannot Converge to a Point
This addresses a long-standing open challenge in game theory, revealing fundamental instability in FP dynamics for zero-sum games, which is incremental as it builds on known convergence results.
The paper tackles the problem of whether fictitious play (FP) converges to a single Nash equilibrium point in zero-sum games, proving that it does not necessarily stabilize at a point, even with tie-breaking rules, by identifying conditions that preclude such convergence.
Fictitious play (FP) is a history-based strategy to choose actions in normal-form games, where players best-respond to the empirical frequency of their opponents' past actions. While it is well-established that FP converges to the set of Nash equilibria (NE) in zero-sum games, the question of whether it converges to a single equilibrium point, especially when multiple equilibria exist, has remained an open challenge. In this paper, we establish that FP does not necessarily stabilize at a single equilibrium. Specifically, we identify a class of zero-sum games where pointwise convergence fails, regardless of the tie-breaking rules employed. We prove that two geometric conditions on the NE set (A1 and A2) and a technical assumption (A3) are sufficient to preclude pointwise convergence. Furthermore, we conjecture that the first two conditions alone may be sufficient to guarantee this non-convergence, suggesting a broader fundamental instability in FP dynamics.