Fictitious Play with Maximin Initialization

Nash equilibrium is the central solution concept in game theory. While a Nash equilibrium can be computed in polynomial time for two-player zero-sum games, it is PPAD-hard for two-player general-sum and multiplayer games and widely believed that no efficient algorithms exist [6, 7, 8]. The best algorithm for computing an exact Nash equilibrium in multiplayer games is based on a non-convex quadratic program formulation and only scales to relatively small games [10]. For larger games several iterative algorithms have been considered; however, they have no theoretical guarantees and may have an extremely high degree of error. It has recently been shown that fictitious play produces a smaller degree of equilibrium approximation error in these games than regret minimization [11], though the average error still becomes relatively large as the game size increases. For example, for 3-player games with 10 strategies per player and all payoffs uniform random in [0,1], the average equilibrium error from fictitious play is 0.056. The classic version of fictitious play initializes strategies for all players to play all actions with equal probability. In this paper we will explore more sophisticated initialization approaches to improve the algorithm's performance. A strategic-form game consists of a finite set of players N = {1,..., n}, a finite set of pure strategies S