# 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? Jan 29 '17 at 4:44
• I don't think it matters, but let's keep it from 1 onward. 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. Jan 29 '17 at 5:04
• Why would it be silly to choose $k$ > $n$? Jan 29 '17 at 8:08

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.

• What happens if players are not required to follow the same strategy? Oct 28 '19 at 18:58

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. 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$. 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. 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$. 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. 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$. Jan 31 '17 at 10:15

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.

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

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