Nash equilibriums can be arbitrarily bad

7


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 over possible amounts to name, and player has a probability distribution over possible amounts. Let be the highest amount such that is non-zero; let be the same, for . Assume that is a Nash equilibrium.

Assume further that (if that's not the case, then just switch the labels and ). Then either £0.00 or £0.00 (and hence both players select £0.00).

We'll now rule out £0.00. If £0.00, then player can improve their score by replacing with . To see this, assume that player has said , and player has said . If , then player can say just as well as - either choice gives them the same amount (namely, £0.02).

There remain two other cases. If , then is superior to , getting (rather than £0.02). And if , then gets £0.02 £0.01, rather than (if ) or (if ).

Finally, if £0.00, then player gets -£0.02 unless they also say £0.00.

Hence if £0.00, the cannot be part of a Nash Equilibrium. Thus £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: . Each player can name or . Then if they both name the same, they get that amount of utility. If they name different ones, then then player naming gets , and the player naming gets .

By the same argument as above, the only Nash equilibrium is for both to name . The maximum possible amount is ; the maximum they can get if they both coordinate is , the Nash equilibrium is , and the worst option is . We can set and for arbitrarily tiny , while setting to be larger than 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."

7