How to choose the smallest number not chosen?

Question

So there are $n$ people, each choosing some non-zero counting number. You don't know what any of them choose. To win, you must choose the smallest number; but if you choose the same number as somebody else, you are disqualified. How would you decide what number $k$ is best to choose? I feel like $k\le n$, but apart from that I have no idea where to start. Any ideas?

EDIT: So to avoid a trivial paradox and to somewhat model real human behavior, we want the $n$ people to choose numbers reasonably but not necessarily perfectly. For instance, nobody else is gonna choose $k > n$, as that would be silly. Since choosing 1 being unreasonable would lead to paradox, we'll also say 1 could be chosen, but won't necessarily be picked.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

I believe the following is a proof that, in the simplified case of exactly 3 players, there doesn't exist a computable optimal strategy.

Assume they're all perfect logicians, and assume there is a computable optimal strategy, ie assume the optimal strategy consists of picking $n$ with probability $f(n)$ where $f(n)$ is a computable function.

Then player 1 can compute her probably of winning when she picks a given number $n$ as $$win(n) = \left(1 - \sum_{i=1}^n f(i)\right)^2 + \sum_{i=1}^n f(i)^2 \,,$$ as she wins iff neither other player picks a number $\leq n$ or both pick the same number $<n$. Now if she can compute $m=max\{win(i)\}_{i\geq1}$ then she will pick $m$ deterministically (ie $f(m) = 1, f(n)= 0, \forall n \neq m$). As the game is the same from the other players' points of view, they will also pick $m$ deterministically so they all have $0$ chance of winning, which is obviously not an optimal strategy, a contradiction. Therefore $win(n)$ must not have a computable maximum.

However, observe that the probability that no one wins is $\sum_{i=1}^\infty f(i)^3$. As we are assuming all three players are following the same strategy (because they're all perfectly logical and there is an optimal strategy), this means they all have equal probability $p$ of winning, where $$p = \frac{1}{3} \times \left( 1 - \sum_{i=1}^\infty f(i)^3 \right) \,.$$ Thus $$\lim_{n \rightarrow \infty} \sum_{i=1}^n 3win(i) + f(i)^3 = 1 \,.$$

Using the limit definition and choosing $\epsilon = win(1)$, we have $$\exists N s.t. \sum_{i=1}^N 3win(i) + f(i)^3 > 1 - win(1) \,,$$ so there can't be any value $j > N$ with $win(j) \geq win(1)$. But then $$max_{1 \leq i \leq N} \{win(i)\} \geq win(1) > max_{i \geq N} \{win(i)\} \,,$$ so the max is computable as $$max_{1 \leq i \leq N} \{win(i)\} = max\{win(i)\}_{i\geq1} \,.$$ The above contradiction then follows, and so the original assumption that $f(n)$ is computable is false.