Optimal strategy for a 3 players infinite game

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$


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

Tags:

Game Theory