How to choose the smallest number not chosen?

Solution 1:

Contrary to intuition, the Nash equilibrium for this game (assuming $n\geq 2$) must have positive probability of choosing any positive integer. Assume not, so there is some integer $m$ such that the Nash equilibrium picks $m$ with probability $p_m>0$ but never picks $m+1$. Suppose everyone else is playing that strategy, and consider what happens if you play the modified strategy which instead picks $m+1$ with probability $p_m$ and never picks $m$. This performs exactly the same if you pick some number other than $m+1$. If you pick $m+1$ and would have won had you picked $m$ then you will still win, since no-one else has picked $m+1$ (because they can't) or $m$ (by assumption that you would have won by picking $m$). You also win in the event that you pick $m+1$ and everyone else picks $m$, which has positive probability. So the original strategy wasn't a Nash equilibrium, because this one beats it.

Solution 2:

Given that there are $n$ players, let's assume that each player must choose a number $k \in \{z \in \mathbb{Z} | 1 \le z \le n\}$. Note that the order of players picking a number does not affect the outcome.

Some thoughts:

When $\textbf{n = 2}$ equilibrium is achieved when both players choose the smallest number i.e. $1$.

For case $\textbf{n = 3}$, let two numbers from $\{1,2,3\}$ be already choose, then

it is impossible to win whenever $\{1, 2\}$, $\{1, 3\}$ are chosen by others.

it is possible to win when $\{2, 3\}$, $\{1, 1\}$, $\{2, 2\}$ or $\{3, 3\}$ by others.

Let's consider what happens if we choose

$\rightarrow$ winning number

$1$

$\{1, 2\} \rightarrow 2$

$\{1, 3\} \rightarrow 3$

$\{2, 3\} \rightarrow 1$ We win!

$\{1, 1\}$ No winner.

$\{2, 2\} \rightarrow 1$ We win!

$\{3, 3\} \rightarrow 1$ We win!

$2$

$\{1, 2\} \rightarrow 1$

$\{1, 3\} \rightarrow 1$

$\{2, 3\} \rightarrow 3$

$\{1, 1\} \rightarrow 2$ We win!

$\{2, 2\}$ No winner.

$\{3, 3\} \rightarrow 2$ We win!

$3$

$\{1, 2\} \rightarrow 1$

$\{1, 3\} \rightarrow 1$

$\{2, 3\} \rightarrow 2$

$\{1, 1\} \rightarrow 3$ We win!

$\{2, 2\} \rightarrow 3$ We win!

$\{3, 3\}$ No winner.

Therefore it has been shown that choosing $1$ when $n = 3$ gives us best chance of winning. Hence, $k = 1$ is the equilibrium.

This approach can be generalised for more players.

Solution 3:

Expanding on Maciej Caputa's answer, I've generalized it to $n=3$ with any probability density function, not just uniform random choices. Let $P(\text{Our Success})=K$ and $P(\text{A player chooses n)}=p_n.$ If we choose 1,

$\{1,1\} \rightarrow $No-one with $P=p_1p_1$

$\{1,2\} \rightarrow 2$ with $P=p_1p_2$

$\{1,3\} \rightarrow 3$ with $P=p_1p_3$

$\{2,2\} \rightarrow $We win! with $P=p_2p_2$

$\{2,3\} \rightarrow $We win! with $P=p_2p_3$

$\{3,3\} \rightarrow $We win! with $P=p_3p_3$ $$\text{If we choose 1, } K_1=p_2^2+2p_2p_3+p_3^2$$ Note that $K_1 = (p_2+p_3)^2=(1-p_1)^2$. Similarly, $K_2=p_1^2+p_3^2$ and $K_3=p_1^2 + p_2^2$. So you should choose each number with the following probabilities:

$1: p_2^2+p_2p_3+p_3^2$

$2 :p_1^2+p_3^2$

$3: p_1^2 + p_2^2.$

But generalizing to any $n$ is proving more difficult than expected.

EDIT: Corrected mistakes pointed our by @elias.

Solution 4:

Edit 18 Nov 2021
With more than three players, I get a sequence of simultaneous polynomial equations. I could not solve them. Instead, I picked a random starting set of probabilities, and did a random walk to minimize the variance of the probabilities of winning. I got the following graph for Nash equilibrium probabilities of selecting each number, depending on the number of players in the game.

Edit 7 Nov 2021
Suppose there are exactly three players. Suppose the first two play $1$ with probability $1-p$, and something else with probability $p$.
To be a Nash equilibrium, the third player's chances of winning, $W$, are the same if he picks 1 or he doesn't.
If he picks 1, he needs the other two to not pick 1.
If he doesn't pick 1 he needs either both the others do, or neither do. If neither do, we are back at the start, but choice 1 is ignored. .
$$W=p^2=(1-p)^2+p^2W$$ The only way this works is if $$p^2=(1-p)^2+p^4\\p=1,p=0.54369$$ Then the probability of picking $n$ is $(1-p)p^{n-1}$. Everyone's chance of winning is $p^2=0.2956$

For $N$ players, either 0, 2 or more rivals pick 1, then you need to be best of what's left. There is a recursion on the winning probability $W=f(p,N)$

$$W=f(p,N)=p^{N-1}=\sum_{k=0\\k\ne1}^{N-1}{N-1\choose k}(1-p)^kp^{N-1-k}f(p,N-k)$$ I will try to get a plot for the roots of that.

Edit 2 Feb 2017:
A rule of thumb is that there will be a unique number somewhere between $1$ and $n/\ln(n)$.

If everyone picks a value between 1 and $n/\ln(n)$, each value will be picked $\ln(n)$ times on average.

For a given value, the number of times it is picked follows a Poisson distribution, with $\lambda = \ln(n)$. The chance it is picked once is $\lambda e^{-\lambda}=\ln(n)/n$.

On average, one value will be unique.

If people pick numbers bigger than $n/\ln(n)$, there will be several unique numbers. Since only the lowest of these wins, they would be better off with smaller numbers - so this is not fruitful. If people spread out over twice the interval, there will likely be $\sqrt{n}$ unique values.

If people only pick values much less than $n/\ln(n)$, then each value is picked several times. Everyone is eliminated, and a winning strategy is to avoid the crush by picking a large value. Again, it is not fruitful to concentrate on small values. If people restrict to half the interval, there is one chance in $n$ of any unique values.