Go hungry with Almost Free Lunches

Consider the following game, called "Almost Free Lunches" (EDIT: this seems to be a variant of the traveller dilemma). You name any pound-and-pence amount between £0 and £1,000,000; your opponent does likewise. Then you will both get whichever amount named was lowest.

On top of that, the person who named the highest amount must give £0.02 to the other. If you tie, no extra money changes hands.

What's the Nash equilibrium of this game? Well:

• The only Nash equilibrium of Almost Free Lunches is for both of you to name £0.00.

Proof: Suppose player A has a probability distribution $p_A$ over possible amounts to name, and player $B$ has a probability distribution $p_B$ over possible amounts. Let $m_A$ be the highest amount such that $p_A\left(m_A\right)$ is non-zero; let $m_B$ be the same, for $B$. Assume that $(p_A,p_B)$ is a Nash equilibrium.

Assume further that $m_A\ge m_B$ (if that's not the case, then just switch the labels $A$ and $B$). Then either $m_A>$ £0.00 or $m_A=$ £0.00 (and hence both players select £0.00).

We'll now rule out $m_A>$ £0.00. If $m_B>$ £0.00, then player $A$ can improve their score by replacing $m_A$ with $m_A^{\prime }=m_B-\pounds 0.01$. To see this, assume that player $B$ has said $n_B$, and player $A$ has said $m_A$. If $n_B<m_A^{\prime }<m_A$, then player $A$ can say $m_A^{\prime }$ just as well as $m_A$ - either choice gives them the same amount (namely, $n_B-$ £0.02).

There remain two other cases. If $n_B=m_A^{\prime }$, then $m_A^{\prime }$ is superior to $m_A$, getting $m_A^{\prime }$ (rather than $m_A^{\prime }-$ £0.02). And if $n_B=m_B$, then $m_A^{\prime }$ gets $m_A^{\prime }+$ £0.02 $=m_B+$ £0.01, rather than $m_B$ (if $m_A=m_B$) or $m_B-\pounds 0.02$ (if $m_A>m_B$).

Finally, if $m_B=$ £0.00, then player $A$ gets -£0.02 unless they also say £0.00.

Hence if $m_A>$ £0.00, the $p_A$ cannot be part of a Nash Equilibrium. Thus $m_A=$ £0.00 and hence the only Nash Equilibrium is at both players saying £0.00.

Pareto optimal

There are three Pareto-optimal outcomes: (£1,000,000.00, £1,000,000.00), (£1,000,000.01, £999,999.97), and (£999,999.97, £1,000,000.01). All of them are very much above the Nash Equilibrium.

Minmax and maximin

The minmax and maximin values are also both terrible, and also equal to £0.00. This is not surprising, though, as minmax and maximin implicitly assume the other players are antagonistic to you, and are trying to keep your profits low.

Arbitrary badness with two options

This shows that choosing the Nash Equilibrium can be worse than almost every other option. We can of course increase the maximal amount, and get the Nash Equilibrium to be arbitrarily worse than any reasonable solution (I would just say either £1,000,000.00 or £999,999.99, and leave it at that).

But we can also make the Nash Equilibrium arbitrarily close to the worst possible outcome, and that without even requiring more than two options for each player.

Assume that there are four ordered amounts of money/utility: $n_3>n_2>n_1>n_0$. Each player can name $n_2$ or $n_1$. Then if they both name the same, they get that amount of utility. If they name different ones, then then player naming $n_2$ gets $n_0$, and the player naming $n_1$ gets $n_3$.

By the same argument as above, the only Nash equilibrium is for both to name $n_1$. The maximum possible amount is $n_3$; the maximum they can get if they both coordinate is $n_2$, the Nash equilibrium is $n_1$, and the worst option is $n_0$. We can set $n_1=n_0+ϵ$ and $n_3=n_2+ϵ$ for arbitrarily tiny $ϵ>0$, while setting $n_2$ to be larger than $n_1$ by some arbitrarily high amount.

So the situation is as bad as it could possibly be.

Note that this is a variant of the prisoner's dilemma with different numbers. You could describe it as "Your companion goes to a hideous jail if and only if you defect (and vice versa). Those that don't defect will also get a dust speck in their eye."