6
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ This is Exercise 1.2 in Algorithmic Game Theory by Noam Nisan. Unless he underestimated the problem, one might expect that there's an easier way to prove the limit without finding a closed form for the finite result. $\endgroup$ – joriki Feb 9 '13 at 20:42
  • $\begingroup$ @joriki I take my hat off to you. But, finding the closed form for the finite result might very well be considered the "easiest" (or: naive) way. However, your point is well taken, and I encourage all to find the most direct proof and include the hint: "You may use the fact that $\lim(1−1/n)^n=1/e$ as $n$ goes to infinity." $\endgroup$ – Keep these mind Feb 9 '13 at 22:06
  • $\begingroup$ Please do keep your hat on; after all I merely found the problem whereas you found the solution :-) $\endgroup$ – joriki Feb 9 '13 at 22:21
  • $\begingroup$ thank you for the answer!!!But can you explain the solution in a more simple way....i lost it with the asymptotic analysis! $\endgroup$ – user61542 Feb 10 '13 at 18:41
  • $\begingroup$ well....im not a mathematics expert....so i cant unterstand how equation 3.7 will help me find the solution...assuming that m=n of course helped but not enough! $\endgroup$ – user61542 Feb 10 '13 at 20:56
0
$\begingroup$

Another answer to my question is for a strategy ai for player A must be ≥ from every other strategy a-i in column j. the same for player B bj. PNE=pure nash euilibrium. with
Pr((ai,bj)=PNE)=
=Pr(ak≤ai)n*Pr(bt≤bj)n=
=Pr(ak≤ai)2n=(1/2)2n
Then the asked probability is
P(∃PNE)=P(∃(ai,bj))=1-(1-(1/2)2n)n2

$\endgroup$
  • 1
    $\begingroup$ this answer is definitely wrong as you are supposing each event independent but they're actually not. Moreover if n tends to +inf the result of your expression is 0, not 1−1/e $\endgroup$ – HAL9000 Mar 18 '14 at 18:03
0
$\begingroup$

I believe you wanted the fact that the probability of pure Nash Equilibrium existing is at least $1-\frac{1}{e}$. The fact that it is exactly $1-\frac{1}{e}$ is highly non-trivial (I believe) and that is why it finds its place in the above mentioned research paper. Showing the inequality is not difficult.

First let us take the payoff matrix and break it into two matrices- one for the row player (call this matrix $R$) and one for the column player (call it $C$). Now I will make sure that we understand Nash Equilibrium properly in this setup. So Nash Equilibrium is $(i,j)$ means that row player wouldn't change his strategy of playing $i$ which means that $(i,j)$ is maximum in its column in $R$. Similarly column player wouldn't change his choice of $j$ meaning that $(i,j)$ is maximum in its row in $C$.

Now I will do some unnecessary operations which will help us visualize the problem in a simpler way. I will rearrange the action space of row player-which allows me to swap rows of $R$ and $C$ simultaneously without changing the game. I will do this in such a way that the first $k_1$ rows of $C$ contain their respective maximum elements in their first columns. Similarly the next $k_2$ rows of $C$ contain their respective maximum elements in their second columns. Like this I go on and there are $k_i$ rows with maximas in their $i$-th columns. (Note that $\forall i, 0\le k_i\le n$)

enter image description here

Now we will have a pure Nash Equilibrium if and only if the first column, $C_1$, of $R$ has its maximum element in the first $k_1$ elements or if the second column $C_2$ has its maximum element among the elements $k_1+1,k_1+2,...,k_1+k_2$ and so on (i.e. $C_i$ needs to have its maximum element in the corresponding $i$ elements :-namely, $(k_1+k_2+...+k_i)+1,(k_1+k_2+...+k_i)+2,...,$ $(k_1+k_2+...+k_i+k_{i+1}$)

Whethere there is a pure Nash Equilibrium corresponding to the first $k_1$ rows of $C$ is independent of whether there is a pure Nash Equilibrium corresponding to the next $k_2$ rows of $C$ (or equivalently corresponding to first row of $R$) since the first event depends only on first $k_1$ rows of $C$ and first column of $R$ while the next event depends only on the next $k_2$ rows of $C$ and the second column of $R$ which are independent to each other. Similarly, it is easy to see that the event of a pure Nash Equilibria corresponding to the relevant $k_i$ rows of $C$ is independent of the event of a pure Nash Equilibrium in the relevant $k_j$ rows of $C$. $(i\ne j)$

Now we do the calculations :

Probability of no pure Nash Equilibrium corresponding to the first column of $R$ $=1-\frac{k_1}{n}$

Probability of no pure Nash Equilibrium corresponding to the second column of $R$ $=1-\frac{k_2}{n}$ $$.$$ $$.$$ $$.$$ Probability of no pure Nash Equilibrium corresponding to the second column of $R$ $=1-\frac{k_n}{n}$

And these are all independent so probability of no pure Nash Equilibrium in game $$=\prod_{i=1}^{n}(1-\frac{k_i}{n})\le\prod_{i=1}^{n}(1-\frac{1}{n})$$

This is true since the terms $1-\frac{k_i}{n}$ sum up to $n-1$ and are all positive. So their product is maximum when they are all equal. Also we have the following : $$\lim_{n\to\infty}\prod_{i=1}^{n}(1-\frac{1}{n})=\frac{1}{e}$$ So probability of no pure Nash Equilibrium is $\le \frac{1}{e}$ as $n\to \infty$

And hence probability of a pure Nash Equilibrium existing is $\ge 1-\frac{1}{e}$

$\endgroup$

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.