Linear Programming Notes IX:Two-Person Zero-Sum Game Theory1 IntroductionEconomists use the word rational in a narrow way. To an economist, a rationalactor is someone who makes decisions that maximize her (or his) preferencessubject to constraints imposed by the environment. So, this actor knows herpreferences and knows how to go about optimizing. It is a powerful approach,but it probably is only distantly related to what you mean when you think ofyourself as rational.Decision theory describes the behavior of a rational actor when her actionsdo not influence the behavior of the people around her. Game theory describesthe behavior of a rational actor in a strategic situation. Here decisions of otheractors determine how well you do. Deciding where to go to dinner can bethought of as a decision problem if all you care about is what you eat and whereyou eat it. It is a strategic problem if you also want to mee t a friend at therestaurant. (In the first case, you go to the restaurant that serves the foo d youlike best. In the second case, the restaurant that you prefer depends not onlyon the food served, but also on the where your friend goes.)2 Zero-Sum GamesThese notes describe a simple class of games called two-player zero-sum games.You can probably figure out what a two-player game is. Zero-sum games referto games of pure c onflict. The payoff of one player is the negative of the payoffof the other player. This formulation is probably appropriate for most parlorgames, where the outcomes are either win, lose, or draw (and there is at mostone winner or loser). Maybe it describes war. It is a restrictive assumptionand is not appropriate to most economic applications, where there is a strongcomponent of common interes ts mixed with the conflict. For example, in abargaining situation, the conflict is clear: the buyer wants to pay a low priceand the seller wants to receive a high price. The cooperative eleme nt arisesbecause it is frequently the case that making a transaction at an intermediateprice is better for both sides than a failure to reach an agreement. Concretely,if something is worth $10 to the seller and $15 to the (potential) buyer, thenmaking a sale at the price $12 (or any price between $10 and $15) is better forboth buyer and seller than making no sale at all. Problems that describe aspectsof firm competition (models of Cournot duopoly that you may have seen in amicro class) have non-zero sum aspects.Why limit attention to zero-sum games? They are simpler. There is abeautiful theory that is more compelling than the general theory of games.Predicting outcomes in these games uses linear programming in ways that do1not generalize to other kinds of game.The general structure of a game involves a list of players; a set of strategiesfor each of the players; a payoff for each vector of strategies. I will assume thatthe game has only two players.3 StrategiesThe intuition behind a strategy is that it tells you how you are going to play thegame. In examples, it will be just a choice from one of a finite list of possiblethings you can do.This story might help you understand the notion of a strategy. You madean arrangement to talk to a friend about what you were going to do together,but you unexpectedly cannot be home when the friend is supposed to call. Yourroommate will be home and promises to talk to your friend. You want to giveyour roommate instructions about what kind of arrangements to make. Youwould like to walk on the beach, but not if it is going to rain. You would liketo go to the Belly Up, but only if you can dance. You would like to see amovie, but only if Leonardo DiCaprio isn’t in it. Most of all, you would liketo do something that your friend also wants to do. What kind of instructionsdo you give your roommate? Complete instructions will account for all possiblecontingencies. You won’t say: “Tell my friend that I’ll do whatever he or shewants to do.” Instead, you’ll say something like: “If she wants to go to a movie,find out if DiCaprio is in it. If he isn’t, tell her OK. If he is, tell her no.” Andso on. In game theory, a strategy is a complete set of instructions. It allowsyour roommate to “negotiate” for you no matter what your friend on the phonesays.When you specify a strategy for each player, you determine the outcomeof the game. Payoffs associate to each outcome a number for each player. Youcan therefore describe two-player games using a payoff matrix. The rows ofthe matrix represent the strategies of one player. The columns of the matrixrepresent the strategies of the other player. The cells of the matrix representoutcomes. In these cells, you place payoff numbers. In general, each cell shouldhave a payoff for each player in it. In zero-sum games, you need only have onenumber in each cell. T his number represents the payoff to the player who picksrows. The negative of this number is the payoff to the player who picks columns.Take the game of matching pennies. Two players simultaneously place apenny on the table. If the pennies ‘match’ (both heads up or both heads down),then the Row player wins the Column player’s penny. If the pennies do not‘match’ (exactly one head), then the Column player wins the Row player’spenny. The payoff matrix is below.Heads TailsHeads 1 -1Tails -1 12In matching pennies, each player has two strategies. The player can eitherplay heads or play tails. Now consider a variant of matching pennies that I playwith my son. First, I decide whether to play heads or tails. Next, he looks atwhat I did. Finally, he decides whether to play heads or tails. I win if the coinsmatch. He wins if they do not. In this game, both players must decide whetherto play heads or tails. So you might think that we both have two strategies.This is not correct. I have two strategies, but my son can make his decisionbased on what I did. He therefore has four strategies:HH: Play heads no matter what I do.T T : Play tails no matter what I do.HT : Play heads if I play heads and tails if I play tails (match).T H: Play tails if I play heads and heads if I play tails (mismatch).Therefore the payoff matrix for this version of matching pennies is:HH TT HT THHeads 1 -1 1 -1Tails -1 1 1 -1Naturally, my son plays T H and I always lose. The point is that even thoughmy son ends up either playing heads or playing tails, in order to describe howhe makes his decision, you need four strategies. Using the four strategies hecould give instructions to