Zero-Sum Fictitious Play Cannot Converge to a Point

A new paper by researcher Jaehong Moon, published on arXiv, provides a definitive answer to a long-standing open problem in algorithmic game theory. The work, titled 'Zero-Sum Fictitious Play Cannot Converge to a Point,' proves that the classic Fictitious Play (FP) algorithm—a simple model where players best-respond to the historical frequency of their opponent's actions—cannot be guaranteed to converge to a single, stable Nash equilibrium point in zero-sum games. This is significant because while FP was known to converge *toward* the *set* of equilibria, the question of whether it would settle on a specific point within that set had remained unresolved for decades.

Moon's proof establishes that in a specific class of zero-sum games, FP's trajectory will fail to stabilize at any one equilibrium, regardless of how ties in best responses are broken. The paper identifies two geometric conditions on the Nash equilibrium set (labeled A1 and A2) that are sufficient to guarantee this non-convergence, with a conjecture that A1 and A2 alone might be the core requirement. This finding reveals an inherent oscillatory or cyclic behavior in FP's learning process, challenging simpler intuitions about how iterative learning algorithms settle in competitive environments.

The implications extend beyond pure theory. Fictitious Play and its variants are foundational concepts used to model learning and adaptation in multi-agent systems, including some AI training paradigms and economic models. This proof of non-convergence underscores the complexity of stability in even simple learning dynamics and may influence the design and analysis of algorithms for competitive multi-agent AI, where predictable convergence is often desirable.