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

Hi,

How to find, or at least express, the equilibrium of a zero-sum game with an $n*n$ payoff matrix (each player has $n$ strategies) and the payoff of the entry $(i,j)$ is $u(i,j)$. $u$ a random function of the strategies $i$ and $j$.

What about the case where $n \rightarrow \infty$.

Any reference or code is welcome.

Thanks a lot!

share|improve this question
1  
Do the players observe the random payoff before or after they made their choices? In the second case, you can just take the expectation $E[u(i,j)]$ as the payoff of $(i,j)$ and reduce the problem to a standard zero-sum game. –  Michael Greinecker Feb 8 '13 at 9:48

1 Answer 1

up vote 1 down vote accepted

Assuming the $u(i,j)$ are iid with a continuous distribution, the probability that $(i,j)$ is a saddle point, i.e. that $u(i,j)$ is the greatest entry in its column and the least in its row, is $((n-1)!)^2/(2n-1)! \approx 2^{1-n^2} \sqrt{\pi/n}$ as $n \to \infty$. Thus the probability that the game has a saddle point goes to $0$ (and very rapidly) as $n \to \infty$. Instead, with probability approaching $1$ the optimal strategies are mixed strategies.

share|improve this answer

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.