# How to choose the smallest number not chosen?

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.

• Are you defining $0$ as a counting number? – Harnoor Lal Jan 29 '17 at 4:44
• I don't think it matters, but let's keep it from 1 onward. – Vedvart1 Jan 29 '17 at 4:46
• Sounds like a paradox. If all the players were game theorists they would all choose $k$ and be disqualified ! – WW1 Jan 29 '17 at 4:59
• Our teacher had us do this experiment once (in a class of 30 students), and the winning number was 12. – SSepehr Jan 29 '17 at 5:04
• Why would it be silly to choose $k$ > $n$? – immibis Jan 29 '17 at 8:08

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.

• This works for uniformly random choices by other players, but could it be extended for some given probability distribution of how the other players will choose? I'm trying now to do so, but I'm not very good with generalizing probability like this and I don't appear to be making progress. – Vedvart1 Jan 29 '17 at 5:35
• I wouldn't choose $1$, as there's always someone else who thinks this way and picks $1$, especially for large $n$. – SSepehr Jan 29 '17 at 5:39
• I understand your point and I am aware of the fact that the model that I described would only work if all players would be aware of the most optimal strategy. We would probably need to have a distribution of probability with which a given number is chosen. – Maciej Caputa Jan 29 '17 at 5:42

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.

• I think to calculate $K_1$ you have to add up the probabilities calculated before instead of multiplying them. Also you should care about $\left\{2,3\right\}$ containing basically two different situations, based on which of the other two players chose $2$. – elias Jan 29 '17 at 10:20
• Also, the main idea of a mixed strategy is to play according the $K$ probability distribution instead of playing the number with the highest probability every time. – elias Jan 29 '17 at 10:24
• You are still missing a term from $K_1$. In fact $K_1=p_2^2+2p_2p_3+p_3^2=(p_2+p_3)^2=(1-p_1)^2$, which is not a big surprise: you win exactly if no one else chooses 1. You got $K_2$ right, but $K_3=p_1^2+p_2^2$. – elias Jan 31 '17 at 10:15

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.

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.

• Why are the three people picking from 1 to 4, rather than 1 to 3? – Glen O Jan 29 '17 at 11:19
• I think it does change the probabilities by lowering the chance of a clash – Michael Jan 29 '17 at 13:20