Game Theory As A Dark Art

One of the most charm­ing fea­tures of game the­ory is the al­most limitless depths of evil to which it can sink.

Your gar­den-va­ri­ety evils act against your val­ues. Your bet­ter class of evil, like Volde­mort and the folk-tale ver­sion of Satan, use your greed to trick you into act­ing against your own val­ues, then grab away the promised re­ward at the last mo­ment. But even demons and dark wiz­ards can only do this once or twice be­fore most vic­tims wise up and de­cide that tak­ing their ad­vice is a bad idea. Game the­ory can force you to be­tray your deep­est prin­ci­ples for no last­ing benefit again and again, and still leave you con­vinced that your be­hav­ior was ra­tio­nal.

Some of the ex­am­ples in this post prob­a­bly wouldn’t work in re­al­ity; they’re more of a re­duc­tio ad ab­sur­dum of the so-called homo eco­nomi­cus who acts free from any feel­ings of al­tru­ism or trust. But oth­ers are lifted di­rectly from real life where seem­ingly in­tel­li­gent peo­ple gen­uinely fall for them. And even the ones that don’t work with real peo­ple might be valuable in mod­el­ing in­sti­tu­tions or gov­ern­ments.

Of the fol­low­ing ex­am­ples, the first three are from The Art of Strat­egy; the sec­ond three are rel­a­tively clas­sic prob­lems taken from around the In­ter­net. A few have been men­tioned in the com­ments here already and are re­posted for peo­ple who didn’t catch them the first time.

The Evil Plu­to­crat

You are an evil plu­to­crat who wants to get your pet bill—let’s say a law that makes evil plu­to­crats tax-ex­empt—through the US Congress. Your usual strat­egy would be to bribe the Con­gress­men in­volved, but that would be pretty costly—Con­gress­men no longer come cheap. As­sume all Con­gress­men act in their own fi­nan­cial self-in­ter­est, but that ab­sent any fi­nan­cial self-in­ter­est they will grudg­ingly de­fault to hon­estly rep­re­sent­ing their con­stituents, who hate your bill (and you per­son­ally). Is there any way to en­sure Congress passes your bill, with­out spend­ing any money on bribes at all?

Yes. Sim­ply tell all Con­gress­men that if your bill fails, you will donate some stu­pen­dous amount of money to whichever party gave the great­est per­cent of their votes in fa­vor.

Sup­pose the Democrats try to co­or­di­nate among them­selves. They say “If we all op­pose the bill, then if even one Repub­li­can sup­ports the bill, the Repub­li­cans will get lots of money they can spend on cam­paign­ing against us. If only one of us sup­ports the bill, the Repub­li­cans may an­ti­ci­pate this strat­egy and two of them may sup­port it. The only way to en­sure the Repub­li­cans don’t gain a mas­sive wind­fall and wipe the floor with us next elec­tion is for most of us to vote for the bill.”

Mean­while, in their meet­ing, the Repub­li­cans think the same thing. The vote ends with most mem­bers of Congress sup­port­ing your bill, and you don’t end up hav­ing to pay any money at all.

The Hos­tile Takeover

You are a ruth­less busi­ness­man who wants to take over a com­peti­tor. The com­peti­tor’s stock costs $100 a share, and there are 1000 shares, dis­tributed among a hun­dred in­vestors who each own ten. That means the com­pany ought to cost $100,000, but you don’t have $100,000. You only have $98,000. Worse, an­other com­peti­tor with $101,000 has made an offer for greater than the value of the com­pany: they will pay $101 per share if they end up get­ting all of the shares. Can you still man­age to take over the com­pany?

Yes. You can make what is called a two-tiered offer. Sup­pose all in­vestors get a chance to sell shares si­mul­ta­neously. You will pay $105 for 500 shares—bet­ter than they could get from your com­peti­tor—but only pay $90 for the other 500. If you get fewer than 500 shares, all will sell for $105; if you get more than 500, you will start by dis­tribut­ing the $105 shares evenly among all in­vestors who sold to you, and then dis­tribute out as many of the $90 shares as nec­es­sary (leav­ing some $90 shares be­hind ex­cept when all in­vestors sell to you) . And you will do this whether or not you suc­ceed in tak­ing over the com­pany—if only one per­son sells you her share, then that one per­son gets $105.

Sup­pose an in­vestor be­lieves you’re not go­ing to suc­ceed in tak­ing over the com­pany. That means you’re not go­ing to get over 50% of shares. That means the offer to buy 500 shares for $105 will still be open. That means the in­vestor can ei­ther sell her share to you (for $105) or to your com­peti­tor (for $101). Clearly, it’s in this in­vestor’s self-in­ter­est to sell to you.

Sup­pose the in­vestor be­lieves you will suc­ceed in tak­ing over the com­pany. That means your com­peti­tor will not take over the com­pany, and its $101 offer will not ap­ply. That means that the new value of the shares will be $90, the offer you’ve made for the sec­ond half of shares. So they will get $90 if they don’t sell to you. How much will they get if they do sell to you? They can ex­pect half of their ten shares to go for $105 and half to go for $90; they will get a to­tal of $97.50 per share. $97.50 is bet­ter than $90, so their in­cen­tive is to sell to you.

Sup­pose the in­vestor be­lieves you are right on the cusp of tak­ing over the com­pany, and her de­ci­sion will de­ter­mine the out­come. In that case, you have at most 499 shares. When the in­vestor gives you her 10 shares, you will end up with 509 − 500 of which are $105 shares and 9 of which are $90 shares. If these are dis­tributed ran­domly, in­vestors can ex­pect to make on av­er­age $104.73 per share, com­pared to $101 if your com­peti­tor buys the com­pany.

Since all in­vestors are think­ing along these lines, they all choose to buy shares from you in­stead of your com­peti­tor. You pay out an av­er­age of $97.50 per share, and take over the com­pany for $97,500, leav­ing $500 to spend on the vic­tory party.

The stock­hold­ers, mean­while, are left won­der­ing why they just all sold shares for $97.50 when there was some­one else who was promis­ing them $101.

The Hos­tile Takeover, Part II

Your next tar­get is a small fam­ily-owned cor­po­ra­tion that has in­sti­tuted what they con­sider to be in­vin­cible pro­tec­tion against hos­tile takeovers. All de­ci­sions are made by the Board of Direc­tors, who serve for life. Although share­hold­ers vote in the new mem­bers of the Board af­ter one of them dies or re­tires, Board mem­bers can hang on for decades. And all de­ci­sions about the Board, im­peach­ment of its mem­bers, and en­force­ment of its by­laws are made by the Board it­self, with mem­bers vot­ing from newest to most se­nior.

So you go about buy­ing up 51% of the stock in the com­pany, and sure enough, a Board mem­ber re­tires and is re­placed by one of your lack­eys. This lackey can pro­pose pro­ce­du­ral changes to the Board, but they have to be ap­proved by ma­jor­ity vote. And at the mo­ment the other four di­rec­tors hate you with a vengeance, and any­thing you pro­pose is likely to be defeated 4-1. You need those other four wind­bags out of there, and soon, but they’re all young and healthy and un­likely to re­tire of their own ac­cord.

The ob­vi­ous next step is to start look­ing for a good as­sas­sin. But if you can’t find one, is there any way you can pro­pose mass forced re­tire­ment to the Board and get them to ap­prove it by ma­jor­ity vote? Even bet­ter, is there any way you can get them to ap­prove it unan­i­mously, as a big “f#@& you” to who­ever made up this stupid sys­tem?

Yes. Your lackey pro­poses as fol­lows: “I move that we vote upon the fol­low­ing: that if this mo­tion passes unan­i­mously, all mem­bers of the of the Board re­sign im­me­di­ately and are given a rea­son­able com­pen­sa­tion; that if this mo­tion passes 4-1 that the Direc­tor who voted against it must re­tire with­out com­pen­sa­tion, and the four di­rec­tors who voted in fa­vor may stay on the Board; and that if the mo­tion passes 3-2, then the two ‘no’ vot­ers get no com­pen­sa­tion and the three ‘yes’ vot­ers may re­main on the board and will also get a spec­tac­u­lar prize—to wit, our com­pany’s 51% share in your com­pany di­vided up evenly among them.”

Your lackey then votes “yes”. The sec­ond newest di­rec­tor uses back­ward rea­son­ing as fol­lows:

Sup­pose that the vote were tied 2-2. The most se­nior di­rec­tor would pre­fer to vote “yes”, be­cause then she gets to stay on the Board and gets a bunch of free stocks.

But know­ing that, the sec­ond most se­nior di­rec­tor (SMSD) will also vote ‘yes’. After all, when the is­sue reaches the SMSD, there will be one of the fol­low­ing cases:

1. If there is only one yes vote (your lackey’s), the SMSD stands to gain from vot­ing yes, know­ing that will pro­duce a 2-2 tie and make the most se­nior di­rec­tor vote yes to get her spec­tac­u­lar com­pen­sa­tion. This means the mo­tion will pass 3-2, and the SMSD will also re­main on the board and get spec­tac­u­lar com­pen­sa­tion if she votes yes, com­pared to a best case sce­nario of re­main­ing on the board if she votes no.

2. If there are two yes votes, the SMSD must vote yes—oth­er­wise, it will go 2-2 to the most se­nior di­rec­tor, who will vote yes, the mo­tion will pass 3-2, and the SMSD will be forced to re­tire with­out com­pen­sa­tion.

3. And if there are three yes votes, then the mo­tion has already passed, and in all cases where the sec­ond most se­nior di­rec­tor votes “no”, she is forced to re­tire with­out com­pen­sa­tion. There­fore, the sec­ond most se­nior di­rec­tor will always vote “yes”.

Since your lackey, the most se­nior di­rec­tor, and the sec­ond most se­nior di­rec­tor will always vote “yes”, we can see that the other two di­rec­tors, know­ing the mo­tion will pass, must vote “yes” as well in or­der to get any com­pen­sa­tion at all. There­fore, the mo­tion passes unan­i­mously and you take over the com­pany at min­i­mal cost.

The Dol­lar Auc­tion

You are an eco­nomics pro­fes­sor who for­got to go to the ATM be­fore leav­ing for work, and who has only $20 in your pocket. You have a lunch meet­ing at a very ex­pen­sive French restau­rant, but you’re stuck teach­ing classes un­til lunchtime and have no way to get money. Can you trick your stu­dents into giv­ing you enough money for lunch in ex­change for your $20, with­out ly­ing to them in any way?

Yes. You can use what’s called an all-pay auc­tion, in which sev­eral peo­ple bid for an item, as in a tra­di­tional auc­tion, but ev­ery­one pays their bid re­gard­less of whether they win or lose (in a com­mon var­i­ant, only the top two bid­ders pay their bids).

Sup­pose one stu­dent, Alice, bids $1. This seems rea­son­able—pay­ing $1 to win $20 is a pretty good deal. A sec­ond stu­dent, Bob, bids $2. Still a good deal if you can get a twenty for a tenth that amount.

The bid­ding keeps go­ing higher, spurred on by the knowl­edge that get­ting a $20 for a bid of less than $20 would be pretty cool. At some point, maybe Alice has bid $18 and Bob has bid $19.

Alice thinks: “What if I raise my bid to $20? Then cer­tainly I would win, since Bob would not pay more than $20 to get $20, but I would only break even. How­ever, break­ing even is bet­ter than what I’m do­ing now, since if I stay where I am Bob wins the auc­tion and I pay $18 with­out get­ting any­thing.” There­fore Alice bids $20.

Bob thinks “Well, it sounds pretty silly to bid $21 for a twenty dol­lar bill. But if I do that and win, I only lose a dol­lar, as op­posed to bow­ing out now and los­ing my $19 bid.” So Bob bids $21.

Alice thinks “If I give up now, I’ll lose a whole dol­lar. I know it seems stupid to keep go­ing, but surely Bob has the same in­tu­ition and he’ll give up soon. So I’ll bid $22 and just lose two dol­lars...”

It’s easy to see that the bid­ding could in the­ory go up with no limits but the play­ers’ funds, but in prac­tice it rarely goes above $200.

...yes, $200. Economist Max Baz­er­man claims that of about 180 such auc­tions, seven have made him more than $100 (ie $50 from both play­ers) and his high­est take was $407 (ie over $200 from both play­ers).

In any case, you’re prob­a­bly set for lunch. If you’re not, take an­other $20 from your earn­ings and try again un­til you are—the auc­tion gains even more money from peo­ple who have seen it be­fore than it does from naive bid­ders (!) Baz­er­man, for his part, says he’s made a to­tal of $17,000 from the ex­er­cise.

At that point you’re start­ing to won­der why no one has tried to build a cor­po­ra­tion around this, and un­sur­pris­ingly, the on­line auc­tion site Swoopo ap­pears to be ex­actly that. More sur­pris­ingly, they seem to have gone bankrupt last year, sug­gest­ing that maybe H.L. Mencken was wrong and some­one has gone broke un­der­es­ti­mat­ing peo­ple’s in­tel­li­gence.

The Bloodthirsty Pirates

You are a pirate cap­tain who has just stolen $17,000, de­nom­i­nated en­tirely in $20 bills, from a very smug-look­ing game the­o­rist. By the Pirate Code, you as the cap­tain may choose how the trea­sure gets dis­tributed among your men. But your first mate, sec­ond mate, third mate, and fourth mate all want a share of the trea­sure, and de­mand on threat of mutiny the right to ap­prove or re­ject any dis­tri­bu­tion you choose.You ex­pect they’ll re­ject any­thing too lop­sided in your fa­vor, which is too bad, be­cause that was to­tally what you were plan­ning on.

You re­mem­ber one fact that might help you—your crew, be­ing bloodthirsty pirates, all hate each other and ac­tively want one an­other dead. Un­for­tu­nately, their greed seems to have over­come their blood­lust for the mo­ment, and as long as there are ad­van­tages to co­or­di­nat­ing with one an­other, you won’t be able to turn them against their fel­low sailors. Dou­bly un­for­tu­nately, they also ac­tively want you dead.

You think quick. “Aye,” you tell your men with a scowl that could turn blood to ice, “ye can have yer votin’ sys­tem, ye scurvy dogs” (you’re that kind of pirate). “But here’s the rules: I pro­pose a dis­tri­bu­tion. Then you all vote on whether or not to take it. If a ma­jor­ity of you, or even half of you, vote ‘yes’, then that’s how we dis­tribute the trea­sure. But if you vote ‘no’, then I walk the plank to pun­ish me for my pre­sump­tion, and the first mate is the new cap­tain. He pro­poses a new dis­tri­bu­tion, and again you vote on it, and if you ac­cept then that’s fi­nal, and if you re­ject it he walks the plank and the sec­ond mate be­comes the new cap­tain. And so on.”

Your four mates agree to this pro­posal. What dis­tri­bu­tion should you pro­pose? Will it be enough to en­sure your com­fortable re­tire­ment in Ja­maica full of rum and wenches?

Yes. Sur­pris­ingly, you can get away with propos­ing that you get $16,960, your first mate gets noth­ing, your sec­ond mate gets $20, your third mate gets noth­ing, and your fourth mate gets $20 - and you will still win 3 −2.

The fourth mate uses back­ward rea­son­ing like so: Sup­pose there were only two pirates left, me and the third mate. The third mate wouldn’t have to promise me any­thing, be­cause if he pro­posed all $17,000 for him­self and none for me, the vote would be 1-1 and ac­cord­ing to the origi­nal rules a tie passes. There­fore this is a bet­ter deal than I would get if it were just me and the third mate.

But sup­pose there were three pirates left, me, the third mate, and the sec­ond mate. Then the sec­ond mate would be the new cap­tain, and he could pro­pose $16,980 for him­self, $0 for the third mate, and $20 for me. If I vote no, then it re­duces to the pre­vi­ous case in which I get noth­ing. There­fore, I should vote yes and get $20. There­fore, the fi­nal vote is 2-1 in fa­vor.

But sup­pose there were four pirates left: me, the third mate, the sec­ond mate, and the first mate. Then the first mate would be the new cap­tain, and he could pro­pose $16,980 for him­self, $20 for the third mate, $0 for the sec­ond mate, and $0 for me. The third mate knows that if he votes no, this re­duces to the pre­vi­ous case, in which he gets noth­ing. There­fore, he should vote yes and get $20. There­fore, the fi­nal vote is 2-2, and ties pass.

(He might also pro­pose $16980 for him­self, $0 for the sec­ond mate, $0 for the third mate, and $20 for me. But since he knows I am a bloodthirsty pirate who all else be­ing equal wants him dead, I would vote no since I could get a similar deal from the third mate and make the first mate walk the plank in the bar­gain. There­fore, he would offer the $20 to the third mate.)

But in fact there are five pirates left: me, the third mate, the sec­ond mate, the first mate, and the cap­tain. The cap­tain has pro­posed $16,960 for him­self, $20 for the sec­ond mate, and $20 for me. If I vote no, this re­duces to the pre­vi­ous case, in which I get noth­ing. There­fore, I should vote yes and get $20.

(The cap­tain would avoid giv­ing the $20s to the third and fourth rather than to the sec­ond and fourth mates for a similar rea­son to the one given in the pre­vi­ous ex­am­ple—all else be­ing equal, the pirates would pre­fer to watch him die.)

The sec­ond mate thinks along the same lines and re­al­izes that if he votes no, this re­duces to the case with the first mate, in which the sec­ond mate also gets noth­ing. There­fore, he too votes yes.

Since you, as the cap­tain, ob­vi­ously vote yes as well, the dis­tri­bu­tion passes 3-2. You end up with $16,980, and your crew, who were so cer­tain of their abil­ity to threaten you into shar­ing the trea­sure, each end up with ei­ther a sin­gle $20 or noth­ing.

The Pri­son­ers’ Dilemma, Re­dux

This se­quence pre­vi­ously men­tioned the pop­u­lar­ity of Pri­son­ers’ Dilem­mas as gim­micks on TV game shows. In one pro­gram, Golden Balls, con­tes­tants do var­i­ous tasks that add money to a cen­tral “pot”. By the end of the game, only two con­tes­tants are left, and are offered a Pri­son­ers’ Dilemma situ­a­tion to split the pot be­tween them. If both play­ers choose to “Split”, the pot is di­vided 50-50. If one player “Splits” and the other player “Steals”, the stealer gets the en­tire pot. If both play­ers choose to “Steal”, then no one gets any­thing. The two play­ers are al­lowed to talk to each other be­fore mak­ing a de­ci­sion, but like all Pri­soner’s Dilem­mas, the fi­nal choice is made si­mul­ta­neously and in se­cret.

You are a con­tes­tant on this show. You are ac­tu­ally not all that evil—you would pre­fer to split the pot rather than to steal all of it for your­self—but you cer­tainly don’t want to trust the other guy to have the same prefer­ence. In fact, the other guy looks a bit greedy. You would pre­fer to be able to rely on the other guy’s ra­tio­nal self-in­ter­est rather than on his al­tru­ism. Is there any tac­tic you can use be­fore the choice, when you’re al­lowed to com­mu­ni­cate freely, in or­der to make it ra­tio­nal for him to co­op­er­ate?

Yes. In one epi­sode of Golden Balls, a player named Nick suc­cess­fully meta-games the game by trans­form­ing it from the Pri­soner’s Dilemma (where defec­tion is ra­tio­nal) to the Ul­ti­ma­tum Game (where co­op­er­a­tion is ra­tio­nal)

Nick tells his op­po­nent: “I am go­ing to choose ‘Steal’ on this round.” (He then im­me­di­ately pressed his but­ton; al­though the show hid which but­ton he pressed, he only needed to demon­strate that he had com­mit­ted and his mind could no longer be changed) “If you also choose ‘Steal’, then for cer­tain nei­ther of us gets any money. If you choose ‘Split’, then I get all the money, but im­me­di­ately af­ter the game, I will give you half of it. You may not trust me on this, and that’s un­der­stand­able, but think it through. First, there’s no less rea­son to think I’m trust­wor­thy than if I had just told you I pressed ‘Split’ to be­gin with, the way ev­ery­one else on this show does. And sec­ond, now if there’s any chance what­so­ever that I’m trust­wor­thy, then that’s some chance of get­ting the money—as op­posed to the zero chance you have of get­ting the money if you choose ‘Steal’.”

Nick’s eval­u­a­tion is cor­rect. His op­po­nent can ei­ther press ‘Steal’, with a cer­tainty of get­ting zero, or press ‘Split’, with a nonzero prob­a­bil­ity of get­ting his half of the pot de­pend­ing on Nick’s trust­wor­thi­ness.

But this solu­tion is not quite perfect, in that one can imag­ine Nick’s op­po­nent be­ing very con­vinced that Nick will cheat him, and de­cid­ing he val­ues pun­ish­ing this defec­tion more than the tiny chance that Nick will play fair. That’s why I was so im­pressed to see cousin_it pro­pose what I think is an even bet­ter solu­tion on the Less Wrong thread on the mat­ter:

This game has mul­ti­ple Nash equil­ibria and cheap talk is al­lowed, so cor­re­lated equil­ibria are pos­si­ble. Here’s how you im­ple­ment a cor­re­lated equil­ibrium if your op­po­nent is smart enough:

”We have two min­utes to talk, right? I’m go­ing to ask you to flip a coin (visi­bly to both of us) at the last pos­si­ble mo­ment, the ex­act sec­ond where we must cease talk­ing. If the coin comes up heads, I promise I’ll co­op­er­ate, you can just go ahead and claim the whole prize. If the coin comes up tails, I promise I’ll defect. Please co­op­er­ate in this case, be­cause you have noth­ing to gain by defect­ing, and any­way the ar­range­ment is fair, isn’t it?”

This sort of clever think­ing is, in my opinion, the best that game the­ory has to offer. It shows that game the­ory need not be only a tool of evil for clas­si­cal figures of villainy like bloodthirsty pirate cap­tains or cor­po­rate raiders or economists, but can also be used to cre­ate trust and en­sure co­op­er­a­tion be­tween par­ties with com­mon in­ter­ests.