# Simulating Mixed Nash Equilibria

I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists.

Can someone please tell me how do I find one of those equilibrium points by numerical simulation?

I can not find in the book any explanation of how to simulate. I just need the basic direction.

I have asked this question in math.stackexchange as well. But I posted here too as I noticed users here are not noticed of questions there. Pardon me if this is wrong practice.

Thank you.

-
@StevenLandsburg Thank you. but I think it is not a linear system. It is linear only for two player games. From three player up it is non-linear for the best of my knowledge. Correlated equilibria will be a linear system for any number of players but not NE. (See slide 17 of cs.ubc.ca/~kevinlb/teaching/cs532a%20-%202006-7/lectures/… ) –  MLT Aug 19 '13 at 12:38
MLT: Apologies. I misread your post as saying there were two players. I'll leave this up long enough to make sure you see it, then delete the comment. –  Steven Landsburg Aug 19 '13 at 12:42
What does "numerical simulation" mean? –  usul Aug 19 '13 at 20:38
@usul It means to find numerically, not analytically. Thanks –  MLT Aug 20 '13 at 1:54

First, an exact equilibrium may not be computable in general, so usually the idea is to specify an error parameter $\epsilon$ and look for an $\epsilon$-equilibrium.

Finding an $\epsilon$-Nash equilibrium is considered a hard problem (it is complete for the complexity class $\mathsf{PPAD}$). So there are no known "fast" algorithms.

One algorithm is called support enumeration and covered in this math.se post. You list all possible supports for the players' mixed strategies. Given a set of supports, one can use linear programming to check whether there is a mixed NE with these supports.

Another method (that I believe is still relatively state of the art (?)) is given by Lipton, Markakis, and Mehta (2003) in Playing Large Games Using Simple Strategies (pdf link). The idea is, given $\epsilon$ and the number of strategies $n$, let $k = 12 \ln n / \epsilon^2$. Enumerate all mixed strategies with probabilities that are a multiple of $1/k$ for each player (there are ${n + k -1 \choose k}^2$ pairs of strategies to look at) and check each pair to see if it is an $\epsilon$-equilibrium; the authors prove that at least one such pair must be.

Both of these are covered in this 2004 article "On Algorithms for Nash Equilibria." I am not sure if there is anything faster that has since been discovered; I guess not for the general case, but there are definitely faster algorithms for certain classes of games. One reference would be On Oblivious PTAS's for Nash Equilibrium by Daskalakis and Papadimitriou (arxiv link), also The Approximate Rank of a Matrix and its Algorithmic Applications by Alon et al from this year's STOC (pdf link).

-