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!

| cite | improve this question | | | | |
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Greinecker Feb 8 '13 at 9:48

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.

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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