Optimal strategy for a 3 players infinite game

Question

I've been asked the following game theory problem:

Each one of three players secretly picks a positive integer. The winner of the game, if any, is the player who picked the smallest number that no one else chose.

Is there an optimal strategy for this game?

Observations Nash' theorem about the existence of an equilibrium doesn't apply to this game, because each player has infinitely many possible choices.

A way I thought to tackle the problem is the following. I assume the existence of an optimal strategy, and I model it by a function $f: \mathbb{Z}_{>0} \rightarrow \mathbb{R}$ such that $\sum_{n=1}^\infty f(n) =1$, which corresponds to picking $n$ with probability $f(n)$. Then, since the strategy is optimal, every player is playing according to this strategy, and the probability $p_f(n)$ that a player wins playing $n$ is given by

$$p_f(n) = f(n) \left(\left(\sum_{m=n+1}^\infty f(m) \right)^2 + \sum_{m=1}^{n-1} f(m)^2 \right).$$

Where $f(n)$ is the probability that she plays $n$, $\left(\sum_{m=n+1}^\infty f(m) \right)^2$ is the probability that both the other players play a number larger than $n$ and $\sum_{m=1}^{n-1} f(m)^2$ is the probability that both the other players play the same number smaller than $n$.

Now we want to maximize the probability of a player winning, i.e. $$p_f = \sum_{n=1}^\infty f(n) \left(\left(\sum_{m=n+1}^\infty f(m) \right)^2 + \sum_{m=1}^{n-1} f(m)^2 \right).$$

I'm a bit at a loss on how to proceed here. If we make the reasonable choice $f(n) = 2^{-n}$, then $p_f = \frac{2}{7}$. This doesn't seem too bad, but it's not optimal. Indeed if two players play this strategy and the third plays the pure strategy $N\geq 2$, she increases her chances to win.

On the other hand the strategy given by $$f_N(n) =\begin{cases} \frac{1}{N}, & \text{ for }n\leq N \\ 0, & \text{ otherwise} \end{cases} $$ is such that $p_{f_N} \rightarrow \frac{1}{3}$ for $N\rightarrow \infty$. But it is clearly very far from being optimal.

I'm grateful for any answer, suggestion or comment.

Answer 1

In game theorey the players are selfish, i.e. the probability of winning that we want to maximize is:

$$p(f,g,h) = \sum_{n=1}^{\infty} f(n) \Bigg(\bigg(\sum_{k=n+1}^{\infty} g(k) \bigg)\bigg(\sum_{k=n+1}^{\infty} h(k) \bigg) + \sum_{k=1}^{n-1} g(k)\cdot h(k) \Bigg),\tag{$\spadesuit$}$$

where $f$, $g$ and $h$ are probability distributions for the first, second and third player respectively. In fact what we want is that $f = g = h$, but that is not true when considering individual optimizations from the player perspective (i.e. the conditions for a Nash Equilibrium).

Now, fix some arbitrary functions $f_1, g_1, h_1$ and observe that if $\frac{\partial p}{\partial f(i)}(f_1,g_1,h_1) < \frac{\partial p}{\partial f(j)}(f_1,g_1,h_1)$ then there exists a tiny strictly positive amount $\delta$ of probability mass that we could shift from number $i$ to number $j$, i.e. take

$$f_2(k) = \begin{cases} f_1(k)-\delta & \text{ when }k = i\\ f_1(k)+\delta & \text{ when }k = j\\ f_1(k) & \text{ otherwise}, \end{cases}$$

and strictly increase the value of $p$, i.e. $p(f_1,g_1,h_1) < p(f_2,g_1,h_1)$. Thus, at a Nash Equilibrium $(f,g,h)$ we have to have $\frac{\partial p}{\partial f(i)}(f,g,h) = \frac{\partial p}{\partial f(j)}(f,g,h)$ for any $i$ and $j$.

Fortunately $(\spadesuit)$ gives us a nice formula for that. Adding our requirement for an optimal strategy that $f = g = h$ we get $q_i = q_j$ where ($q_n$ was intentionally kept to be consistent with answer of @smcc):

\begin{align} q_n &= \frac{\partial p}{\partial f(n)}(f,g,h)\ \Bigg|_{g = h = f} \\ &= \bigg(\sum_{k=n+1}^{\infty} g(k) \bigg)\bigg(\sum_{k=n+1}^{\infty} h(k) \bigg) + \sum_{k=1}^{n-1} g(k)\cdot h(k)\ \Bigg|_{g = h = f} \\ &= \bigg(\sum_{k=n+1}^{\infty} f(k) \bigg)^2 + \sum_{k=1}^{n-1} f^2(k) \\ &= \bigg(1-\sum_{k=1}^{n} f(k) \bigg)^2 + \sum_{k=1}^{n-1} f^2(k). \end{align}

I cannot prove that this is the unique equilibrium, but we can show that there exist one particular, namely $f(n) = (1-d)\cdot d^{n-1}$ where $d$ denotes the probability of not picking number $1$ and it happens to be the only real root of $d^3+d^2+d^1 - 1 = 0$.

With that hypothesis we have that

\begin{align} q_n &= \bigg(1-\sum_{k=1}^{n} (1-d)\cdot d^{k-1} \bigg)^2 + \sum_{k=1}^{n-1} \big((1-d)\cdot d^{k-1}\big)^2 \\ &= d^{2n} + \frac{(1-d)(d^2-d^{2n})}{(1+d)d^2} = \frac{(1-d)d^2+d^{2n} \overbrace{(d^3+d^2+d-1)}^{\text{zero}}}{(1+d)d^2} = \frac{1-d}{1+d} \end{align}

Thus, all the $q_n$'s are constant and so $(f,f,f)$ is a Nash Equilibrium. Wolfram Alpha says

$$d = \frac13\left(\sqrt[3]{17+3\sqrt{33}}-\sqrt[3]{\frac{2}{17+3 \sqrt{33}}}-1\right) \approx 0.543689.$$

On a final note, equation $d^3+d^2+d^1 = 1$ or perhaps better $$\big(1-f(1)\big)^3+\big(1-f(1)\big)^2+\big(1-f(1)\big)^1 = 1$$ suggest that $f$ satisfies $f(n) = f(n+1) + f(n+2) + f(n+3)$ (like a reversed 3-term Fibonacci sequence), but I can't find any probabilistic interpretation for that. Maybe someone can use it to obtain a nice elegant proof?

I hope this helps $\ddot\smile$

Answer 2

First note that there are infinitely many pure strategy Nash equilibria where one player plays $1$, and the other players each choose some larger integer(s). There is no incentive to deviate because the players with integers larger than $1$ cannot win.

Similarly there are infinitely many Nash equilibria where one player plays $1$ and the other players mix over larger integers in any way.

There are also three equilibria where two players play $1$ and the third plays $2$.

---

Let us look for a symmetric equilibrium where players play all positive integers with positive probability. Let $p_i$ denote the probability of playing $i$. It must be that (given the mixed strategy the others are playing) the probability of winning from playing any integer with probability one is the same.

If a player plays $n$ they win with probability

$$q_n=\left(\sum_{i=n+1}^\infty p_i \right)^2 + \sum_{i=1}^{n-1} p_i^2 .$$

Since $$\sum_{i=n+1}^\infty p_i=1-\sum_{i=1}^np_i$$ we can write this as

$$q_n=\left(1-\sum_{i=1}^n p_i\right)^2 + \sum_{i=1}^{n-1} p_i^2.$$

---

We require $q_n=\frac{1}{3}k^2$ for all positive integers $n$, where $k^2$ is the probability (given the players' common strategy) that there is a winner, i.e.

$$k^2=1-\sum_{i=1}^\infty p_i^3.$$

---

When $n=1$ we have

$$q_1=(1-p_1)^2=\frac{1}{3}k^2$$

so $p_1=1-\frac{k}{\sqrt{3}}$.

When $n=2$ we have

$$q_2=(1-p_1-p_2)^2+p_1^2=\frac{1}{3}k^2$$

so $p_2=\frac{1}{\sqrt{3}}\left(k-\sqrt{2\sqrt{3}k-3}\right)$.

Continuing, in this way one can solve recursively for each $p_i$ as a function of $k^2$ and then calculate $k^2$.

---

Note that there cannot be a symmetric equilibrium where they play only integers up to $n$ with positive probability, because a player would have a higher probability of winning from playing $n+1$ than playing $n$.