Nash Equilibria and Schelling Points

A Nash equil­ibrium is an out­come in which nei­ther player is will­ing to unilat­er­ally change her strat­egy, and they are of­ten ap­plied to games in which both play­ers move si­mul­ta­neously and where de­ci­sion trees are less use­ful.

Sup­pose my girlfriend and I have both lost our cell phones and can­not con­tact each other. Both of us would re­ally like to spend more time at home with each other (util­ity 3). But both of us also have a slight prefer­ence in fa­vor of work­ing late and earn­ing some over­time (util­ity 2). If I go home and my girlfriend’s there and I can spend time with her, great. If I stay at work and make some money, that would be pretty okay too. But if I go home and my girlfriend’s not there and I have to sit around alone all night, that would be the worst pos­si­ble out­come (util­ity 1). Mean­while, my girlfriend has the same set of prefer­ences: she wants to spend time with me, she’d be okay with work­ing late, but she doesn’t want to sit at home alone.

This “game” has two Nash equil­ibria. If we both go home, nei­ther of us re­grets it: we can spend time with each other and we’ve both got our high­est util­ity. If we both stay at work, again, nei­ther of us re­grets it: since my girlfriend is at work, I am glad I stayed at work in­stead of go­ing home, and since I am at work, my girlfriend is glad she stayed at work in­stead of go­ing home. Although we both may wish that we had both gone home, nei­ther of us speci­fi­cally re­grets our own choice, given our knowl­edge of how the other acted.

When all play­ers in a game are rea­son­able, the (ap­par­ently) ra­tio­nal choice will be to go for a Nash equil­ibrium (why would you want to make a choice you’ll re­gret when you know what the other player chose?) And since John Nash (re­mem­ber that movie A Beau­tiful Mind?) proved that ev­ery game has at least one, all games be­tween well-in­formed ra­tio­nal­ists (who are not also be­ing su­per­ra­tional in a sense to be dis­cussed later) should end in one of these.

What if the game seems speci­fi­cally de­signed to thwart Nash equil­ibria? Sup­pose you are a gen­eral in­vad­ing an en­emy coun­try’s heart­land. You can at­tack one of two tar­gets, East City or West City (you de­clared war on them be­cause you were offended by their un­cre­ative to­ponyms). The en­emy gen­eral only has enough troops to defend one of the two cities. If you at­tack an un­defended city, you can cap­ture it eas­ily, but if you at­tack the city with the en­emy army, they will suc­cess­fully fight you off.

Here there is no Nash equil­ibrium with­out in­tro­duc­ing ran­dom­ness. If both you and your en­emy choose to go to East City, you will re­gret your choice—you should have gone to West and taken it un­defended. If you go to East and he goes to West, he will re­gret his choice—he should have gone East and stopped you in your tracks. Re­v­erse the names, and the same is true of the branches where you go to West City. So ev­ery op­tion has some­one re­gret­ting their choice, and there is no sim­ple Nash equil­ibrium. What do you do?

Here the an­swer should be ob­vi­ous: it doesn’t mat­ter. Flip a coin. If you flip a coin, and your op­po­nent flips a coin, nei­ther of you will re­gret your choice. Here we see a “mixed Nash equil­ibrium”, an equil­ibrium reached with the help of ran­dom­ness.

We can for­mal­ize this fur­ther. Sup­pose you are at­tack­ing a differ­ent coun­try with two new po­ten­tial tar­gets: Metropo­lis and Po­dunk. Metropo­lis is a rich and strate­gi­cally im­por­tant city (util­ity: 10); Po­dunk is an out of the way ham­let barely worth the trou­ble of cap­tur­ing it (util­ity: 1).

A so-called first-level player thinks: “Well, Metropo­lis is a bet­ter prize, so I might as well at­tack that one. That way, if I win I get 10 util­ity in­stead of 1”

A sec­ond-level player thinks: “Ob­vi­ously Metropo­lis is a bet­ter prize, so my en­emy ex­pects me to at­tack that one. So if I at­tack Po­dunk, he’ll never see it com­ing and I can take the city un­defended.”

A third-level player thinks: “Ob­vi­ously Metropo­lis is a bet­ter prize, so any­one clever would never do some­thing as ob­vi­ous as at­tack there. They’d at­tack Po­dunk in­stead. But my op­po­nent knows that, so, seek­ing to stay one step ahead of me, he has defended Po­dunk. He will never ex­pect me to at­tack Metropo­lis, be­cause that would be too ob­vi­ous. There­fore, the city will ac­tu­ally be un­defended, so I should take Metropo­lis.”

And so on ad in­fini­tum, un­til you be­come hope­lessly con­fused and have no choice but to spend years de­vel­op­ing a re­sis­tance to io­cane pow­der.

But sur­pris­ingly, there is a sin­gle best solu­tion to this prob­lem, even if you are play­ing against an op­po­nent who, like Pro­fes­sor Quir­rell, plays “one level higher than you.”

When the two cities were equally valuable, we solved our prob­lem by flip­ping a coin. That won’t be the best choice this time. Sup­pose we flipped a coin and at­tacked Metropo­lis when we got heads, and Po­dunk when we got tails. Since my op­po­nent can pre­dict my strat­egy, he would defend Metropo­lis ev­ery time; I am equally likely to at­tack Po­dunk and Metropo­lis, but tak­ing Metropo­lis would cost them much more util­ity. My to­tal ex­pected util­ity from flip­ping the coin is 0.5: half the time I suc­cess­fully take Po­dunk and gain 1 util­ity, and half the time I am defeated at Metropo­lis and gain 0.And this is not a Nash equil­ibrium: if I had known my op­po­nent’s strat­egy was to defend Metropo­lis ev­ery time, I would have skipped the coin flip and gone straight for Po­dunk.

So how can I find a Nash equil­ibrium? In a Nash equil­ibrium, I don’t re­gret my strat­egy when I learn my op­po­nent’s ac­tion. If I can come up with a strat­egy that pays ex­actly the same util­ity whether my op­po­nent defends Po­dunk or Metropo­lis, it will have this use­ful prop­erty. We’ll start by sup­pos­ing I am flip­ping a bi­ased coin that lands on Metropo­lis x per­cent of the time, and there­fore on Po­dunk (1-x) per­cent of the time. To be truly in­differ­ent which city my op­po­nent defends, 10x (the util­ity my strat­egy earns when my op­po­nent leaves Metropo­lis un­defended) should equal 1(1-x) (the util­ity my strat­egy earns when my op­po­nent leaves Po­dunk un­defended). Some quick alge­bra finds that 10x = 1(1-x) is satis­fied by x = 111. So I should at­tack Metropo­lis 111 of the time and Po­dunk 1011 of the time.

My op­po­nent, go­ing through a similar pro­cess, comes up with the sus­pi­ciously similar re­sult that he should defend Metropo­lis 1011 of the time, and Po­dunk 111 of the time.

If we both pur­sue our cho­sen strate­gies, I gain an av­er­age 0.9090… util­ity each round, soundly beat­ing my pre­vi­ous record of 0.5, and my op­po­nent sus­pi­ciously loses an av­er­age -.9090 util­ity. It turns out there is no other strat­egy I can use to con­sis­tently do bet­ter than this when my op­po­nent is play­ing op­ti­mally, and that even if I knew my op­po­nent’s strat­egy I would not be able to come up with a bet­ter strat­egy to beat it. It also turns out that there is no other strat­egy my op­po­nent can use to con­sis­tently do bet­ter than this if I am play­ing op­ti­mally, and that my op­po­nent, upon learn­ing my strat­egy, doesn’t re­gret his strat­egy ei­ther.

In The Art of Strat­egy, Dixit and Nale­buff cite a real-life ap­pli­ca­tion of the same prin­ci­ple in, of all things, penalty kicks in soc­cer. A right-footed kicker has a bet­ter chance of suc­cess if he kicks to the right, but a smart goalie can pre­dict that and will defend to the right; a player ex­pect­ing this can ac­cept a less spec­tac­u­lar kick to the left if he thinks the left will be un­defended, but a very smart goalie can pre­dict this too, and so on. Economist Ig­na­cio Pala­cios-Huerta la­bo­ri­ously an­a­lyzed the suc­cess rates of var­i­ous kick­ers and goalies on the field, and found that they ac­tu­ally pur­sued a mixed strat­egy gen­er­ally within 2% of the game the­o­retic ideal, prov­ing that peo­ple are pretty good at do­ing these kinds of calcu­la­tions un­con­sciously.

So ev­ery game re­ally does have at least one Nash equil­ibrium, even if it’s only a mixed strat­egy. But some games can have many, many more. Re­call the situ­a­tion be­tween me and my girlfriend:

There are two Nash equil­ibria: both of us work­ing late, and both of us go­ing home. If there were only one equil­ibrium, and we were both con­fi­dent in each other’s ra­tio­nal­ity, we could choose that one and there would be no fur­ther prob­lem. But in fact this game does pre­sent a prob­lem: in­tu­itively it seems like we might still make a mis­take and end up in differ­ent places.

Here we might be tempted to just leave it to chance; af­ter all, there’s a 50% prob­a­bil­ity we’ll both end up choos­ing the same ac­tivity. But other games might have thou­sands or mil­lions of pos­si­ble equil­ibria and so will re­quire a more re­fined ap­proach.

Art of Strat­egy de­scribes a game show in which two strangers were sep­a­rately taken to ran­dom places in New York and promised a prize if they could suc­cess­fully meet up; they had no com­mu­ni­ca­tion with one an­other and no clues about how such a meet­ing was to take place. Here there are a nearly in­finite num­ber of pos­si­ble choices: they could both meet at the cor­ner of First Street and First Av­enue at 1 PM, they could both meet at First Street and Se­cond Av­enue at 1:05 PM, etc. Since nei­ther party would re­gret their ac­tions (if I went to First and First at 1 and found you there, I would be thrilled) these are all Nash equil­ibria.

De­spite this mind-bog­gling ar­ray of pos­si­bil­ities, in fact all six epi­sodes of this par­tic­u­lar game ended with the two con­tes­tants meet­ing suc­cess­fully af­ter only a few days. The most pop­u­lar meet­ing site was the Em­pire State Build­ing at noon.

How did they do it? The world-fa­mous Em­pire State Build­ing is what game the­o­rists call fo­cal: it stands out as a nat­u­ral and ob­vi­ous tar­get for co­or­di­na­tion. Like­wise noon, clas­si­cally con­sid­ered the very mid­dle of the day, is a fo­cal point in time. Th­ese fo­cal points, also called Schel­ling points af­ter the­o­rist Thomas Schel­ling who dis­cov­ered them, provide an ob­vi­ous tar­get for co­or­di­na­tion at­tempts.

What makes a Schel­ling point? The most im­por­tant fac­tor is that it be spe­cial. The Em­pire State Build­ing, de­pend­ing on when the show took place, may have been the tallest build­ing in New York; noon is the only time that fits the crite­ria of “ex­actly in the mid­dle of the day”, ex­cept maybe mid­night when peo­ple would be ex­pected to be too sleepy to meet up prop­erly.

Of course, spe­cial­ness, like beauty, is in the eye of the be­holder. David Fried­man writes:

Two peo­ple are sep­a­rately con­fronted with the list of num­bers [2, 5, 9, 25, 69, 73, 82, 96, 100, 126, 150 ] and offered a re­ward if they in­de­pen­dently choose the same num­ber. If the two are math­e­mat­i­ci­ans, it is likely that they will both choose 2—the only even prime. Non-math­e­mat­i­ci­ans are likely to choose 100—a num­ber which seems, to the math­e­mat­i­ci­ans, no more unique than the other two ex­act squares. Illiter­ates might agree on 69, be­cause of its pe­cu­liar sym­me­try—as would, for a differ­ent rea­son, those whose in­ter­est in num­bers is more pruri­ent than math­e­mat­i­cal.

A re­cent open thread com­ment pointed out that you can jus­tify any­thing with “for de­ci­sion-the­o­retic rea­sons” or “due to meta-level con­cerns”. I humbly pro­pose adding “as a Schel­ling point” to this list, ex­cept that the list is tongue-in-cheek and Schel­ling points re­ally do ex­plain al­most ev­ery­thing—stock mar­kets, na­tional bor­ders, mar­riages, pri­vate prop­erty, re­li­gions, fash­ion, poli­ti­cal par­ties, peace treaties, so­cial net­works, soft­ware plat­forms and lan­guages all in­volve or are based upon Schel­ling points. In fact, when­ever some­thing has “sym­bolic value” a Schel­ling point is likely to be in­volved in some way. I hope to ex­pand on this point a bit more later.

Se­quen­tial games can in­clude one more method of choos­ing be­tween Nash equil­ibria: the idea of a sub­game-perfect equil­ibrium, a spe­cial kind of Nash equlibrium that re­mains a Nash equil­ibrium for ev­ery sub­game of the origi­nal game. In more in­tu­itive terms, this equil­ibrium means that even in a long mul­ti­ple-move game no one at any point makes a de­ci­sion that goes against their best in­ter­ests (re­mem­ber the ex­am­ple from the last post, where we crossed out the branches in which Clin­ton made im­plau­si­ble choices that failed to max­i­mize his util­ity?) Some games have mul­ti­ple Nash equil­ibria but only one sub­game-perfect one; we’ll ex­am­ine this idea fur­ther when we get to the iter­ated pris­on­ers’ dilemma and ul­ti­ma­tum game.

In con­clu­sion, ev­ery game has at least one Nash equil­ibrium, a point at which nei­ther player re­grets her strat­egy even when she knows the other player’s strat­egy. Some equil­ibria are sim­ple choices, oth­ers in­volve plans to make choices ran­domly ac­cord­ing to cer­tain crite­ria. Purely ra­tio­nal play­ers will always end up at a Nash equil­ibrium, but many games will have mul­ti­ple pos­si­ble equil­ibria. If play­ers are try­ing to co­or­di­nate, they may land at a Schel­ling point, an equil­ibria which stands out as spe­cial in some way.