Session 1 Lecture Notes

Chapter 1 Introduction Game Theory is a misnomer for Multiperson Decision Theory. It develops tools, meth­ ods, and language that allow a coherent analysis of the decision-making processes when there are more than one decision-makers and each player’s payoff possibly depends on the actions taken by the other players. In this lecture, I will illustrate some of these methods on simple examples. Note that, since a player’s preferences on his actions depend on which actions the other parties take, his action depends on his beliefs about what the others do. Of course, what the others do depends on their beliefs about what each player does. In this way, a player’s action, in principle, depends on the actions available to each player, each player’s preferences on the outcomes, each player’s beliefs about which actions are available to each player and how each player ranks the outcomes, and further his beliefs about each player’s beliefs, ad infinitum. When players think through what the other players will do, taking what the other players think about them into account, they may find a clear way to play the game. Consider the following “game”: 1\2 L m R T 1, 1 0, 2 2, 1 M 2, 2 1, 1 0, 0 B 1, 0 0, 0 −1, 1 Here, There are two players, namely Player 1 and Player 2. Player 1 has strategies, T, M, B, and Player 2 has strategies L, m, R. They pick their strategies simultaneously. Every pair of strategies leads to a payoff to each player, a payoff measured by a real number. In each entry, the first number is the payoff of Player 1, and the second entry is the payoff of Player 2. For instance, if Player 1 plays T and Player 2 plays R, then Player 1 gets a payoff of 2 and Player 2 gets a payoff of 1. Let’s assume that each player knows that these are the strategies and the payoffs, each player knows that each player knows this, each player knows that each player knows that each player knows this,. . . ad infinitum. Now, Player 1 looks at his payoffs, and realizes that, no matter what the other player plays, it is better for him to play M rather than B. That is, if Player 2 plays L, M gives 2 and B gives 1; if Player 2 plays m, M gives 1, B gives 0; and if Player 2 plays R, M gives 0, B gives −1. Therefore, he realizes that he should not play B. Now he compares T and M . He realizes that, if Player 2 plays L or m, M is better than T , but if she plays R, T is definitely better than M . Would Player 2 play R? What would she play? To find an answer to these questions, Player 1 looks at the game from Player 2’s point of view. He realizes that, for Player 2, there is no strategy that is outright better than any other strategy. For instance, R is the best strategy if Player 1 plays B, but otherwise it is strictly worse than m. Would Player 2 think that Player 1 would play B? Well, she knows that Player 1 is trying to maximize his expected payoff, given by the first entries as everyone knows. She must then deduce that Player 1 will not play B. Therefore, Player 1 concludes, she will not play R (as it is worse than m in this case). Ruling out the possibility that Player 2 plays R, Player 1 looks at his payoffs and sees that M is now better than T , no matter what. On the other side, Player 2 goes through similar reasoning, and concludes that Player 1 must play M , and therefore plays L. Exercise 1 In the above analysis, players are assumed to make many assumptions about the other players’ reasoning capabilities. What are these assumptions? How would the analysis change if these assumptions are changed, e.g., if players act rationally but as­ sumes that the other parties play a random strategy? The kind of reasoning in the above analyses does not always yield such a clear prediction. Imagine that you want to meet with a friend in one of two places, about which you both are indifferent. Unfortunately, you cannot communicate with each other until you meet. This situation is formalized in the following game, which is called pure coordination game: 1 \2 Left Right Top 1, 1 0, 0 Bottom 0, 0 1, 1 Here, Player 1 chooses between Top and Bottom rows, while Player 2 chooses between Left and Right columns. In each box, the first and the second numbers denote the payoffs of players 1 and 2, respectively. Note that Player 1 prefers Top to Bottom if he knows that Player 2 plays Left; he prefers Bottom if he knows that Player 2 plays Right. Similarly, Player 2 prefers Left if she knows that Player 1 plays Top. There is no clear prediction about the outcome of this game. One may look for the stable outcomes (strategy profiles) in the sense that no player has incentive to deviate if he knows that the other players play the prescribed strategies. (Such strategy profiles are called Nash equilibrium, named after John Nash.) Here, TopLeft and Bottom-Right are such outcomes. But Bottom-Left and Top-Right are not stable in this sense. For instance, if Bottom-Left is known to be played, each player would like to deviate. Unlike in this game, mostly players have different preferences on the outcomes, in­ ducing conflict. In the following game, which is known as the Battle of Sexes, conflict and the need for coordination are present together. 1 \ 2 Left Right Top 2, 1 0, 0 Bottom 0, 0 1, 2 Here, once again players would like to coordinate on Top-Left or Bottom-Right, but now Player 1 prefers to coordinate on Top-Left, while Player 2 prefers to coordinate on Bottom-Right. The stable outcomes are again Top-Left and Bottom- Right. The above analysis assumes that players take their actions simultaneously, so that a player does not observe the action taken by the others when chooses his own action. In general, a player may observe some of the actions of some other players. Such a knowledge may have a dramatic impact on the outcome of the game. For an illustration, in the Battle of Sexes, imagine that Player 2 knows what Player 1 does when she takes her action. This can be formalized via the tree in Figure 1.1. Here, Player 1 first chooses between Top and Bottom, and then Player 2 chooses between Left and Right, 1 O B 2 2 B 2,1 O B O 0,0 0,0 1,2 Figure 1.1: Battle of Sexes with sequential moves knowing what Player 1 has chosen. Clearly, now Player 2 would choose Left if Player 1 plays Top, and choose Right if Player 1 plays Bottom. Knowing this, Player 1 would play Top. Therefore, one can argue that the only reasonable outcome of this game is Top-Left. (This kind of reasoning is called backward induction.) When Player 2 is able to check what the other player does, he gets only 1, while Player 1 gets 2. (In the previous game, two outcomes were stable, in which Player 2 would get 1 or 2.) That is, Player 2 prefers that Player 1 has information about what Player 2 does, rather than she herself has information about what Player 1 does. When it is common knowledge that a player has some information or not, the player may prefer not to have that information–a robust fact that we will see in various contexts. Exercise 2 Clearly, this is generated by the fact that Player 1 knows that Player 2 will know what Player 1 does when she moves. Consider the situation that Player 1 thinks that Player 2 will know what Player 1 does only with probability π < 1, and this probability does not depend on what Player 1 does. What will happen in a “reasonable” equilibrium? [By the end of this course, hopefully, you will be able to formalize this situation, and compute the equilibria.] Another interpretation is that Player 1 can communicate to Player 2, who cannot communicate to player 1. This enables Player 1 to commit to his actions, providing a strong position in the relation. 1 Exit (3/2,3/2) Play B O B (2,1) (0,0) O (0,0) (1,2) Figure 1.2: Battle of Sexes with exit option Exercise 3 Consider the following version of the last game: after knowing what Player 2 does, Player 1 gets a chance to change his action; then, the game ends. In other words, Player 1 chooses between Top and Bottom; knowing Player 1’s choice, Player 2 chooses between Left and Right; knowing 2’s choice, Player 1 decides whether to stay where he is or to change his position. What is the “reasonable” outcome? What would happen if changing his action would cost player 1 c utiles? Imagine that, before playing the Battle of Sexes, Player 1 has the option of exiting, in which case each player will get 3/2, or playing the Battle of Sexes. When asked to play, Player 2 will know that Player 1 chose to play the Battle of Sexes, as depicted in Figure 1.2. There are two “reasonable” equilibria (or stable outcomes). One is that Player 1 exits, thinking that, if he plays the Battle of Sexes, they will play the BottomRight equilibrium of the Battle of Sexes, yielding only 1 for Player 1. The second one is that Player 1 chooses to Play the Battle of Sexes, and in the Battle of Sexes they play Top-Left equilibrium. Some would argue that the first outcome is not really reasonable? Because, when asked to play, Player 2 will know that Player 1 has chosen to play the Battle of Sexes, forgoing the payoff of 3/2. She must therefore realize that Player 1 cannot possibly be planning to play Bottom, which yields the payoff of 1 max. That is, when asked to play, Player 2 should understand that Player 1 is planning to play Top, and thus she should play Left. Anticipating this, Player 1 should choose to play the Battle of Sexes game, in which they play Top-Left. Therefore, the second outcome is the only reasonable one. (This kind of reasoning is called Forward Induction.) Here are some more examples of games that will be referred to frequently throughout the course. Prisoners’ Dilemma 1 \2 Cooperate Defect Cooperate 5, 5 0, 6 Defect 6, 0 1, 1 This is a well known game that most of you know. Two prisoners are arrested for a crime for which there is no firm evidence, and they are being interrogated in separate rooms. Each prisoner could either cooperate with the other and not confess their crime or defect and confess the crime. In this game no matter what the other player does, each player would like to defect, confessing their crime. This yields (1, 1). If they both cooperated and not confessed their crime, each would get a better payoff of 5. Hawk-Dove game 1 \ 2 Hawk Hawk V −C V −C , 2 2 Dove 0,V Dove V, 0 V V , 2 2 This is an important biological game, but is also quite similar to many games in Eco­ nomics and Political Science. V is the value of a resource that one of the players will enjoy. If they shared the resource, their values are V /2. Hawk stands for a “tough” strategy, whereby the player does not give up the resource. However, if the other player is also playing hawk, they end up fighting, and incur the cost C/2 each. On the other hand, a Hawk player gets the whole resource for itself when playing a Dove. When V > C, this is a Prisoners’ Dilemma game, yielding a fight. When V < C, so that fighting is costly, this game is similar to another well-known game, named “Chicken”, where two players driving towards a cliff have to decide whether to stop or continue. The one who stops first loses face, but may save his life. More generally, a class of games called “wars of attrition” are used to model this type of situations. In this case, a player would like to play Hawk if his opponent plays Dove, and play Dove if his opponent plays Hawk. An investment game: 1 \ Invest Don’t Invest 2 Invest Don’t Invest θ, θ θ − c, 0 0,θ − c 0,0 Here, two parties simultaneously decide whether two invest; the investment is more valuable if the other party also invests (as in the coordination game). For example, consider a potential worker and a potential employer, potential worker deciding whether to get education (investing in his human capital), and the potential employer deciding wether to invest in a technology that would require human capital. (Think about what are the reasonable outcomes for various values of θ and c. How would you analyze this situations if the players do not know the actual values of these parameters, but have some private information about what these values could be?)