Backward Reasoning Over Decision Trees

Game the­ory is the study of how ra­tio­nal ac­tors in­ter­act to pur­sue in­cen­tives. It starts with the same ques­tion­able premises as eco­nomics: that ev­ery­one be­haves ra­tio­nally, that ev­ery­one is purely self-in­ter­ested1, and that de­sires can be ex­actly quan­tified—and uses them to in­ves­ti­gate situ­a­tions of con­flict and co­op­er­a­tion.

Here we will be­gin with some fairly ob­vi­ous points about de­ci­sion trees, but by the end we will have the tools nec­es­sary to ex­plain a some­what sur­pris­ing find­ing: that giv­ing a US pres­i­dent the ad­di­tional power of line-item veto may in many cases make the pres­i­dent less able to en­act her poli­cies. Start­ing at the be­gin­ning:

The ba­sic unit of game the­ory is the choice. Ra­tional agents make choices in or­der to max­i­mize their util­ity, which is sort of like a mea­sure of how happy they are. In a one-per­son game, your choices af­fect your­self and maybe the nat­u­ral en­vi­ron­ment, but no­body else. Th­ese are pretty sim­ple to deal with:

Here we vi­su­al­ize a choice as a branch­ing tree. At each branch, we choose the op­tion with higher util­ity; in this case, go­ing to the beach. Since each out­come leads to new choices, some­times the de­ci­sion trees can be longer than this:

Here’s a slightly more difficult de­ci­sion, de­nom­i­nated in money in­stead of util­ity. If you want to make as much money as pos­si­ble, then your first choice—go­ing to col­lege or start­ing a min­i­mum wage job right Now—seems to fa­vor the more lu­cra­tive min­i­mum wage job. But when you take Later into ac­count, col­lege opens up more lu­cra­tive fu­ture choices, as mea­sured in the gray to­tals on the right-hand side. This illus­trates the im­por­tant prin­ci­ple of rea­son­ing back­ward over de­ci­sion trees. If you rea­son for­ward, tak­ing the best op­tion on the first choice and so on, you end up as a low-level man­ager. To get the real cash, you’ve got to start at the end—the to­tal on the right—and then ex­am­ine what choice at each branch will take you there.

This is all about as ob­vi­ous as, well, not hit­ting your­self on the head with a ham­mer, so let’s move on to where it re­ally gets in­ter­est­ing: two-player games.

I’m play­ing White, and it’s my move. For sim­plic­ity I con­sider only two op­tions: queen takes knight and queen takes rook. The one chess book I’ve read val­ues pieces in num­ber of pawns: a knight is worth three pawns, a rook five, a queen nine. So at first glance, it looks like my best move is to take Black’s rook. As for Black, I have ar­bi­trar­ily sin­gled out pawn takes pawn as her preferred move in the cur­rent po­si­tion, but if I play queen takes rook, a new op­tion opens up for her: bishop takes queen. Let’s look at the de­ci­sion tree:

If I fool­ishly play this two player game the same way I played the one-player go-to-col­lege game, I note that the mid­dle branch has the high­est util­ity for White, so I take the choice that leads there: cap­ture the rook. And then Black plays bishop takes queen, and I am left wailing and gnash­ing my teeth. What did I do wrong?

I should start by as­sum­ing Black will, when­ever pre­sented with a choice, take the op­tion with the high­est Black util­ity. Un­less Black is stupid, I can cross out any branch that re­quires Black to play against her own in­ter­ests. So now the tree looks like this:

The two re­al­is­tic op­tions are me play­ing queen takes rook and end­ing up with­out a queen and −4 util­ity, or me play­ing queen takes knight and end­ing up with a mod­est gain of 2 util­ity.

(my apolo­gies if I’ve missed some ob­vi­ous strate­gic pos­si­bil­ity on this par­tic­u­lar chess­board; I’m not so good at chess but hope­fully the point of the ex­am­ple is clear.)

This method of al­ter­nat­ing moves in a branch­ing tree matches both our in­tu­itive thought pro­cesses dur­ing a chess game (“Okay, if I do this, then Black’s go­ing to do this, and then I’d do this, and then...”) and the foun­da­tion of some of the al­gorithms chess com­put­ers like Deep Blue use. In fact, it may seem pretty ob­vi­ous, or even un­nec­es­sary. But it can be used to an­a­lyze some more com­pli­cated games with coun­ter­in­tu­itive re­sults.

Art of Strat­egy de­scribes a de­bate from 1990s US poli­tics re­volv­ing around so-called “line-item veto” power, the abil­ity to veto only one part of a bill. For ex­am­ple, if Congress passed a bill declar­ing March to be Na­tional Game The­ory Month and April to be Na­tional Branch­ing Tree Aware­ness Month, the Pres­i­dent could veto only the part about April and leave March in­tact (as poli­tics cur­rently works, the Pres­i­dent could only veto or ac­cept the whole bill). Dur­ing the ’90s, Pres­i­dent Clin­ton fought pretty hard for this power, which seems rea­son­able as it ex­pands his op­tions when deal­ing with the hos­tile Repub­li­can Congress.

But Dixit and Nale­buff ex­plain that gain­ing line-item veto pow­ers might hurt a Pres­i­dent. How? Branch­ing trees can ex­plain.

Imag­ine Clin­ton and the Repub­li­can Congress are fight­ing over a bud­get. We can think of this as a game of se­quen­tial moves, much like chess. On its turn, Congress pro­poses a bud­get. On Clin­ton’s turn, he ei­ther ac­cepts or re­jects the bud­get. A player “wins” if the bud­get con­tains their pet pro­jects. In this game, we start with low do­mes­tic and mil­i­tary bud­gets. Clin­ton re­ally wants to raise do­mes­tic spend­ing (util­ity +10), and has a minor dis­taste for raised mil­i­tary spend­ing (util­ity −5). Congress re­ally wants to raise mil­i­tary spend­ing (util­ity +10), but has a minor dis­taste for raised do­mes­tic spend­ing (util­ity −5). The sta­tus quo is zero util­ity for both par­ties; if nei­ther party can come to an agree­ment, vot­ers get an­gry at them and they both lose 2 util­ity. Here’s the tree when Clin­ton lacks line-item veto:

For any par­tic­u­lar Repub­li­can choice, Clin­ton will never re­spond in a way that does not max­i­mize his util­ity, so the the Repub­li­cans rea­son back­ward and ar­rive at some­thing like this:

If Repub­li­cans are perfectly ra­tio­nal agents, they choose the sec­ond op­tion, high do­mes­tic and high mil­i­tary spend­ing, to give them their high­est plau­si­bly ob­tain­able util­ity of 5.

But what if Clin­ton has the line-item veto? Now his op­tions look like this:

If the Repub­li­cans stick to their pre­vi­ous choice of “high do­mes­tic and high mil­i­tary spend­ing”, Clin­ton line-item ve­toes the mil­i­tary spend­ing, and we end up with a situ­a­tion iden­ti­cal to the first choice: Clin­ton sit­ting on a pile of util­ity, and the Repub­li­cans wailing and gnash­ing their teeth. The Repub­li­cans need to come up with a new strat­egy, and their thought pro­cesses, based on Clin­ton as a util­ity-max­i­mizer, look like this:

Here Congress’s high­est util­ity choice is to pro­pose low do­mes­tic spend­ing (it doesn’t mat­ter if they give more money to the mil­i­tary or not as this will get line-item ve­toed). Let’s say they pro­pose low do­mes­tic and low mil­i­tary spend­ing, and Clin­ton ac­cepts. The util­ities are (0, 0), and now there is much wailing and gnash­ing of teeth on both sides (game the­o­rists call this a gnash equil­ibrium. Maybe you’ve heard of it.)

But now Clin­ton has a util­ity of 0, in­stead of a util­ity of 5. Giv­ing him ex­tra op­tions has cost him util­ity! Why should this hap­pen, and shouldn’t he be able to avoid it?

This hap­pened be­cause Clin­ton’s new abil­ities af­fect not only his own choices, but those of his op­po­nents (com­pare Schel­ling: Strate­gies of Con­flict). He may be able to deal with this if he can make the Repub­li­cans trust him.

In sum­mary, sim­ple se­quen­tial games can of­ten be ex­plored by rea­son­ing back­wards over de­ci­sion trees rep­re­sent­ing the choices of the play­ers in­volved. The next post will dis­cuss si­mul­ta­neous games and the con­cept of a Nash equil­ibrium.


1: Game the­ory re­quires self-in­ter­est in that all play­ers’ are driven solely by their de­sire to max­i­mize their own pay­off in the game cur­rently be­ing played with­out re­gard to the welfare of other play­ers or any ex­ter­nal stan­dard of fair­ness. How­ever, it can also be used to de­scribe the be­hav­ior of al­tru­is­tic agents so long as their al­tru­is­tic con­cerns are rep­re­sented in the eval­u­a­tion of their pay­off.