Lowest Unique Ordinal Game

139 Views Asked by At

The "lowest unique integer game" is widely-known: Some number of players each pick an integer from the range $[1, n]$ and the winner is the player who chose the lowest unique integer (if such a player exists; otherwise, the game is a tie). People have also considered the version where there is no upper bound on the set of integers you can choose from. (I first saw it in this blog, but that page is no longer available. It was also considered in this CS.SE post and this Math.SE post.) I am interested in what happens if we play this game on an ordinal $\alpha$. That is, each player chooses an ordinal in the range $[1, \alpha)$ and the winner is the player that chose the smallest ordinal. (It seems traditional to start with $1$ instead of $0$ in this game.)

For the rest of this post, let's limit the number of players to $3$. In this case, the game on $\omega$ has a symmetric mixed strategy Nash equilibrium where each player picks the integer $k$ with probability $p_k = (1-x)x^{k-1}$ where $x$ is the real root of $x^3 + x^2 + x - 1 = 0$ (which also happens to be the Tribonacci constant!).

Here is the sketch: Assume that two of the players are playing with the same (mixed) strategy where they choose $i$ with probability $p_i$. Then if the third player chooses $k$, she wins if either both other players chose something larger than $k$ or if they chose the same integer less than $k$. That is, the probability that player 3 wins given that she chooses $k$ is

\begin{equation}\tag{*} \left(1 - \sum_{i=1}^{k} p_i\right)^2 + \sum_{i=1}^{k-1} p_i^2. \end{equation}

In order for this to be at equilibrium, these should be the constant as $k$ varies. Then, one just checks that $p_k = (1-x)x^{k-1}$ makes this true and satisfies that $\sum_{i=1}^\infty p_i = 1$.

Now let's consider the game on $\omega + 1$. This is the same as the above except now players can choose $\omega$ as well. Let's say that players 1 and 2 do this with probability $p_\omega$. Then the probability that player 3 wins by choosing the integer $k$ is just (*), and the probability that she wins choosing $\omega$ is just the probability that the other two players choose the same integer, which is $\sum_{i=1}^\infty p_i^2$. But this is just the limit as $k$ approaches $\infty$ of (*), which means that the previous equilibrium (along with $p_\omega = 0$) is an equilibrium for the game on $\omega+1$ as well.

My questions are:

  1. Is there a Nash equilibrium for the game on $\omega + 1$ where $p_\omega$ is nonzero? What about a non-symmetric equilibrium? Clearly, it's not categorically irrational for a player to pick $\omega$: If two players are playing with the strategy above then the third player will have the same probability of winning if she picks $\omega$ as if she picks $1$.

  2. Is this Nash Equilibrium unique? One can show that it is unique for the finite ordinals. What about for the infinite game?

  3. What about for larger countable ordinals? For example, $\omega + 10$ or $\omega \cdot 2$?

Some thoughts on question 1: I have a feeling the answer should be "no", but I'm not sure how to prove it. I've tried to find a strategy for the game on $\omega + 1$ of the same kind of exponential form $p_k = Ax^{k-1}, p_\omega = c$ but I keep running into obstructions when $c \neq 0$.

Another thing to notice is that the equations (*) imply that the sequence $\{p_1, p_2, \ldots\}$ is non-increasing. Indeed, comparing equation $k$ with equation $k+1$ we can rearrange to get $p_k^2 - p_{k+1}^2$ on one side where the other side is apparently nonnegative. But I can't seem to find a way to argue that $p_k \geq p_\omega$ for all $k$ (which would imply $p_\omega = 0$ as $\sum_{i=1}^\omega p_i = 1$).

1

There are 1 best solutions below

4
On BEST ANSWER

I think question 1 finds the root of the problem. When you consider the game on $\omega+1$ you need to define a new variable $p_\omega$ for the chance a player plays $\omega$. Your expression for the chance of winning for any finite ordinal is still correct but the sum of the $p_i$ for $i$ finite is now $1-p_\omega$. The chance of winning if you choose $\omega$ is $$ \sum_{i\lt \omega}p_i^2$$
For a given value of $p_\omega$ the argument for the $\omega$ strategy goes through nicely and one should choose $k$ with probability $(1-x)x^{k-1}(1-p_\omega)$ We can now find $p_\omega$ by claiming it should have the same chance of winning as if you choose $1$, so $$ \sum_{i\lt \omega}p_i^2=(1-p_1)^2\\ \sum_{i\lt \omega}\left((1-x)x^{k-1}(1-p_\omega)\right)^2=\left((1-x)(1-p_\omega)\right)^2$$ If we assume $p_\omega \gt 0$, we can find a $k$ such that $p_k \lt p_\omega$. Then the chance you will be tied choosing $k$ will be less than the chance you will be tied choosing $\omega$. If you are not tied at $k$, you will win all the time you would have won with $\omega$ and some more because the others could choose higher numbers. This means choosing $k$ dominates over choosing $\omega$. This says the $\omega+1$ strategy is the same as the $\omega$ strategy. I then believe this carries over to all higher ordinals.