Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
@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
add comment

3 Answers

up vote 2 down vote accepted

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).

share|improve this answer
add comment

I believe that by "numerical simulation" you mean something in the spirit of an "adaptive dynamics". If I'm right, I could recommend the paper: Germano, Fabrizio, and Gabor Lugosi. "Global Nash convergence of Foster and Young's regret testing." Games and Economic Behavior 60.1 (2007): 135-154. to be found online e.g. here.

share|improve this answer
add comment

If by „Simulating Mixed Nash Equilibria” you simply mean algorithmically finding Nash equilibria, you can find interesting information in the section “3.2 General-player games” available here.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.