Monte Carlo Fictitious Play for Finding Pure Nash Equilibria in Identical Interest Games

Computing equilibria in large-scale games is an important topic in many areas. One approach is to define a dynamic procedure such as fictitious play (FP) that converges to a mixed Nash equilibrium (NE) in identical interest games (among other classes) but suffers from exponential iteration complexity. Recent variants of FP reduce the computational burden, but many still do not guarantee convergence to a pure NE. We analyze a procedure—Monte Carlo fictitious play (MCFP)—that overcomes these limitations and efficiently discovers a pure NE in finite time with probability one in identical interest games. We also show a variant of MCFP finds a pure NE with optimal utility with probability one. Numerical results demonstrate the comparative performance of several variants of MCFP.

Funding: This research was supported by the DARPA ARCOS program under contract #FA8750-20-C-0507 and under AFRL contract #FA8750-22-9-0001 and by NSF#2046588.