Nash equilibriums can be arbitrarily bad

Go hun­gry with Al­most Free Lunches

Con­sider the fol­low­ing game, called “Al­most Free Lunches” (EDIT: this seems to be a var­i­ant of the trav­el­ler dilemma). You name any pound-and-pence amount be­tween £0 and £1,000,000; your op­po­nent does like­wise. Then you will both get whichever amount named was low­est.

On top of that, the per­son who named the high­est amount must give £0.02 to the other. If you tie, no ex­tra money changes hands.

What’s the Nash equil­ibrium of this game? Well:

  • The only Nash equil­ibrium of Al­most Free Lunches is for both of you to name £0.00.

Proof: Sup­pose player A has a prob­a­bil­ity dis­tri­bu­tion over pos­si­ble amounts to name, and player has a prob­a­bil­ity dis­tri­bu­tion over pos­si­ble amounts. Let be the high­est amount such that is non-zero; let be the same, for . As­sume that is a Nash equil­ibrium.

As­sume fur­ther that (if that’s not the case, then just switch the la­bels and ). Then ei­ther £0.00 or £0.00 (and hence both play­ers se­lect £0.00).

We’ll now rule out £0.00. If £0.00, then player can im­prove their score by re­plac­ing with . To see this, as­sume that player has said , and player has said . If , then player can say just as well as - ei­ther choice gives them the same amount (namely, £0.02).

There re­main two other cases. If , then is su­pe­rior to , get­ting (rather than £0.02). And if , then gets £0.02 £0.01, rather than (if ) or (if ).

Fi­nally, if £0.00, then player gets -£0.02 un­less they also say £0.00.

Hence if £0.00, the can­not be part of a Nash Equil­ibrium. Thus £0.00 and hence the only Nash Equil­ibrium is at both play­ers say­ing £0.00.

Pareto optimal

There are three Pareto-op­ti­mal out­comes: (£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 Equil­ibrium.

Min­max and maximin

The min­max and max­imin val­ues are also both ter­rible, and also equal to £0.00. This is not sur­pris­ing, though, as min­max and max­imin im­plic­itly as­sume the other play­ers are an­tag­o­nis­tic to you, and are try­ing to keep your prof­its low.

Ar­bi­trary bad­ness with two options

This shows that choos­ing the Nash Equil­ibrium can be worse than al­most ev­ery other op­tion. We can of course in­crease the max­i­mal amount, and get the Nash Equil­ibrium to be ar­bi­trar­ily worse than any rea­son­able solu­tion (I would just say ei­ther £1,000,000.00 or £999,999.99, and leave it at that).

But we can also make the Nash Equil­ibrium ar­bi­trar­ily close to the worst pos­si­ble out­come, and that with­out even re­quiring more than two op­tions for each player.

As­sume that there are four or­dered amounts of money/​util­ity: . Each player can name or . Then if they both name the same, they get that amount of util­ity. If they name differ­ent ones, then then player nam­ing gets , and the player nam­ing gets .

By the same ar­gu­ment as above, the only Nash equil­ibrium is for both to name . The max­i­mum pos­si­ble amount is ; the max­i­mum they can get if they both co­or­di­nate is , the Nash equil­ibrium is , and the worst op­tion is . We can set and for ar­bi­trar­ily tiny , while set­ting to be larger than by some ar­bi­trar­ily high amount.

So the situ­a­tion is as bad as it could pos­si­bly be.

Note that this is a var­i­ant of the pris­oner’s dilemma with differ­ent num­bers. You could de­scribe it as “Your com­pan­ion 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.”