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.



Simulating Mixed Nash Equilibria
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](https://math.stackexchange.com/questions/97858/finding-nash-equilibria-using-support-enumeration). 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](https://mpi-sb.mpg.de/departments/d1/teaching/ws11/AGT/NE-LiMaMe03.pdf)). 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](http://web.mit.edu/tabbott/Public/final.pdf) "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](http://arxiv.org/abs/1102.2280)), also *The Approximate Rank of a Matrix and its Algorithmic Applications* by Alon et al from this year's STOC ([pdf link](http://www.tau.ac.il/~nogaa/PDFS/epsrankstoc3.pdf)).


