Game theory Computing pure Nash equilibrium probability

Question

We have a $2$-player game and each player has $n$ strategies. The payoffs for each player are in range $\left[0,1\right]$ and are selected at random. Show that the probability that this random game has a pure deterministic Nash equilibrium approaches $1-1/\mathrm e$ as $n$ goes to infinity. Can anyone find a solution to this problem?

Answer 1

I think this 1968 paper (DOI) covers your question.

A formula is derived for the probability that a "random" $m$-by-$n$ two-person noncooperative game has an equilibrium-point solution in pure strategies. The limit of this probability as $m, n\to\infty$ is shown to be $1-1/e$.

With respect to the comments; you can rewrite $(3.8)$ - as the authors do just after $(5.1)$ - by splitting $(3.8)$ into terms of $m$ and $n$, and using te following for the $n$-term (and similarly for the $m$-term).

$$\binom{n}{k}(1/n)^k\\ ={\color{orange}{n!}\over{\color{brown}{k!}\color{orange}{(n-k)!}}}(1/n)^k\\ =\color{brown}{1\over{{k!}}}\color{orange}{{n!}\over{(n-k)!}}(1/n)^k\\ ={1\over{k!}}\left[\color{cyan}(n\color{cyan}{-0)}(n-1)(n-2)\cdots(n-k+1)\right](1/n)^k\\ ={1\over{k!}}\color{green}{n^k}\left[{(1-0/n)}(1-1/n)(1-2/n)\cdots(1-{{k-1}\over n})\right]\color{green}{(1/n)^k}\\ ={1\over{k!}}\left[{(1-\color{red}0/n)}(1-\color{red}1/n)(1-\color{red}2/n)\cdots(1-{\color{red}{k-1}\over n})\right]\\ ={1\over{k!}}\prod_\color{red}{j=0}^\color{red}{{k-1}}(1-\color{red}j/n)$$

(I hope the colours help. I'm trying to learn this MathJax.)

Answer 2

Another answer to my question is for a strategy a_i for player A must be ≥ from every other strategy a_-i in column j. the same for player B b_j. PNE=pure nash euilibrium. with
Pr((a_i,b_j)=PNE)=
=Pr(a_k≤a_i)ⁿ*Pr(b_t≤b_j)ⁿ=
=Pr(a_k≤a_i)²ⁿ=(1/2)²ⁿ
Then the asked probability is
P(∃PNE)=P(∃(a_i,b_j))=1-(1-(1/2)²ⁿ)ⁿ²