Nash Equilibrium Solving for General Non-Zero-Sum Games from Non-Convergent Dynamics of Fictitious Play

Solving Nash equilibrium (NE) is a fundamental problem in game theory. However, for general non-zero-sum games, computing NE remains challenging (in fact, it is PPAD-hard), and there are no known efficient algorithms so far. Apart from classical combinatorial methods, learning-based approaches offer an alternative for approximating NE. However, for general non-zero-sum games, the dynamics of learning algorithms turns out to be intricate, and often fail to converge. In this paper, we give a novel method to solve NE from the trajectory of fictitious play (FP), a classical learning algorithm in repeated games. By leveraging the equalization principle of NE, we demonstrate that hidden NE can be unveiled via the trajectory data. Specifically, we focus on two scenarios. For the 3 × 3 game with interior equilibrium when FP exhibits non-convergent behavior, such as cyclic or erratic trajectories, we can obtain an approximate NE by estimating the indifferent lines and solving their intersection points. For the games without an interior equilibrium, by identifying the intersection points between the indifferent lines and the edges of the players’ strategy simplexes, and proposing a label-matching principle, we can still find the approximate NE Hence via this method, we can solve all 3 × 3 games from finite trajectory date of FP no matter how complicated the dynamics is. Further experiments show that the method can be extended to more general normal form games and special kind of stochastic games. This paper reveals that there is more information hidden in the behavior of learning dynamics, and thus indicating a promising way to utilize trajectory data.