A Simple Matrix Game
The following game popped into my head and I wondered if it had a Nash equilibrium.
Two players $A$ and $B$ simultaneously choose a number. Call these $n_A$ and $n_B$.
- If $n_A = n_B$, then it is a tie, and no payout is awarded.
- If $n_A = n_B + 1$, then $A$ wins $n_A$ dollars from $B$.
- Symmetrically, if $n_B = n_A + 1$, then $B$ wins $n_B$ dollars from $A$.
- Otherwise, the player who named the smaller number wins $\max(n_A, n_B)$ dollars
from the player who named the larger number.
Suppose the players are only allowed to play $0, 1, 2$.
Then the payoff matrix for $A$ looks like
| | $A$ |
| | 0 | 1 | 2 |
| 0 | 0 | 1 | -2 |
| $B$ | 1 | -1 | 0 | 2 |
| 2 | 2 | -2 | 0 |
Suppose $A$'s strategy is mixed $p_0, p_1, p_2$ with $\sum_i p_i = 1$.
At equilibrium $B$'s choice doesn't matter, so
\[p_1 - 2p_2 = -p_0 + 2p_2 = 2p_0 - 2p_1 \]
hence substituting $p_2 = 1 - p_0 - p_1$,
\[2p_0 + 3p_1 - 2 = -2p_1 -3p_0 + 2 = 2p_0 - 2p_1 \]
Looking at the last equation, we see $p_0 = 2/5$, so
\[4/5 + 3p_1 - 2 = 4/5 - 2p_1 \]
\[ 5p_1 = 2 \]
\[ p_1 = 2/5 \]
\[ p_2 = 1/5 \]
Right, since the payoffs are symmetric, we should additionally expect that the expected payoff is zero.
What about with $0,1,2,3$? We have
| | $A$ |
| | 0 | 1 | 2 | 3 |
| 0 | 0 | 1 | -2 | -3 |
| $B$ | 1 | -1 | 0 | 2 | -3 |
| 2 | 2 | -2 | 0 | 3 |
| 3 | 3 | 3 | -3 | 0 |
giving us the equations
\[0 = p_1 - 2p_2 -3p_3 \]
\[0 = -p_0 + 2p_2 -3p_3 \]
\[0 = 2p_0 - 2p_1 + 3p_3 \]
\[0 = 3p_0 + 3p_1 - 3p_2 \]
so $p_0 = p_1$ so $p_3 = 0$ and $p_2 = p_0 / 2$. Again we get $(2/5, 2/5, 1/5)$, which
is a little surprising.
What about $0,1,2,3,4$? We have
\[0 = p_1 - 2p_2 -3p_3 - 4p_4\]
\[0 = -p_0 + 2p_2 -3p_3 -4p_4\]
\[0 = 2p_0 - 2p_1 + 3p_3 -4p_4\]
\[0 = 3p_0 + 3p_1 - 3p_2 + 4p_4\]
\[0 = 4p_0 + 4p_1 + 4p_2 - 4p_3\]
Right away we know $p_3 = p_0 + p_1 + p_2$, so
\[0 = -3p_0 -2 p_1 - 5p_2 - 4p_4\]
\[0 = -4p_0 -3p_1 - p_2 -4p_4\]
\[0 = 5p_0 + 1p_1 + 3p_2 -4p_4\]
\[0 = 3p_0 + 3p_1 - 3p_2 + 4p_4\]
To eliminate $p_4$, we can subtract or add neighboring equations.
\[0 = p_0 + p_1 - 4p_2 \]
\[0 = -9p_0 -4p_1 - 4p_2 \]
\[0 = 8p_0 + 4p_1 \]
This seems impossible to satisfy with probabilities in $[0,1]$. What's going on? I must
have made an algebra mistake somewhere.
Maybe I've Totally Forgotten How Game Theory Works
Tried using the solver here:
http://cgi.csc.liv.ac.uk/~rahul/bimatrix_solver/
And it seems to be saying that (2/5,2/5,1/5) is the best strategy
even for arbitrarily large numbers of moves! I guess the penalty
of big plays just dwarfs the chance of one-upping your opponent's
play. What if you're only penalized according to the size of their play?
- If $n_A = n_B$, then it is a tie, and no payout is awarded.
- If $n_A = n_B + 1$, then $A$ wins $n_A$ dollars from $B$.
- Symmetrically, if $n_B = n_A + 1$, then $B$ wins $n_B$ dollars from $A$.
- Otherwise, the player who named the smaller number wins $\min(n_A, n_B)$ dollars
from the player who named the larger number.
This appears to stabilize at
$(0, 1/37, 12/37, 10/37, 11/37, 3/37)$ which to me is also a big surprise.