1Lectures 9 Single deviation-principle&Forward Induction14.12 Game Theory Muhamet YildizRoad Map1. Single-deviation principle – Infinite-horizon bargaining 2. Quiz3. Forward Induction – Examples4. Finitely Repeated Games2Single-Deviation principleDefinition: An extensive-form game is continuous at infinity iff, given any εε> 0, there exists some t such > 0, there exists some t such that, for any two path whose first t acts are the same, that, for any two path whose first t acts are the same, the payoff difference of each player is less than the payoff difference of each player is less than εε..Theorem: Let G be a game that is continuous at infinity. A strategy profile s = (s1,s2,…,sn) is a subgame-perfect equilibrium of G iff, at any information set, where a player i moves, given the other players strategies and given i’s moves at the other information sets, player i cannot increase his conditional payoff at the information set by deviating from his strategy at the information set.Sequential Bargaining• N = {1,2}• D = feasible expected-utility pairs (x,y ∈D )•Ui(x,t) = δitxi• d = (0,0) ∈ D disagreement payoffs11D3Timeline – ∞ periodT = {1,2,…, n-1,n,…}If t is odd,– Player 1 offers some (xt,yt),– Player 2 Accept or Rejects the offer– If the offer is Accepted, the game ends yielding δt(xt,yt),– Otherwise, we proceed to date t+1.If t is even– Player 2 offers some (xt,yt),– Player 1 Accept or Rejects the offer– If the offer is Accepted, the game ends yielding payoff δt(xt,yt),– Otherwise, we proceed to date t+1.SPE of ∞-period bargainingTheorem: At any t, proposer offers the other player δ/(1+δ), keeping himself 1/(1+δ), while the other player accept an offer iff he gets δ/(1+δ).“Proof:”4Nash equilibria of bidding game• 3 equilibria: s1= everybody plays 1; s2= everybody plays 2; s3= everybody plays 3.• Assume each player trembles with probability ε < 1/2, and plays each unintended strategy w.p. ε/2, e.g., w.p. ε/2, he thinks that such other equilibrium is to be played.–s3is an equilibrium iff –s2is an equilibrium iff–s1is an equilibrium iffForward InductionStrong belief in rationality: At any history of the game, each agent is assumed to be rational if possible. (That is, if there are two strategies s and s’ of a player i that are consistent with a history of play, and if s is strictly dominated but s’ is not, at this history no player j believes that i plays s.)5Bidding game with entry feeEach player is first to decide whether to play the bidding game (E or X); if he plays, he is to pay a fee p > 60.10060203-80402--601321BidminFor each m =1,2,3, ∃SPE: (m,m,m) is played in the bidding game, and players play the game iff 20(2+m) ≥ p.Forward induction: when 20(2+m) < p, (Em) is strictly dominated by (Xk). After E, no player will assign positive probability to min bid ≤ m. FI-Equilibria: (Em,Em,Em) where 20(2+m) ≥ p. What if an auction before the bidding game?Burning Money1,30,0S0,03,1BSB0,3-1,0S-1,02,1BSB10DREHTODSDB0S0BSSSBBSBB6Repeated GamesEntry deterrence 1 2EnterX Acc.Fight(0,2) (-1,-1)(1,1)7Entry deterrence, repeated twice12Ent erX Ac c .Fight12Ent erXAcc. Fi ght(1,3) (0,0) (2,2) 12Ent erXAcc.Fight(-1,1)(-2,-2)(0,0)12 Enter X Acc. Fight (-1,1) (1,3) (0,4)Prisoners’ Dilemma, repeated twice, many times• Two dates T = {0,1};• At each date the prisoners’ dilemma is played:• At the beginning of 1 players observe the strategies at 0. Payoffs= sum of stage payoffs.1,16,0D0,65,5CDC8Twice-repeated PD1212121212CDCDCDCDCDCDCDCDCDCDCDCDCDCDC D1010511115665110126617115661207166177122What would happen if T = {0,1,2,…,n}?A general result• G = “stage game” = a finite game• T = {0,1,…,n}• At each t in T, G is played, and players remember which actions taken before t;• Payoffs = Sum of payoffs in the stage game.• Call this game G(T).Theorem: If G has a unique subgame-perfect equilibrium s*, G(T) has a unique subgame-perfect equilibrium, in which s* is played at each