14.770 Recitation 5 Notes

14.770 Recitation 5 Notes Today: A review of dynamic games, with: • A formal definition of Subgame Perfect Equilibrium, • A statement of single-deviation principle, and, • Markov Perfect Equilibrium. Why? Next week we’ll start covering models on policy determination (legislative bargaining, political compromise etc.) and those models are dynamic – they heavily rely on SPE and punishment strategies etc. Understanding them will be useful! Also, the models in last lecture (divide-and-rule and politics of fear) use Markov Perfect Equilibrium, so it’s helpful to review those. Consequently, this recitation will be mostly about game theory, and less about political economy. Indeed, this document is based on the lecture notes I typed up when I was TAing for 14.122 (Game Theory) last year. There exists another document in titled “A Review of Dynamic Games” – which more or less covers the same stuff, but some in greater detail and some in less.1 Here, I’ll try to be more hands-on and go over some basic concepts via some illustrations. Some good in-depth resources are Fudenberg and Tirole’s Game Theory and Gibbons’ Game Theory for Applied Economists. Extensive Form Games: Definition and Notation Informally, an extensive form game is a complete description of: 1. The set of players. 2. Who moves when, and what choices they have. 3. Players’ payoffs as a function of the choices that are made. 4. What players know when they move. I provide a formal definition of a finite extensive form game with perfect information (i.e. observed actions) below, but a similar definition applies to infinite horizon games, or games with imperfect information, as well. Definition 1. A finite extensive form game with perfect information consists of 1 The notation used here differs from the one in the other document – sorry. 1 1. A finite set I of players, / Z: 2. A finite set T of nodes that form a tree2 along with functions giving for each nonterminal node t ∈ (a) i(t): the player who moves, (b) A(t): the set of possible actions, (c) n(t, a): the successor node resulting from each possible action. 3. Payoff functions ui : Z → R, i.e. mapping from terminal nodes to the real numbers. This is too notation heavy for our purposes, and you shouldn’t worry about it too much. Most of the notation is there because it helps us define the strategy space. Given an extensive form game, define Hj := {t ∈ T such that i(t) = j}. This is the set of nodes (or histories, you may read) where j is called to move. Write Aj := ∪s∈H(j) A(s) Definition 2. A pure strategy for player j in an extensive form game with perfect information is a function sj : Hj → Aj such that sj (h) ∈ A(h) for all h ∈ Hj . Note: A strategy is a complete contingent plan specifying what a player will do in any situation (history) that arises. Subgame Perfect Equilibrium What’s a “subgame” anyway? Definition 3. Let G = (I, T, Z, i, A, n, u) be an extensive form game. A subgame G0 = (I 0 , T 0 , Z 0 , i0 , A0 , n0 , u0 ) consists of 1. I 0 = I 2. T 0 ⊂ T consists of a single nonterminal node and all of its successors. 3. All functions (i0 , A0 , n0 , h0 , u0 ) are exactly as in G but restricted to the appropriate domain given by T 0 . We’re now ready to define what a SPE is. Definition 4. A strategy profile s∗ is a Subgame Perfect Equilibrium (SPE) if the restriction of s∗ to G0 is a Nash Equilibrium of G0 for every subgame G0 of G. I’ll not have time to discuss why this is an appropriate solution concept here – you can refer to the in-depth resources I listed above if interested. Infinite Horizon Games Ok, the above discussion was useful in terms of visualizing what a subgame is, but you should’ve realized that most of the examples we covered in class are infinite horizon games. In such games, drawing the game tree and finding all the subgames is a cumbersome task. To make it more tractable, we’ll place more structure on the game, and focus on infinite horizon multistage games with observed actions. 2 The notion of forming a tree leaves out cyclicities among nodes, etc. 2 Definition 5. An infinite horizon multistage game with observed actions is an extensive form game where: • At stage t = 0, 1, 2, ... some subset of players simultaneously choose actions. • All players observe stage t actions before choosing stage t + 1 actions. • Players’ payoffs are some function of the action sequence: ui (a0 , a1 , ...). It is often the case that that player i’s payoffs are some discounted sum, i.e. they are of the form: ui (si , s−i ) = ui0 (si , s−i ) + δui1 (si , s−i ) + δ 2 ui2 (si , s−i ) + . . . where uit (si , s−i ) is a payoff received at t when the strategies are followed. Interpretation of δ 1. Interest rate: δ = Two possible interpretations of the discount rate is: 1 1+r 2. Probabilistic end of the game: suppose game is finite, but that the end is not deterministic. Instead, given that stage t is reached, there is probability δ that stage t + 1 will be reached. Note that the structure we place on these games makes the definition of a subgame easier. A subgame in this context is simply: the game played after a stage, following some history. A history ht , on the other hand, is just the list of actions taken up until this point: ht = (a0 , a1 , . . . , at ) Here are two canonical examples of the games in this form: Example 1. Repeated Game. Let G be a simultaneous move game with finite action spaces A1 , A2 , . . . , AI . The infinitely repeated game G∞ is the game where in periods t = 0, 1, 2, . . . the players simultaneously choose actions (at1 , . . . , atI ) after observing all previous actions. We define payoffs in this game by: ui (si , s−i ) = ∞ X δ t gi (at1 , . . . , atI ) t=0 where (at1 , . . . , atI ) is the actions taken in period t when players follow strategies s1 , . . . , sI . Example 2. Bargaining Game. Suppose a prize worth of $ 1 is to be divided between two players. The following procedure is used: 1. At t = 0, 2, 4, ... Player 1 proposes a division (x1 , 1 − x1 ). Player 2 then says yes or no. If yes, the game ends. Otherwise, continue. 2. At t = 1, 3, 5, ... Player 2 proposes (1 − x2 , x2 ). Player 1 says yes or no. Assume that if (y, 1 − y) agreed to at period t, payoffs are: δ t y and δ t (1 − y). Analysis of Infinite Horizon Games Now that we have a tractable structure, we can find all the subgames of an infinite horizon multistage game with observed action and find the SPE. It turns out this still isn’t very easy: There are infinitely many subgames and uncountably many strategies that might do better. 3 Soon, we’ll discuss a theorem which substantially simplifies the analysis in most infinite horizon games. We first need a definition. Definition 6. An infinite horizon game G is continuous at ∞ if lim sup |ui (s) − ui (s0 )| = 0 T →∞ i,s,s0 s.t. s(ht ) = s0 (ht ) ∀t ≤ T Essentially, this means that distant future events have a very small effect on payoff. This is satisfied in a standard game with discounting and bounded payoffs. For instance, repeated games (with bounded stage game payoff) and the bargaining game are continuous at ∞. Virtually in all the models we cover in this class, this condition is satisfied. It is violated by no discounting, or some payoff function or technology that allows potentially unbounded payoffs. Now, some notation. Definition 7. Write ui (si , s−i |ht ) for the payoff ui (s̃i , s̃−i ), where (s̃i , s̃−i ) are played to reach some history ht , and then (si , s−i ) are followed at later stages. One interpretation for ui (si , s−i |ht ) is the payoff of player i from (si , s−i ) conditional on ht being reached. Note the following observation, which follows from the definition of SPE: s∗ is a SPE iff ui (s∗ |ht ) ≥ ∗ ui (s0i , s−i |ht ) for all i and for all ht that start a subgame. We’re now ready to present the theorem justifying the one-stage deviation principle. Theorem 1. Suppose G is an infinite horizon extensive form game with observed actions that is continuous at ∞. A strategy profile s∗ is a SPE if and only if @ht and ŝi differing from s∗i only in play of i at ht with ui (ŝi , s∗−i |ht ) > ui (s∗ |ht ) Note the strength of this theorem: recall that we had argued that the main difficulty of infinite horizon games is that there are uncountably many deviations to check. This theorem says that in many games, it suffices to check deviations at single stages, rather than checking other complicated deviations. Thanks to this theorem, the only types of deviations we need to check are the ones where player i says: “Let me deviate from s∗i only once right now, and then go back to playing according to s∗i .” Without this theorem, we would also need to check deviations like: “Let me deviate from si∗ only once seven periods from now on, and then twelve periods from now on, etc.” That’s a very onerous task! Below is the proof – you don’t need to know it by heart (presented here just for the sake of completeness), but you should keep the basic intuition in mind: Keep other players’ strategies fixed. If you can find a profitable deviation, you should be able to find a one-stage deviation as well. This is more or less the same idea with principle of optimality from dynamic programming – the idea which gives way to the recursive formulation. Proof. ( =⇒ ) direction is obvious: if there is some profitable deviation from s∗ , clearly, s∗ cannot be a SPE. ( ⇐= ) direction is more interesting. We need to show that not being able to find one-stage deviations is sufficient to ensure that s∗ is a SPE. Assume that s∗ satisfies the no-single deviation property. We need to ∗ show that ui (s∗ |ht ) ≥ ui (s0i , s−i |ht ) for all i and for all ht that start a subgame. We will show this by covering two cases: (1) the case where the s0i differs from s∗i in a finite number of stages, (2) the case where s0i differs from si∗ in an infinite number of stages. 4 Step 1. Suppose s∗i and s0i differ only in T stages. We’ll prove the result by induction on T . Base Step. Assume s∗i and s0i differ only in period t0 . Consider an information set ht . ∗ • If t0 < t then ui (s∗i , s∗−i |ht ) = ui (s0i , s−i |ht ), since they only differ on things that happen before stage t. • If t0 ≥ t then ∗ ui (s0i , s−i |ht ) = X = X ≤ X 0 0 0 0 0 0 ∗ ∗ Pr{ht |ht , si0 , s−i }ui (si0 , s−i |ht ) ht0 ∗ Pr{ht |ht , s∗i , s−i }ui (s0i , s∗−i |ht ) ht0 ∗ ∗ Pr{ht |ht , s∗i , s−i }ui (si∗ , s−i |ht ) ht0 = ∗ ui (s∗i , s−i |ht ). Where the first equality follows by definition, the second equality follows because s0i and s∗i are the same in periods before t0 (which implies that they give the same probability of reaching to a 0 history ht ), and the inequality follows due to the running hypothesis that s∗ satisfies the no-single deviation property. Inductive Step. Assume the result holds for strategies that differ in T periods. Let s0i be any strategy differing from si∗ in T + 1 periods. Let t0 denote the last period at which they differ, and define s̃i by: ( si0 (ht ) if t < t0 s̃i (h ) = s∗i (ht ) if t ≥ t0 t For any ht , we have: ∗ ui (s0i , s−i |ht ) ≤ ui (s̃i , s∗−i |ht ) ≤ ui (s∗i , s∗−i |ht ) where the first inequality comes from an argument identical to the one made in T = 1 case and the second inequality follows from inductive hypothesis. The induction is therefore complete, and so is the proof for Step 1. Step 2. Suppose s0i differs from si∗ in an infinite number of periods. Suppose, to get a contradiction, that there exists an information set ht (which is an initial node of a subgame) such that ∗ ui (s0i , s−i |ht ) > ui (s∗ |ht ) Clearly, we can find an  > 0 such that ∗ ui (s0i , s−i |ht ) > ui (s∗ |ht ) +  (1) Since G is continuous at ∞, we can find a T such that |ui (s0 ) − ui (s00 )| <  whenever s0 and s00 differ only after first T periods. Let s̃i be the strategy with ( s0i (ht ) if t < T t s̃i (h ) = s∗i (ht ) if t ≥ T Then we have: ∗ ∗ ui (s̃i , σ−i |ht ) > ui (s0i , s−i |ht ) −  > ui (s∗ |ht ) 5 where the first inequality follows because s̃i and s0i differ only after the first T periods, and the second inequality follows by Equation (1). But this contradicts the conclusion of Step 1, because s̃i differs from s∗i in a finite number of periods. Since we have covered both steps, which consider exhaustive cases, the result follows. Example: Bargaining Game To illustrate the use of one-stage deviation principle and to show the power of SPE in one interesting model, we now return to the bargaining model discussed earlier. We will show that SPE provides quite sharp predictions for this game. Claim 1. In Bargaining Game, a SPE is: s∗i (ht ) = ( s∗i (ht ) = yes no 1 1+δ at all proposal nodes δ if offered at least 1+δ at all response nodes δ if offered less than 1+δ Proof. Remember that Bargaining Game is continuous at ∞. Therefore, using Theorem 1, we just need to show ∗ ui (s∗i , s−i |ht ) ≥ ui (s0i , s∗−i |ht ) whenever s0i differs only at ht . • Case 1: ht is a proposal node, so ∗ ui (s∗i , s−i |ht ) = δt . 1+δ If s0i differs at ht then ( ∗ ui (s0i , s−i |ht ) = δ 1 δ t+1 1+δ if s0i (ht ) > 1+δ t 0 t δ × less if si (h ) is less than 1 1+δ . • Case 2: ht is a response node where y was offered. 1 If response is yes, then δ t y is the payoff. If response is no then δ t+1 1+δ . If y ≥ δ ∗ t is optimal. If y < 1+δ then si (h ) = no is optimal. δ 1+δ then si∗ (ht ) = yes The result follows. This proposition is useful and illustrates the strength of Theorem 1, but what about other SPE? Below, we show that the SPE we characterized above is unique. It also illustrates another interesting technique: a non-constructive proof of uniqueness by conducting the analysis in the payoff space instead of strategy space. We’ll cover this in next Monday’s class, but it never hurts to cover it earlier, right? Claim 2. In the Barganing Game, in any SPE, Player 1 receives a payoff of δ payoff of 1+δ 1 1+δ and Player 2 receives a Proof. Suppose v and v̄ are the smallest and largest possible payoffs for a Player 1 (the first proposer) in a SPE. Some observations: 1. 0 ≤ v ≤ v̄ ≤ 1. By construction. 2. 1 − v̄ ≥ δv. This is because Player 2 can always reject the offer and propose in the next round, in which she gets at least δv. This implies that Player 1 must leave at least δv to Player 2 when she proposes. 6 3. v ≥ 1 − δv̄. This is because if the game advances to the next round, Player 2 will at most get δv̄. Thus, any offer giving Player 2 δv̄ +  must be accepted. Therefore, Player 1 can ensure a payoff of at least 1 − δv̄ −  for any . If you draw the set of all points that satisfy all three inequalities, you’ll see that v = v̄ = 1 1+δ . 1 This concludes the proof that the proposing player must get 1+δ in every subgame in a SPE. Incidentally, this is also the payoff that Player 1 receives in the SPE we constructed earlier. Note that the extremely strong predictive power of SPE in Bargaining Game depends on a few critical assumptions. If, for instance, there was simultaneous proposals by both players, then any division (x, 1 − x) is a SPE. The predictions also would not extend to the case of more than two players: in such a case, the predictive power of SPE drops significantly. Markov Perfect Equilibrium The Markov Perfect Equilibrium (MPE) concept is a drastic refinement of SPE developed as a reaction to the multiplicity of equilibria in dynamic problems. (SPE doesn’t suffer from this problem in the context of a bargaining game, but many other games -especially repeated games- contain a large number of SPE.) Essentially it reflects a desire to have some ability to pick out unique solutions in dynamic problems. Payoff-Relevant Variables After seeing examples where SPE lacks predictive power, people sometimes start to complain about unreasonable “bootstrapping” of expectations. Suppose we want to rule out such things. One first step to developing such a concept is to think about the minimal set of things we must allow people to condition on. Often, there is a natural set of payoff-relevant variables. Example 3. Exploitation of Common Resource. • Two fishermen choose quantities (q10 , q20 ), (q11 , q21 ), ..., (q1t , q2t ). • Stock of fish grows by St+1 = (1 + g)(St − (q1t + q2t )) • Price is pt = P (q1t + q2t ) 7 With unrestricted strategy spaces, anything could happen with patient agents. This is because either fisherman can fish to extinction in the next period, and construct an equilibrium using it as a threat point. On the other hand, Markov approach allow qit to depends only on St , and not on how we got there. Clearly we would like a solution concept that eliminates such punishments, and have a solution more like a “repeated static NE”. Definition, Notation and Examples Let G be a multistage game with observed actions, i.e. at time t = 0, 1, 2, . . . some subset of players simultaneously choose actions and all previous actions are observed before these choices are made. 0 0 Definition 8. Period t histories ht and (h0 )t are said to be Markov equivalent, ht ∼ (h0 )t , if for any ∞ two action sequences {αs }∞ s=0 and {βs }s=0 of present and future action profiles and for all i: 0 0 gi (ht , {αs }) ≥ gi (ht , {βs }) ⇐⇒ gi ((h0 )t , {αs }) ≥ gi ((h0 )t , {βs }). Intuitively, two histories are Markov equivalent when the relative preferences over future actions are identical. Note that we allow payoffs to be scaled differently but want decision making to be the same. Some examples: 0 • In the common resource game, any two histories ht , (h0 )t with the same number of fish (St = St00 ) are Markov equivalent. • In a repeated game, any two histories are Markov Equivalent. • In the divide-and-rule model, any two histories which end up with the same state (K or D) are Markov equivalent. Indeed, in almost all of the dynamic game models we covered in class, the definition of what a state is will be obvious. Let H = ∪t Ht and Ai = ∪t Ait . Recall that a strategy is a function si : H → Ai . Definition 9. A Markov strategy is a function si : H → Ai such that 0 si (ht ) = si ((h0 )t ) 0 whenever ht ∼ (h0 )t . Definition 10. A Markov Perfect Equilibrium of G is a SPE of G in which all players use Markov strategies. Note that an effect of this refinement is: it declares past to be irrelevant as long as present value of payoffrelevant variables to be the same. This essentially eliminates the effect of punishments. Here’s an existence result: Proposition 1. A MPE exists in any finite multistage game with observed actions, and in infinite horizon games whose payoffs are continuous at ∞. And here’s another result which (in a loose sense) suggests that Markov strategies are self-enforcing: 8 Proposition 2. If all other players use Markov strategies, then the remaining player has a Markov strategy among her (unrestricted) best responses. This result holds because when the other players are not conditioning on irrelevant things (past play), then you do not have to condition on irrelevant things either. Does MPE fix the problems we started with? • In some cases, yes. For instance, for a repeated game, Markov Perfect Equilibria are NE for the static game, repeated each period. • Similarly, in the divide-and-rule model there are many SPE (where the ruler can condition punishments on the past behavior) but a unique MPE. • In other cases, it may be tricky. For instance, in the common resources game, if the stock of fish grows in a deterministic manner, then one can still do punishments (e.g. “if number of fish is not exactly 137 we’ll catch everything tomorrow.”) Putting some noise in the stock of fish sometimes fixes this, but there is no general rule which asserts that it always will. In a (totally unrelated) note: 9