Chapter 3: Representation of Games

Chapter 3 Representation of Games We are now ready to formally introduce games and some fundamental concepts, such as a strategy. In order to analyze a strategic situations, one needs to know • who the players are, • which actions are available to them, • how much each player values each outcome, • what each player knows. A game is just a formal representation of the above information. This is usually done in one of the following two ways: 1. The extensive-form representation, in which the above information is explicitly described using game trees and information sets; 2. The normal-form (or strategic-form) representation, in which the above information is summarized by use of strategies. Both forms of representation are useful in their on way, and I will use both representations extensively throughout the course. It is important to emphasize that, when describing what a player knows, one needs to specify not only what he knows about external parameters, such as the payoffs, but also what he knows about the other players’ knowledge and beliefs about these parameters, 29 30 CHAPTER 3. REPRESENTATION OF GAMES as well as what he knows about the other players’ knowledge of his own beliefs, and so on. In both representations such information is encoded in an economical manner. In the first half of this course, we will focus on non-informational issues, by confining ourselves to the games of complete information, in which everything that is known by a player is known by everybody. In the second half, we will focus on informational issues, allowing players to have asymmetric information, so that one may know a piece of information that is not known by another. The outline of this lecture is as follows. The first section is devoted to the extensiveform representation of games. The second section is devoted to the concept of strategy. The third section is devoted to the normal-form representation, and the equivalence between the two representations. The final section contains exercises and some of their solutions. 3.1 Extensive-form Representation The extensive-form representation of a game contains all the information about the game explicitly, by defining who moves when, what each player knows when he moves, what moves are available to him, and where each move leads to, etc. This is done by use of a game tree and information sets–as well as more basic information such as players and the payoffs. 3.1.1 Game Tree Definition 3.1 A tree is a set of nodes and directed edges connecting these nodes such that 1. there is an initial node, for which there is no incoming edge; 2. for every other node, there is exactly one incoming edge; 3. for any two nodes, there is a unique path that connect these two nodes. For a visual aid, imagine the branches of a tree arising from its trunk. For example, the graph in Figure 3.1 is a tree. There is a unique starting node, and it branches out from there without forming a loop. It does look like a tree. On the other hand, the 3.1. EXTENSIVE-FORM REPRESENTATION 31 graphs in Figure 3.2 are not trees. In the graph on the left-hand side, there are two alternative paths to node A from the initial node, one through node B and one through node C. This violates the third condition. (Here, the second condition in the definition is also violated, as there are two incoming edges to node A.) On the right-hand side, there is no path that connects the nodes x and y, once again violating the third condition. (Once again, the second condition is also violated.) Figure 3.1: A tree. B x A y C Figure 3.2: Two graphs that are not a tree Note that edges (or arrows) come with labels, which can be same for two different arrows. In a game tree there are two types of nodes, terminal nodes, at which the game ends, and non-terminal nodes, at which a player would need to make a further decision. This is formally stated as follows. Definition 3.2 The nodes that are not followed by another node are called terminal. 32 CHAPTER 3. REPRESENTATION OF GAMES The other nodes are called non-terminal. Non-terminal nodes Terminal Nodes Figure 3.3: Terminal and non-terminal nodes. For example, the terminal and non-terminal nodes for the game tree in Figure 3.1 are as in Figure 3.3. There is no outgoing arrow in any terminal node, indication that the game has ended. A terminal node may also be referred to as an outcome in the game. At such a node, we need to specify the players’ payoffs towards describing their preferences among the outcomes. On the other hand, there are some outgoing arrows in any non-terminal node, indicating that some further decisions are to be made. In that case, on needs to describe who makes a decision and what he knows at the time of the decision. A game is formally defined just like this, next. 3.1.2 Games in Extensive Form Definition 3.3 (Extensive form) A Game consists of • a set of players, • a tree, 3.1. EXTENSIVE-FORM REPRESENTATION 33 • an allocation of non-terminal nodes of the tree to the players, • an informational partition of the non-terminal nodes (to be made precise in the next subsection), and • payoffs for each player at each terminal node. Players The set of players consists of the decision makers or actors who make some decision during the course of the game. Some games may also contain a special player Nature (or Chance) that represent the uncertainty the players face, as it will be explained in Subsection 3.1.4. The set of games is often denoted by  = {1 2     } and   ∈  are designated as generic players. Outcomes and Payoffs The set of terminal nodes often denoted by . At a terminal node, the game has ended, leading to some outcome. At that point, one specifies a payoff, which is a real number, for each player . The mapping  :  → R that maps each terminal node to the payoff of player  at that node is the Von-Neumann and Morgenstern utility function of player . Recall from the previous chapter that this means that player  tries to maximize the expected value of  . That is, given any two lotteries  and  on , he prefers  to  if and only if  leads to a higher expected value for P P function  than  does, i.e., ∈  ()  () ≥ ∈  ()  (). Recall also that these preferences do not change if we multiply all payoffs with a fixed positive number or add a fixed number to all payoffs. The preferences do change under any other transformation. Decision Nodes In a non-terminal node, a new decision is to be made. Hence, in the definition of a game, a player is assigned to each non-terminal node. This is the player who will make the decision at that point. Towards describing the decision problem of the player at the time, one defines the available choices to the player at the moment. These are the outgoing arrows at the node, each of them leading to a different node. Each of these choices is also called move or action (interchangeably). Note that the 34 CHAPTER 3. REPRESENTATION OF GAMES moves come with their labels, and two different arrows can have the same label. In that case, they are the same move. 1 Head Tail 2 2 head tail (-1,1) (1,-1) head (1,-1) tail (-1,1) Figure 3.4: Matching Pennies with Perfect Information Example 3.1 (Matching Pennies with Perfect Information) Consider the game in Figure 3.4.The tree consists of 7 nodes. The first one is allocated to Player 1, and the next two to Player 2. The four end-nodes have payoffs attached to them. Since there are two players, payoff vectors have two elements. The first number is the payoff of Player 1 and the second is the payoff of Player 2. These payoffs are von NeumannMorgenstern utilities. That is, each player tries to maximize the expected value of his own payoffs given his beliefs about how the other players will play the game. One also needs to describe what the player knows at the moment of his decision making. This is formally done by information sets, as follows. 3.1.3 Information Sets Definition 3.4 An information set is a collection of nodes such that 1. the same player  is to move at each of these nodes; 2. the same moves are available at each of these nodes. Definition 3.5 An information partition is an allocation of each non-terminal node of the tree to an information set; the starting node must be "alone". 3.1. EXTENSIVE-FORM REPRESENTATION 35 The meaning of an information set is that when the individual is in that information set, he knows that one of the nodes in the information set is reached, but he cannot rule out any of the nodes in the information set. Moreover, in a game, the information set belongs to the player who is to move in the given information set, representing his uncertainty. That is, the player  who is to move at the information set is unable to distinguish between the points in the information set, but able to distinguish between the points outside the information set from those in it. Therefore, the above definition would be meaningless without condition 1, while condition 2 requires that the player knows his available choices. The latter condition can be taken as a simplifying assumption. I also refer to information sets as history and write  for a generic history at which player  moves. For an example, consider the game in Figure 3.5. Here, Player 2 knows that Player 1 has taken action  or  and not action ; but Player 2 cannot know for sure whether 1 has taken  or .1 1 x T B 2 L R L R Figure 3.5: A game Example 3.2 (Matching Pennies with Perfect Information) In Figure 3.4, the informational partition is very simple. Every information set has only one element. Hence, there is no uncertainty regarding the previous play in the game. 1 Throughout the course, the information sets are depicted either by circles (as in sets), or by dashed curves connecting the nodes in the information sets, depending on convenience. Moreover, the information sets with only one node in them are depicted in the figures. For example, in Figure 3.5, the initial node is in an information set that contains only that node. 36 CHAPTER 3. REPRESENTATION OF GAMES A game is said to have perfect information if every information set has only one element. Recall that in a tree, each node is reached through a unique path. Hence, in a perfect-information game, a player can construct the previous play perfectly. For instance in Figure 3.4, Player 2 knows whether Player 1 chose Head or Tail. And Player 1 knows that when he plays Head or Tail, Player 2 will know what Player 1 has played. 3.1.4 Nature as a player and representation of uncertainty The set of players includes the decision makers taking part in the game. However, in many games there is room for chance, e.g. the throw of dice in backgammon or the card draws in poker. More broadly, the players often face uncertainty about some relevant fact, including what the other players know. In that case, once again chance plays a role (as a representation). To represent these possibilities we introduce a fictional player: Nature. There is no payoff for Nature at end nodes, and every time a node is allocated to Nature, a probability distribution over the branches that follow needs to be specified, e.g., Tail with probability of 1/2 and Head with probability of 1/2. Note that this is the same as adding lotteries in the previous section to the game. For an example, consider the game in Figure 3.6. In this game, a fair coin is tossed, where the probability of Head is 1/2. If Head comes up, Player 1 chooses between Left and Right; if Tail comes up, Player 2 chooses between Left and Right. The payoffs also depend on the coin toss. Left (5, 0) 1 Head 1/2 Right 1/2 Left (2, 2) Nature Tail 2 (3, 3) Right (0, -5) Figure 3.6: A game with chance 3.1. EXTENSIVE-FORM REPRESENTATION 3.1.5 37 Commonly Known Assumptions The structure of a game is assumed to be known by all the players, and it is assumed that all players know the structure and so on. That is, in a more formal language, the structure of game is common knowledge.2 For example, in the game of Figure 3.5, Player 1 knows that if he chooses  or , Player 2 will know that Player 1 has chosen one of the above actions without being able to rule out either one. Moreover, Player 2 knows that Player 1 has the above knowledge, and Player 1 knows that Player 2 knows it, and so on. Using information sets and richer game trees, one can model arbitrary information structures like this. For example, one could also model a situation in which Player 1 does not know whether Player 2 could distinguish the actions  and . One could do that by having three information set for Player 2; one of them is reached only after  , one of them is reached only after  and one of them can be reached after both  and . Towards modeling uncertainty of Player 1, one would further introduce a chance move, whose outcome either leads to the first two information sets (observable case) or to the last information case (unobservable case). Exercise 3.1 Write the variation of the game in Figure 3.5, in which Player 1 believes that Player 2 can distinguish actions  and  with probability 13 and cannot distinguish them probability 23, and this beliefs is common knowledge. To sum up: At any node, the following are known: which player is to move, which moves are available to the player, and which information set contains the node, summarizing the player’s information at the node. Of course, if two nodes are in the same information set, the available moves in these nodes must be the same, for otherwise the player could distinguish the nodes by the available choices. Again, all these are assumed to be common knowledge. 2 Formally, a proposition  is said to be common knowledge if all of the following are true:  is true; everybody knows that  is true; everybody knows that everybody knows that  is true; . . . ; everybody knows that . . . everybody knows that  is true, ad infinitum. 38 CHAPTER 3. REPRESENTATION OF GAMES 3.2 Strategies Definition 3.6 A strategy of a player is a complete contingent-plan determining which action he will take at each information set he is to move (including the information sets that will not be reached according to this strategy). More mathematically, a strategy of a player  is a function  that maps every information set  of player  to an action that is available at  . It is important to note the following three subtleties in the definition. 1. One must assign a move to every information set of the player. (If we omit to assign a move for an information set, we would not know what the player would have done when that information set is reached.) 2. The assigned move must be available at the information set. (If the assigned move is not available at an information set, then the plan would not be feasible as it could not be executed when that information set is reached.) 3. At all nodes in a given information set, the player plays the same move. (After all, the player cannot distinguish those nodes from each other.) Example 3.3 (Matching Pennies with Perfect Information) In Figure 3.4, Player 1 has only one information set. Hence, the set of strategies for Player 1 is {Head, Tail}. On the other hand, Player 2 has two information sets. Hence, a strategy of Player 2 determines what to do at each information set, i.e., depending on what Player 1 does. So, her strategies are:  = Head if Player 1 plays Head, and Head if Player 1 plays Tail;  = Head if Player 1 plays Head, and Tail if Player 1 plays Tail;   = Tail if Player 1 plays Head, and Head if Player 1 plays Tail;   = Tail if Player 1 plays Head, and Tail if Player 1 plays Tail. Example 3.4 In Figure 3.5, both players have one information set. Hence, the sets of strategies for Players 1 and 2 are 1 = {  } and 2 = { }  3.2. STRATEGIES 39 respectively. Although Player 2 moves at two different nodes, they are both in the same information set. Hence, she needs to either play  at both nodes or  at both nodes. For certain purposes it might suffice to look at the reduced-form strategies. A reduced form strategy is defined as an incomplete contingent plan that determines which action the agent will take at each information set he is to move and that has not been precluded by this plan. But for many other purposes we need to look at all the strategies. Throughout the course, we must consider all strategies. What are the outcomes of strategies of players? What are the payoffs generated by those strategies? Towards answering these questions, we need first a couple of jargon. Definition 3.7 In a game with players  = {1     }, a strategy profile is a list  = (1       ) of strategies, one for each player. Definition 3.8 In a game without Nature, each strategy profile  leads to a unique terminal node  (), called the outcome of . The payoff vector from strategy  is the payoff vector at  (). Sometimes the outcome is also described by the resulting history, which can also be called as the path of play. Example 3.5 (Matching Pennies with Perfect Information) In Figure 3.4, if Player 1 plays Head and Player 2 plays , then the outcome is both players choose Head, and the payoff vector is (−1 1). If Player 1 plays Head and Player 2 plays  , the outcome is the same, yielding the payoff vector (−1 1). If Player 1 plays Tail and Player 2 plays HT, then the outcome is now both players choose Tail, but the payoff vector is (−1 1) once again. Finally, if Player 1 plays Tail and Player 2 plays , then the outcome is Player 1 chooses Tail and Player 2 chooses Head, 40 CHAPTER 3. REPRESENTATION OF GAMES and the payoff vector is (1 −1). One can compute the payoffs for the other strategy profiles similarly. In games with Nature, a strategy profile leads to a probability distribution on the set of terminal nodes. The outcome of the strategy profile is then the resulting probability distribution. The payoff vector from the strategy profile is the expected payoff vector under the resulting probability distribution. Example 3.6 (A game with Chance) In Figure 3.5, each player has two strategies, Left and Right. The outcome of the strategy profile (Left,Left) is the lottery that Nature chooses Head and Player 1 plays Left with probability 1/2 and Nature chooses Tail and Player 2 plays Left with probability 1/2. Hence, the expected payoff vector is  (  ) = 1 1 (5 0) + (3 3) = (4 32)  2 2 Sometimes, it suffices to summarize all of the information above by the set of strategies and the utility vectors from the strategy profiles, computed as above. Such a summary representation is called formal-form or strategic-form representation. 3.3 Normal form Definition 3.9 (Normal form) A game is any list  = (1       ; 1       )  where, for each  ∈  = {1     },  is the set of all strategies that are available to player , and  : 1 ×    ×  → R is player ’s von Neumann-Morgenstern utility function. 3.3. NORMAL FORM 41 Notice that a player’s utility depends not only on his own strategy but also on the strategies played by other players. Moreover, each player  tries to maximize the expected value of  (where the expected values are computed with respect to his own beliefs); in other words,  is a von Neumann-Morgenstern utility function. We will say that player  is rational iff he tries to maximize the expected value of  (given his beliefs). It is also assumed that it is common knowledge that the players are  = {1     }, that the set of strategies available to each player  is  , and that each  tries to maximize expected value of  given his beliefs. When there are only two players, we can represent the normal form game by a bimatrix (i.e., by two matrices): 1\2     0 2 1 1  4 1 3 2 Here, Player 1 has strategies  and , and Player 2 has the strategies  and . In each box the first number is Player 1’s payoff and the second one is Player 2’s payoff (e.g., 1 (  ) = 0, 2 (  ) = 2.) 3.3.1 From Extensive Form to Normal Form As it has been described in detail in the previous section, in an extensive form game, the set of strategies is the set of all complete contingent plans, mapping information sets to the available moves. Moreover, each strategy profile  leads to an outcome  (), which is in general probability distribution on the set of terminal nodes. The payoff vector is the expected payoff vector from  (). One can always convert an extensive-form game to a normal form game in this way. Example 3.7 (Matching Pennies with Perfect Information) In Figure 3.4, based on the earlier analyses, the normal or the strategic form game corresponding to the matching penny game with perfect information is      −1 1 −1 1 1 −1 1 −1   1 −1 −1 1 1 −1 −1 1 42 CHAPTER 3. REPRESENTATION OF GAMES 1 Head Tail 2 head tail (-1,1) (1,-1) head tail (1,-1) (-1,1) Figure 3.7: Matching Pennies Game Information sets are very important. To see this, consider the following standard matching-penny game. This game has imperfect information. Example 3.8 (Matching Pennies) Consider the game in Figure 3.7. This is the standard matching penny game, which has imperfect information as the players move simultaneously. In this game, each player has only two strategies: Head and Tail. The normal-form representation is 1\2 head tail Head −1 1 1 −1 Tail 1 −1 −1 1 The two matching penny games may appear similar (in extensive form), but they correspond to two distinct situations. Under perfect information Player 2 knows what Player 1 has done, while nobody knows about the other player’s move under the version with imperfect information. As mentioned above, when there are chance moves, one needs to compute the expected payoffs in order to obtain the normal-form representation. This is illustrated in the next example. Example 3.9 (A game with Nature) As mentioned, in Figure 3.6, each player has two strategies, Left and Right. Following the earlier calculations, the normal-form rep- 3.3. NORMAL FORM 43 2 TT HH HT TH 1 1 1 1 H T H T ‐1 1 1 ‐1 ‐1 1 ‐1 1 H T H T 1 ‐1 1 ‐1 1 ‐1 ‐1 1 Figure 3.8: A matching penny game with perfect information? resentation is obtained as follows: 1\2 Left Right Left 4 32 52 −52 Right 52 52 1 −32 The payoff from (Left,Left) has been computed already. The payoff from (Left, Right) computed as 1 1 (5 0) + (0 −5) = (52 −52)  2 2 While there is a unique normal-form representation for any extensive-form game (up to a relabeling of strategies), there can be many extensive-form games with the same normal-form representation. After all, any normal-form game can also be represented as a simultaneous action game in extensive form. For example, the normal-form game of matching pennies with perfect information can also be represented as in Figure 3.8. 3.3.2 Mixed Strategies In many cases a player may not be able to guess exactly which strategies the other players play. In order to cover these situations we introduce the mixed strategies: Definition 3.10 A mixed strategy of a player is a probability distribution over the set of his strategies. 44 CHAPTER 3. REPRESENTATION OF GAMES If player  has strategies  = {1  2       }, then a mixed strategy  for player  is a function on  such that 0 ≤   ( ) ≤ 1 and  (1 ) +   (2 ) + · · · +   ( ) = 1 There are many interpretations for mixed strategies, from deliberate randomization (as in coin tossing) to heterogeneity of strategies in the population. In all cases, however, they serve as a device to represent the uncertainty the other players face regarding the strategy played by player . Throughout the course,  is interpreted as the other players’ beliefs about the strategy player  plays. 3.4 Exercises with Solutions 1. What is the normal-form representation for the game in Figure 3.12? Solution: Player 1 has two information sets with two action in each. Since the set of strategies is functions that map information sets to the available moves, he has the following four strategies:    . The meaning here is straightforward:  assigns  to the first information set and  to the last information set. On the other hand, Player 2 has only two strategies:  and . Filling in the payoffs from the tree, one obtains the following normal-form representation: 1\2    1 −5 5 2 3 3 5 2  4 4 4 4  4 4 4 4  2. [Midterm 1, 2001] Find the normal-form representation of the game in Figure 3.9. 3.4. EXERCISES WITH SOLUTIONS 45 Figure 3.9: Solution: 1\2     2 1 2 1 2 1  2 1 2 1 2 1  2 1 2 1 2 1  2 1 2 1 2 1  1 2 3 1 1 3  1 2 3 1 3 1  1 2 1 3 1 3  1 2 1 3 3 1 3. [Make up for Midterm 1, 2007] Write the game in Figure 3.10 in normal form. Solution: The important point in this exercise is that Player 2 has to play the same move in a given information set. For example, she cannot play  on the left node and  on the right node of her second information set. Hence, her set of strategies is {   }.      3 3 3 3 0 0 0 0  3 3 3 3 0 0 0 0  0 0 0 0 3 3 3 3  0 0 0 0 3 3 3 3  2 2 2 2 1 −1 −1 3  2 2 2 2 −1 1 1 −1 46 CHAPTER 3. REPRESENTATION OF GAMES 1 A c B 2 a a b b a 3 3 2 2 b 1 3 3 0 0 0 0 Y X 2 x y x y 1 ‐1 ‐1 3 ‐1 1 1 ‐1 Figure 3.10: 4. [Make up for Midterm 1, 2007] Write the following game in normal form, where the first entry is the payoff of student and the second entry is the payoff of Prof. healthy sick .5 student regular .5 Make up Make up student regular Prof 2 1 same 4 -1 new 1 -c same 4 0 new 0 -1 1 -c Solution: Write the strategies of the student as , , , and , where  means Regular when Healthy and Make up when Sick,  means Make up 3.5. EXERCISES 47 Figure 3.11: when Healthy and Regular when Sick, etc. The normal form game is as follows: Student\Prof same new  1 0 1 0  3 12  2 −1 32 (1 − ) 2 4 −12  12 −(1 + )2 1 − Here, the payoffs are obtained by taking expectations over whether the student is healthy or sick. For example,  leads to (2 1) and (0 −1) with equal prob- abilities, yielding (1 0), regardless of the strategy of Prof. On the other hand, ( new) leads to (2 1) and (1 −) with equal probabilities, yielding (32 (1 − ) 2). 5. [Midterm 2006] Write the game in Figure 3.11 in normal form. Solution: 3.5 1\2          1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  3 2 3 2 3 2 3 2 3 1 3 1 0 0 0 0  0 0 0 0 0 0 0 0 0 −1 2 3 0 −1 2 3 Exercises 1. [Midterm 1, 2010] Write the game in Figure 3.13 in normal form. 48 CHAPTER 3. REPRESENTATION OF GAMES 1 A 2 D α δ (4,4) (5,2) 1 a d (3,3) Figure 3.12: A centepede-like game Figure 3.13: (1,-5) 3.5. EXERCISES 49 2. [Midterm 1, 2005] Write the game in Figure 3.14 in normal form. 3. [Midterm 1, 2004] Write the game in Figure 3.15 in normal form. Figure 3.14: 4. [Midterm 1, 2007] Write the following game in normal form. Figure 3.15: 50 CHAPTER 3. REPRESENTATION OF GAMES Figure 3.16: 5. [Homework 1, 2011] Find the normal-form representation of the extensive-form game in Figure 3.16.