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.
 A: 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: 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.
A: 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.
A: 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.
A: 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.
