Original Question: Each of $n$ players secretly choose a natural number. Among the players whose number does not coincide with anyone else, the one with the smallest number wins. State the Nash Equilibrium strategy of the players.
My Attempt: Let the winner have payoff $1$ and others $0$. By symmetry, we let each player have the same prob. $P_{i}$ to choose number $i$.
Now suppose only one player slightly differs from the equilibrium and chooses numbers $a,b$ by prob. $P_{a}+p,P_{b}-p$ instead. We have that
$K_{i}=1-(1-P_i)^{N-1}-(N-1)P_i(1-P_i)^{N-2}$
be the prob. that the number $i$ is chosen at least twice among the rest $N-1$ players. Hence the expected payoff of the player before differing is
$\frac{1}{N}=P_1 (1-P_1)^{N-1}+P_2\{(1-P_1-P_2)^{N-1}+K_{1}\}+...=\sum_{i=1}^{\infty}P_{i}\{(1-\sum_{j=1}^{i}P_{j})^{N-1}+ \sum_{j=1}^{i-1}K_{j}\}$
and after differing
$\sum_{i=1，i\neq a,b}^{\infty}P_{i}\{(1-\sum_{j=1}^{i}P_{j})^{N-1}+ \sum_{j=1}^{i-1}K_{j}\}+(P_a+p)\{(1-\sum_{j=1}^{a}P_{j})^{N-1}+ \sum_{j=1}^{a-1}K_{j}\}+(P_b-p)\{(1-\sum_{j=1}^{b}P_{j})^{N-1}+ \sum_{j=1}^{b-1}K_{j}\}$
by definition of Nash Equilibrium we know that such a change does not result in positive payoff change, so
$-p\{(1-\sum_{j=1}^{a}P_{j})^{N-1}+ \sum_{j=1}^{a-1}K_{j}\}+p\{(1-\sum_{j=1}^{b}P_{j})^{N-1}+ \sum_{j=1}^{b-1}K_{j}\}\geq0$
Since this must hold for any $a,b$, we guess that all terms in curly brackets are the same, let it be $C$, so
$\frac{1}{N}=C\sum_{i=1}^{\infty}P_{i}=C $
Finally we have the recursive relation
$\{(1-\sum_{j=1}^{i}P_{j})^{N-1}+ \sum_{j=1}^{i-1}K_{j}\}=\frac{1}{N}, \\ K_{i}=1-(1-P_i)^{N-1}-(N-1)P_i(1-P_i)^{N-2}$
which gives all required $P_{i}$.
My Related Questions:
- Does the attempt above give a correct result?
- Are there any other Nash Equilibria? e.g. asymmetric strategies