The Expected Number of Nash Equilibria of a Normal Form Game
Econometrica · 2005 · Volume 73 · Issue 1
DOI: 10.1111/j.1468-0262.2005.00567.x
Abstract
Fix finite pure strategy setsS1,…,Sn, and letS=S1×⋯×Sn. In our model of a random game the agents' payoffs are statistically independent, with each agent's payoff uniformly distributed on the unit sphere in ℝS. For given nonemptyT1⊂S1,…,Tn⊂Snwe give a computationally implementable formula for the mean number of Nash equilibria in which each agenti's mixed strategy has supportTi. The formula is the product of two expressions. The first is the expected number of totally mixed equilibria for the truncated game obtained by eliminating pure strategies outside the setsTi. The second may be construed as the “probability” that such an equilibrium remains an equilibrium when the strategies in the setsSi∖Tibecome available.
Keywords
Nash equilibrium, number of equilibria, computational complexity, random games, algebraic geometry, rotational invariance
Enable JavaScript for citation tools and additional paper interactions.