Dynamic Games of Complete InformationExtensive form gamesThe Stackelberg gameModel of strategic investmentThe Extensive formExtensive form treesFormalizing the extensive formExampleStrategies & equilibria in extensive formStrategic-form versus extensive-formBackward induction & Subgame perfectionMulti-stage games with observed actionsSlide 13Slide 14Principle of optimality and subgame perfectionRubinstein Bargaining modelSubgame perfect equilibriumSlide 18Slide 19A model of R&D raceThe extensive form of R&D gameSubgame perfect equilibrium of R&D gameDavid vs Goliath in Entry DecisionsSlide 24Slide 25Patent racesAssumptions and preliminariesModel without leapfroggingSketch of proof of Result 1 (contd.):Model with leapfroggingSlide 31Slide 32Slide 33Dynamic Games of Complete Information.Extensive form games•To model games with a dynamic structure•Main issues with a dynamic structure:1. Information structure: who knows what and when?2. Credibility3. Commitment 4. The idea of Backward InductionThe Stackelberg game•A dynamic version of the Cournot game•Player 1, “Stackelberg leader” chooses output q1 first•Player 2, “Stackelberg follower” chooses output q2 next•Demand is linear: p(q)=12-q•Player i’s utility is ui(q1 , q2 )=[12- (q1 + q2)]qi•What is the Stackelberg equilibrium?•Are there other Nash equilibria?Model of strategic investment•Firms 1, 2 have average cost of 2 per unit•Firm 1 can install new technology at cost f. Then average cost is zero•Firm 2 can observe firm 1’s investment•The two firms then move simultaneously to set quantity. Demand is p(q)=14-q•How should firm 1 forecast its rival’s output?•Backward induction not directly applicable. Why?The Extensive form•Building blocks of the extensive form game:1. The set of players2. The order of moves - i.e. who moves when3. The player’s payoffs as a function of moves4. What the player’s choices are when they move5. What a player knows when making his choice6. Probability distribution over any exogenous eventsExtensive form trees•Rules for forming trees1. Single starting point2. No cycles3. One way to proceed•Define precedence relation: a b a precedes b1. ‘ ‘ is asymmetric: a b, means b a2. ‘ ’ is transitive3. x/ x and x// x implies x/ x// or x// x/4. There is single initial node   Formalizing the extensive form 1. Let i єI be the finite set of players2. Let i(x) bet set of players that move at node x3. Let Z be set of terminal nodes. Maps ui:Z→R with values ui(z) are i’s payoffs to a sequence of moves z4. Let A(x) be set of feasible actions at node x5. Information Sets h partition nodes of the tree:a. Each node x is in only one information set h(x)b. If x/єh(x), then player moving at x does not know if he is at x or x/c. If x/єh(x), then the same player moves at x & x/d. If x/єh(x), then A(x) = A(x/). Thus A(h) is action set at information set hExample •Two people want to go to a Broadway musical in great demand•There is exactly one ticket left, and whoever arrives first gets it•There are three transportation choices: c(cab); b(bus); s(subway)•Player 1 leaves home a little earlier•A cab is faster than the subway, which is faster than a busStrategies & equilibria in extensive form•Let Hi be set of player i’s information sets•Let be the set of all actions for i•A pure strategy for i is a map si: Hi → Ai , with si(hi) є A(hi) for all hi є Hi •The set of pure strategies for i is Si=•The number of i’s pure strategies is given by the product•Mixed strategies in extensive form are called behavior strategies. Let ∆(A(hi)) be prob dist on A(hi)A behavior strategy for i, denoted bi, is an element of Cartesian product )(iHhihAAii )(iHhhAii))((##iHhihASii))((iHhhAiiStrategic-form versus extensive-form •Using its pure strategies and payoffs, an extensive form can be transformed to strategic form•Extensive form interpretation: player i waits until hi is reached before deciding how to play there•Strategic form interpretation: player i makes a complete contingent plan in advance•Games of perfect information with all singleton information sets constitute a special class•Any mixed strategy σi (strat form) generates a behavior strategy bi (ext form), but many different σi’s can generate the same bi •Theorem (Kuhn 1953):In a game of perfect recall, mixed and behavior strategies are equivalentBackward induction & Subgame perfection•Theorem (Zermelo 1913; Kuhn 1953)A finite game of perfect information has a pure strategy Nash equilibrium•Subgame perfection is the analog of backward induction for multi-player situations•G is a proper subgame of an extensive form game T if it1. Starts at a single node x of T2. Contains all successors of x3. If x/є G, and x//є h(x/), then x//є G•A behavior strategy σ of an extensive form game is a subgame perfect equilibrium if the restriction of σ to G is a Nash equilibrium of G for every proper subgame GMulti-stage games with observed actions1. There are k stages: 0, 1, …, k-12. All players know the actions chosen at all previous stages3. All players move simultaneously in each stage4. This includes games where players move alternately (all other players have strategy: “do nothing”)Multi-stage games with observed actions•Let a0≡ be the stage-0 action-profile•At the beginning of stage1, players know history h1 which is just a0•Let Ai(h1) be player i’s action set at stage 1 with history h1 • hk+1 is history at end of stage k, hk+1=(a0, a1,… ak), and Ai(hk+1) is player i’s action set at stage k+1 •If game is K stages, HK is set of all ‘terminal histories’•A pure strategy for i is seq. of maps such that where ),...,,(00201 IaaaKkkis0}{)(:kikkiHAHs )()(kiHhkihAHAkk Multi-stage games with observed actions•Payoffs are defined on terminal histories, ui: Hk+1→R•In most applications, payoffs are additively separable over stages. This isn’t necessary•The game from stage k on with history hk is a proper subgame G(hk), and a strategy profile s for whole game induces si│hk for subgame G(hk)•A Nash equilibrium s satisfies the familiar condition ui(si , s-i)≥ ui(s/i , s-i) for all s/i •A Nash equilibrium s is subgame perfect if si│hk is a Nash equilibrium for every subgame G(hk)Principle of optimality and subgame