Game Theory PDF

P1: SFK Trim: 189mm × 246mm Top: 0.393in Gutter: 0.83in AppendixNew cuuk974-Belleflamme 978 0 521 86299 8 September 10, 2014 21:33 682 Game theory A.2 Games in extensive form and su...

P1: SFK Trim: 189mm × 246mm Top: 0.393in Gutter: 0.83in AppendixNew cuuk974-Belleflamme 978 0 521 86299 8 September 10, 2014 21:33 682 Game theory A.2 Games in extensive form and subgame perfection Extensive-form games Many games have the feature that players make their decisions at different points in time. Such dynamic situations are typically better approached as games presented in their extensive form. The extensive form representation of a game specifies a number of things: (1) the players in the game (this possibly includes a player called Nature to include the situation in which some external event occurs with a particular probability and some players have to make decisions before the uncertainty is resolved); (2) when each player has to make a decision; (3) what decisions each player can make whenever it is his or her turn; (4) what each player knows about the other players’ decisions which were made before; (5) the payoffs of each player for each combination of decisions that can possibly be chosen by the players. A formal definition of an extensive form game would take us much time; see Mas-Colell, Whinston and Green (1995). A game in extensive form starts at an initial decision node at which player i makes a decision. Each of the possible choices by player i is represented by a branch. At the end of each branch is another decision node at which some other player j has to make a choice; again, each choice is represented by a branch. This is continued until no more choices are made and the end of the game is reached, represented by terminal nodes. At each terminal node, we list the players’ payoffs arising from the sequence of decisions leading to that terminal node. The set of all decision nodes between which a player cannot distinguish are called an information set. Games of perfect information A special class of games are games of perfect information. In such games, all players know in which decision node they are when making a choice. In other words, in games of perfect information, each information set contains exactly one decision node. As an example of a game of perfect information, consider a simplified Stackelberg game with demand P(q) = 0 for q > 2, P(q) = 1/2 for q ∈ (1, 2], and P(q) = 1 for p ∈ (0, 1]. Marginal costs are assumed to be equal to zero. Each of the two players can choose either high output q H = 3/2 or low output q L = 1/4. Profits are π i (q H , q H ) = 0, π i (q L , q L ) = 1/2, π i (q H , q L ) = 3/4 and π i (q L , q H ) = 1/4. Suppose firm 1 sets the quantity before firm 2. Thus we are considering a 2-stage game in which, at stage 1, firm 1 chooses its quantity q1 ∈ {q L , q H } and, at stage 2, firm 2 chooses its quantity q2 ∈ {q L , q H }. Games in extensive form are often represented by game trees. The game tree for our example is depicted in Figure A.1 (where, at each terminal node, firm 1’s payoff is written above firm 2’s payoff). Using simple reasoning, it is clear that if firm 1 chose q L , firm 2 would choose q H and if firm 1 chose q H firm 2 would choose q L. If firm 1 anticipates these choices of firm 2 (which it does if it knows that firm 2 maximizes profit), it will choose q H if it maximizes its profit. Because players know exactly where they are in the game tree whenever they have to make a decision (i.e., their information set at each point of decision contains a single element), we can use the backward induction procedure to obtain a unique prediction of the outcome of the game (as long as payoffs of each player are different across the different end nodes of the game). P1: SFK Trim: 189mm × 246mm Top: 0.393in Gutter: 0.83in AppendixNew cuuk974-Belleflamme 978 0 521 86299 8 September 10, 2014 21:33 683 A.2 Games in extensive form and subgame perfection 1 Figure A.1 Extensive form of the simplified Stackelberg model qL qH 2 2 qL qH qL qH 1/2 1/4 3/4 0 1/2 3/4 1/4 0 Alternatively, we can consider the normal-form representation of this game. Strategies are X 1 = {q L , q H }, X 2 = {q L |q L ∧ q L |q H , q L |q L ∧ q H |q H , q H |q L ∧ q L |q H , q H |q L ∧ q H |q H }. Firm 1 only has one decision node and can choose between two actions at this node; therefore, firm 1 has two strategies: firm 1’s strategy q L is denoted by L and the strategy q H by H. As for firm 2, it has two decision nodes and two possible actions at each node; that makes 4 (2 × 2) strategies for firm 2: firm 2’s strategy q L |q L ∧ q L |q H is denoted by L L, q L |q L ∧ q H |q H by L H , q H |q L ∧ q L |q H by H L and q H |q L ∧ q H |q H by H H. Note that strategies are contingent plans that tell the player what to decide at each decision node where the player is called upon to play. The normal-form representation of the game is then Firm 2 LL LH HL HH L 1/2, 1/2 1/2 , 1/2 1/4, 3/4∗ ∗ 1/4∗ , 3/4∗ Firm 1 H 3/4∗ , 1/4∗ 0, 0 3/4∗ , 1/4∗ 0, 0 We observe that this game form has three pure-strategy Nash equilibria, (H, L L), (H, H L) and (L , H H ). The second of these three equilibria, (H, H L), is also the outcome of our previous reasoning. The other two equilibria, however, can be criticized as unreasonable because they involve non-credible threats by firm 2: in (H, L L), firm 2 threatens to choose q L if firm 1 has chosen q L , which is not credible; similarly, in (L , H H ), firm 2 threatens to choose q H if firm 1 has chosen q H , which is not credible either. We can exclude such non-credible threats by the backward induction procedure that was exemplified above. The general result is the following: Every finite game of perfect information has a pure-strategy equilibrium that can be derived through backward induction. If no player has the same payoffs at any two terminal nodes, there exists a unique Nash equilibrium that can be derived through backward induction. This is Zermelo’s theorem. Subgame perfect Nash equilibrium We want to exclude non-credible threats not only in games of perfect information but more generally in any multi-stage game. To do so, we first have to introduce the notion of a subgame. P1: SFK Trim: 189mm × 246mm Top: 0.393in Gutter: 0.83in AppendixNew cuuk974-Belleflamme 978 0 521 86299 8 September 10, 2014 21:33 684 Game theory A subgame in an extensive-form game (1) begins at a decision node that is the only decision node of the information set it belongs to (i.e. at the beginning of a subgame, the player who is about to decide knows where he is in the game) and (2) includes those and only those decision and terminal nodes that follow the decision node at which the subgame starts. In addition, we require that if we take any information set that contains a decision node in the subgame, all decision nodes contained in this information set must belong to the subgame. In the game tree, this means that a subgame cannot cut information sets. To exclude non-credible threats, we have to require that a Nash equilibrium of the whole game induces a Nash equilibrium in each of its subgames. The corresponding equilib- rium concept is that of a subgame perfect Nash equilibrium (SPNE). Let us define this a bit more formally. Denote an extensive-form game by " E. A strategy profile s ∗ in an n-player extensive form game " E is defined to be a SPNE if it induces a Nash equilibrium in every subgame of " E. The following result holds. Consider an extensive form game " E and some subgame " ES of " E. Suppose that strategy profile s s∗ is an SPNE in subgame " ES. Let "ˆ E be the reduced game formed by replacing subgame " ES by a terminal node with payoffs equal to those arising from play of s s∗. Then, (1) in any SPNE s ∗ of " E in which s s∗ is an SPNE of " ES , players’ reduced strategies ŝ ∗ of s ∗ in the reduced game "ˆ E constitute an SPNE of "ˆ E and (2) if ŝ ∗ is an SPNE of "ˆ E , then the strategy profile s ∗ that specifies the moves in s s∗ at information sets belonging to " ES and that specifies the moves as described by ŝ ∗ at information sets not belonging to " ES is an SPNE of " E. For games with a finite number of stages (of perfect or imperfect information), we can generalize the backward induction procedure from above that is only useful for games of perfect information. The generalized backward induction procedure works as follows. 1. Identify all Nash equilibria of the final subgames (those that have no other subgames nested within). 2. Select one Nash equilibrium in each of those subgames and derive the reduced extensive form in which the subgames are replaced by the equilibrium payoffs in the selected Nash equilibrium of those subgames. 3. Repeat steps 1 and 2 for the reduced game until this procedure provides a path of play from the initial node to a terminal node of the game. The outcome of this generalized backward induction procedure gives all subgame perfect Nash equilibria of the game. We make use of this result repeatedly in the book. Note however that the procedure is not useful, e.g., in infinitely repeated games. Infinitely repeated games are analysed in Chapter 14. A.3 Static asymmetric information games and Bayesian Nash equilibrium So far, we have ignored the possibility that some players may possess private information, i.e., payoff-relevant information that is not available to other players. To analyse such situations of incomplete information, we consider Bayesian games as games in which Nature chooses the P1: SFK Trim: 189mm × 246mm Top: 0.393in Gutter: 0.83in AppendixNew cuuk974-Belleflamme 978 0 521 86299 8 September 10, 2014 21:33 685 A.4 Dynamic asymmetric information games state of the world ω ∈ $, which is only partially revealed to players. Formally, suppose θ i ∈ &i is a random variable chosen by Nature. The realization θ i is only observed by player i. We say that player i is of type θ i. For instance, the type may reflect a firm’s cost type, which may be unobservable for other players. Players have common knowledge of the type distribution; this is a joint probability distribution of the θ i ’s, denoted by ρ(θ 1 ,... , θ n ). Payoff functions π i then depend on the actions x ∈ X and the realization of types θ ∈ &. Hence, a Bayesian game in normal form consists of the type space &, the prior probability distribution ρ, the set of players N , a strategy set X i and a payoff function π i for each player i ∈ N. Suppose there is a finite number of types θ i for each player. Then all players share common prior probabilities ρ(θ 1 ,... , θ n ). Player i observes his or her type θ i so that his or her beliefs are the conditional probability ρ(θ −i |θ i ). Note that the conditioning does not affect beliefs if the own type realization does not provide information of the type distribution of the other players. This is for instance the case if types are drawn independently from some type distribution that applies to all players. Observing θ i , player i has expected payoff ! ρ(θ −i |θ i )π i (xi , s−i (θ −i ), (θ i , θ −i )) θ −i ∈&−i if he chooses xi and the other players follow decision rules (or strategies) s j (θ j ), j &= i. Hence, observing θ i , player i chooses ! si∗ (θ i ) ∈ arg max ∗ ρ(θ −i |θ i )π i (xi , s−i (θ −i ), (θ i , θ −i )) xi ∈X i θ −i ∈&−i in a Bayesian Nash equilibrium. It is straightforward to see that Bayesian Nash equilibrium is formally the same concept as Nash equilibrium. Since each type occurs with positive probability, the above formulation is equivalent to the following ex ante formulation that solves for all types of each player i, ! ! si∗ (.) ∈ arg max ∗ ρ(θ i |θ −i ) π i (si (θ i ), s−i (θ −i ), (θ i , θ −i )), (A.1) &i si (.)∈X i θ i ∈&i θ −i ∈&−i with X i&i denoting the space of pure strategies. Hence, a Bayesian Nash equilibrium for the Bayesian game is a strategy profile (si∗ (.),... , sn∗ (.)) that constitutes a Nash equilibrium of game in normal form with strategy sets X i&i and payoff functions ! ! π" i (s1 (.),... , sn (.)) = ρ(θ i , θ −i )π i (si (θ i ), s−i (θ −i ), (θ i , θ −i )), θ i ∈&i θ −i ∈&−i which are the (ex ante) expected payoffs of each player. That is, for all i ∈ N , (A.1) is satisfied. A.4 Dynamic asymmetric information games and perfect Bayesian Nash equilibrium In static games of incomplete information, the beliefs of uninformed players are easy to specify: players know the probability distribution that Nature uses to assign types, and their private information about their type possibly allows them to update their beliefs. However, since their P1: SFK Trim: 189mm × 246mm Top: 0.393in Gutter: 0.83in AppendixNew cuuk974-Belleflamme 978 0 521 86299 8 September 10, 2014 21:33 686 Game theory decisions are being made simultaneously they cannot base their beliefs on decisions of other players. Things change in dynamic games of incomplete information, where players make their decisions at different points in time. Here, before making a decision, uninformed players have the opportunity to use the observation of other players’ previous decisions to update their beliefs from the initial probability distribution used by Nature. In such contexts, we want to refine Nash equilibrium by requiring that beliefs are formed optimally given decisions, while decisions are made optimally given beliefs. This defines intuitively the concept of perfect Bayesian Nash equilibrium (PBNE). Perfect Bayesian Nash equilibrium To give a more precise definition of PBNE, we need to introduce three additional notions. First, we define a belief system as an assignment of probabilities to every node in the game such that the sum of probabilities in any information set is 1. Second, we say that a strategy profile is sequentially rational at a particular information set for a particular belief system if and only if the expected payoff of the player who has the move at that information set is maximal given the strategies played by all the other players. A strategy profile is sequentially rational for a particular belief system if it satisfies this requirement for every information set. Third, a belief system is consistent for a given strategy profile if and only if the probability assigned by the system to every node is computed as the probability of that node being reached given the strategy profile, i.e., players use Bayes’ rule. We can then define a perfect Bayesian equilibrium as a strategy profile and a belief system such that the strategies are sequentially rational given the belief system and the belief system is consistent, wherever possible, given the strategy profile. A more detailed definition is given in the context of signalling games below. In the definition, the phrase ‘wherever possible’ deserves some explanation. Bayes’ rule can be applied to compute beliefs at information sets that are on the equilibrium path, i.e., that can be reached with positive probability given the players’ equilibrium strategies. Off the equilibrium path, beliefs are also determined by Bayes’ rule and the players’ equilibrium strategies, where this is possible. Still, in many games this does not impose many restrictions giving rise to a large set of equilibria. Several approaches have been proposed for ruling out unreasonable off-the-equilibrium-path beliefs. Some equilibrium refinements of PBNE restrict the players’ beliefs about moves off the equilibrium path to the set of those types only for which the observed off-equilibrium move could have been worthwhile. In the context of signalling games studied below, the most commonly used refinement is the so-called intuitive criterion. Since we avoid issues of equilibrium selection in this book, we do not describe this or other refinements. Signalling games Signalling games form a class of dynamic games of incomplete information. In signalling games, an informed player takes an action which serves as a signal to an uninformed player: the latter can use the signal to update her beliefs about the informed player’s unknown type. For simplicity, we consider a finite type space &. P1: SFK Trim: 189mm × 246mm Top: 0.393in Gutter: 0.83in AppendixNew cuuk974-Belleflamme 978 0 521 86299 8 September 10, 2014 21:33 687 Further reading The timing of the game is thus as follows. At stage 1, the type θ ∈ & of player 1 is realized with probability ρ(θ); this probability distribution is common knowledge. The realized type θ is privately observed by player 1. At stage 2, player 1 chooses his strategy x1. This is then publicly observed. At stage 3, player 2 updates her beliefs on player 1’s type based on x1 and makes her decision x2. Payoffs are denoted by π i (x1 , x2 , θ ), i = 1, 2. A PBNE in a signalling game consists of player 1’s strategy x1∗ (θ) that assigns a decision x1 to each possible type of player 1, player 2’s strategy x2∗ (x1 ) that assigns a deci- sion x2 to each possible choice of player 2, and posterior beliefs of player 2 µ(θ |x1 ) that assign probabilities to each type for any given choice of player 1, x1. To be a PBNE the following requirements have to be fulfilled: (1) posterior beliefs are a probability distribu- ! tion over types, θ ∈& µ(θ|x1 ) = 1; (2) player 2 maximizes her payoff given her beliefs, ! i.e. x2∗ (x1 ) = arg maxx2 ∈X 2 θ ∈& µ(θ|x1 )π 2 (x1 , x2 , θ ); (3) player 1 maximizes his payoff given player 2’s equilibrium strategy x2∗ (x1 ), i.e. x1∗ (θ) = arg maxx1 ∈X 1 π 1 (x1 , x2∗ (x1 ), θ ); (4) for each choice x1 ∈ X 1 and types that player 2 considers compatible with this choice of player 1, θ ∈ &(x " ), posterior beliefs ρ(θ) are formed according to Bayes’ rule, i.e., ! 1 µ(θ|x1 ) = ρ(θ)/( θ∈&(x " 1 ) p(θ)). In such games we distinguish between two types of PBNE, separating and pooling equilibria (there is possibly a third type, so-called hybrid equilibria, which we do not consider here). A separating equilibrium is such that different types of the informed player send signals from disjoint subsets of the set of available signals. The uninformed player is then able to deduce the informed player’s type based on the signal sent. In contrast, in a pooling equilibrium, all informed player types take the same action. The uninformed player is therefore unable to extract information from this action and does not update her prior beliefs. We analyse signalling games for instance in Part V. Further reading A good introduction into standard concepts of game theory is Gibbons (1992). Also, Mas-Colell, Whinston and Green (1995) provide a good coverage of the standard material. For an advanced treatment, see Fudenberg and Tirole (1991).