1Recap! Last class (January 20, 2004)! Duopoly models! Multistage games with observed actions! Subgame perfect equilibrium! Extensive form of a game! Two-stage prisoner’s dilemma! Today (January 22, 2004)! Finitely repeated games! Infinitely repeated games! Prisoner’s dilemma! Friedman’s Theorem! Repeated Cournot gameRepeated gamesgames. stage T the from payoffs theof sum d)(discounte theare G(T)for payoffs The begins.play next thebefore observed plays preceding all of outcomes with the times,T played isG in which thedenote G(T)let G, game stage aGiven game. repeated theof theG call We).,...,( ..., ),,...,( payoffs receive and ,..., spacesaction from ,..., actions their chooseously simulatene ..., 1, playersin which n informatio complete of game static a denote } ..., , ;,...,{GLet 1n1111n11gamerepeated finitelystage gameaaaaAAaanAAnnnnn•=•ππππ2Repeated games! Result: If the stage game G has a unique Nash equilibrium then for any finite T, the repeated game G(T) has a unique subgame-perfect outcome: the Nash equilibrium of G is played in every stage.Example3, 30, 00, 0R0, 04, 40, 5M0, 05, 01, 1LRMLPlayer 1Player 2! The stage game is played twice! The first-stage outcome is observed before the second stage begins3Example3, 30, 00, 0R0, 04, 40, 5M0, 05, 01, 1LRMLPlayer 1Player 2! Partial strategy for stage 2:! Play R in stage 2 if stage 1 outcome is (M,M); otherwise, play L in stage 2.Example4, 41, 11, 1R1, 17, 71, 6M1, 16, 12, 2LRMLPlayer 1Player 2! Modified stage 1 game! Subgame perfect equilibria:[(L,L),(L,L)] [(M,M),(R,R)] [(R,R),(L,L)]4Observation! Let G be a static game of complete information with multiple Nash equilibria. There may be subgame-perfect outcomes of the repeated game G(T) in which for any t <T, the outcome in stage tis not a Nash equilibrium of G. Definitions! In the finitely repeated game G(T), a player’s strategyspecifies the player’s actions in each stage, for each possible history of play through the previous stages.! In the finitely repeated game G(T), a subgamebeginning at stage t+1 is the repeated game in which G is played T-t times, denoted by G(T-t).5Example ! All possible outcomes (histories) at the end of stage 1:(L,L) (L,M) (L,R) (M,L) (M,M) (M,R) (R,L) (R,M) (R,R)! (M, L, L, L, L, R, L, L, L, L)Play M in the first stage; Play L in the second stage unless the first stage outcome is (M,M) 3, 30, 00, 0R0, 04, 40, 5M0, 05, 01, 1LRMLPlayer 1Player 2Infinitely Repeated Prisoner’s Dilemma! The game is repeated infinitely! For each t, the outcomes of the previous t-1 stage games are observed! Payoffs?1, 15, 0 D0, 54, 4CD (defect)C (cooperate)Prisoner 1Prisoner 26Discounted payoffs! Let δ be the value today of a dollar to be received one stage later! E.g., δ=1/(1+r) where r is the interest rate per stage! Given the discount factor δ the present value of the infinite sequence of payoffs π1, π2, π3, … isπ1+ δπ2+ δ2π3+ … = ∑t=1→∞δt-1πt .Discounted payoffs! Suppose after each stage is played, the game continues to the next stage with probability 1-p and stops with probability p. ! Expected present value of next stage’s payoff(1-p)π/(1+r).! Expected present value of the payoff two stages later(1-p)2π/(1+r)2.! Let δ= (1-p)/(1+r)! π1+ δπ2+ δ2π3+ … reflects the time value of money and the possibility that the game will end7Average payoffs! V = π1+ δπ2+ δ2π3+ … = ∑t=1→∞δt-1πt ! If we received an “average” payoff of π in every stage, thenV = π+ δπ+ δ2π+ … = π(1+ δ+ δ2+ … )= π/(1- δ)! π/(1- δ) = ∑t=1→∞δt-1πt .π = (1- δ) ∑t=1→∞δt-1πt .Example: Payoffs 4 4 4 4 4 ….Average payoff = 4 Net present value = 4/ (1- δ) Infinitely repeated gamesgames. stage of sequence infinite thefrom payoffs splayer' theof luepresent va theis ),G(in payoff splayer'Each begins. stage thebefore observed are game stage theof plays preceding 1 theof outcomes the,each For .factor discount share players theandforever repeated isG in which thedenote ),G(let G, game stage aGiven thδδδ∞∞•tt-tamerepeated ginfinitely8Infinitely Repeated Prisoner’s Dilemma! Strategy:Play C in the first stage. In the tthstage, if the outcome of all t-1 preceding stages has been (C,C), then play C; otherwise, play D1, 15, 0 D0, 54, 4CD (defect)C (cooperate)Prisoner 1Prisoner 2Definitions! In an infinitely repeated game G(∞,δ), a player’s strategyspecifies the player’s actions in each stage, for each possible history of play through the previous stages.! In the infinitely repeated game G(∞,δ), each subgamebeginning at stage t+1 is is identical to the original game G(∞,δ).9Trigger strategies for Prisoner’s Dilemma! Assuming player 1 adopts the trigger strategy, what is the best response of player 2?Player 2 best response in stage t+1:! If the outcome in stage t is (D,D) ! Play D forever! If the outcomes of stages 1,…,t are (C,C)! Play D → receive 5 in this stage, switch to (D,D) forever after → 5 + δ.1 + δ2.1+ δ3.1+…=5+ δ/(1- δ)! Play C → receive 4 in this stage, and face the exact same game (same choices) in stage t+2!Trigger strategies for Prisoner’s Dilemma! Let V be the payoff of player 2 from making the optimal choice in the subgame starting in stage t+1, given that the outcomes in the previous stages have been (C,C)! Play C → V=4+ δV → V = 4/(1- δ)! Play D → V= 5+ δ/(1- δ)Play C if 4/(1- δ) ≥ 5+ δ/(1- δ) → if δ≥1/410Trigger strategies for Prisoner’s Dilemma! Two types of subgames:(i) Subgames where the outcomes of all previous stages have been (C,C)The trigger strategies are Nash equilibrium for this class of subgames, as well as for the original game.(ii) Subgames where the outcome of at least one earlier stage differs from (C,C)Player’s strategies are to repeat (D,D) forever, which is also a Nash equilibrium for the original gameObservation! Even if the stage game G has a unique Nash equilibrium, there may be subgame-perfect outcomes of the infinitely repeated game in which no stage’s outcome is a Nash equilibrium of G.11Feasible payoffsin the stage game! The payoffs (π1, π2, … , πn) are feasiblein the stage game G if they are a convex combination of the pure-strategy payoffs of G.Example! What are the pure-strategy payoffs?! (4,4) (0,5) (5,0) (1,1)1, 15, 0 D0, 54, 4CD (defect)C (cooperate)Prisoner 1Prisoner 212Feasible payoffs in the