Unformatted text preview:

14.12 G am e Th eory Lecture N otesLectu res 10-11Mu h amet Yildiz1 Repeated GamesIn these notes, we’ll discuss the repeated games, the games where a particular smaller game isrepeated; the small game is called the stage game. The stage game is repeated regardless ofwhat has been played in the previous games. For our analysis, it is important whether thegame is repeated finitely or infinitely many times, and whether the players observe what eachplayer has played in each previous game.1.1 Finitely repeated games with observable actionsWe will first consider the games where a stage game is repeated finitely many times, and at thebeginning of each repetition each player recalls what each player has played in each previousplay. Consider the following entry deterrence game, where an entrant (1) decides whether toenter a market or not, and the incumbent (2) decides whether to fight or accommodate theentrant if he enters. 1 2EnterX Acc.Fight(0,2) (-1,-1)(1,1)Consider the game where this entry deterrence game is repeated twice, and all the previousactions are observed. Assume that a player simply cares about the sum of his payoffsatthestage games. This game is depicted in the following figure.112EnterX Acc.Fight12EnterXAcc. Fight (1,3) (0,0) (2,2) 12EnterXAcc.Fight(-1,1) (-2,-2)(0,0) 12 Enter X Acc. Fight (-1,1) (1,3) (0,4)Note that after the each outcome of the first p lay, the entry deterrence game is played again—where the pa yoff from the first play is added to each outcome. Since a player’s preferencesover the lotteries do not change when we add a number to his utility function, each of the threegames played on the second “day” is the same as the stage game (namely, the entry deterrencegame above). The stage game has a unique subgame perfect equilibrium, where the incumbentaccommodates the entrant, and anticipating this, the entrant enters the market. 1 2EnterX Acc.Fight(0,2) (-1,-1)(1,1)In that case, each of the three games played on the second day has only this equilibriumas its subgame perfect equilibrium. This is depicted in the following.12EnterX Acc.Fight12EnterXAcc. Fight (1,3) (0,0) (2,2) 12EnterXAcc.Fight(-1,1) (-2,-2)(0,0) 12 Enter X Acc. Fight (-1,1) (1,3) (0,4)Using backward induction, we therefore reduce the game to the following.21 2EnterX Acc.Fight(1,3) (0,0) (2,2)Notice that we simply added the unique subgame perfect equilibrium payoff of 1 fromthe second day to each payoff in the stage game. Again, adding a constan t to a player’spayoffs does not change the game, and hence the reduced game possesses the subgame perfectequilibrium of the stage game as its unique subgame perfect equilibrium. Therefore, theunique subgame perfect equilibrium is as depicted below .12EnterX Acc.Fight12EnterXAcc. Fight (1,3) (0,0) (2,2) 12EnterXAcc.Fight(-1,1) (-2,-2)(0,0) 12 Enter X Acc. Fight (-1,1) (1,3) (0,4)This can be generalized. T hat is, given any finitely repeated game with observable actions,if the stage game has a unique subgame perfect equilibrium, then the repeated game has aunique subgame perfect equilibrium, where the subgame perfect equilibrium of the stage gameis player at each day.If the stage game has more than one equilibrium, then in the repeated game we may havesome subgame perfect equilibria where, in some stages, players play some actions that are notplayed in any subgame perfect equilibria of the stage game. For the equilibrium to be playedontheseconddaycanbeconditionedtotheplayonthefirst day, in which case the “ reducedgame” for the first day is no longer the same as the stage game, and thus may obtain somedifferent equilibria. To see this, see Gibbons.1.2 Infinitely repeate d games with observed actionsNow we consider the infinitely repeated games where all the previous moves are commonknowledge at the beginning of each stage. In an infinitely repeated game, we cannot simplyadd the payoffs of each stage, as the sum becomes infinite. For these games, we will confine3ourselves to the case where players maximize the discounted sum of the payoffs from the stagegames. The present value of any given payoff stream π =(π0, π1,...,πt,...) is computed byPV (π; δ)=∞Xt=0δtπt= π0+ δπ1+ ···+ δtπt+ ··· ,where δ ∈ (0, 1) is the discount factor.Bytheaverage value,we simplymean(1 − δ) PV (π; δ) ≡ (1 − δ)∞Xt=0δtπt.Note that, when we have a constant payoff stream (i.e., π0= π1= ··· = πt= ···), the averagevalue is simply the stage payoff (namely, π0). Note that the present and the average valuescan be computed with respect to the current date. That is, given any t, the present value at tisPVt(π; δ)=∞Xs=tδs−tπs= πt+ δπt+1+ ···+ δkπt+k+ ··· .Clearly,PV (π; δ)=π0+ δπ1+ ···+ δt−1πt−1+ δtPVt(π; δ) .Hence, the analysis does not change whether one uses PV or PVt, but using PVtis simpler.The main property of infinitely repeated games is that the set of equilibria becomes verylargeasplayersgetmorepatients,i.e.,δ → 1.givenanypayoff vector that gives each playermore than some Nash equilibrium outcome of the stage game, for sufficiently large values ofδ, there exists some subgame perfect equilibrium that yields the payoff vector at hand astheaveragevalueofthepayoff stream. Thisfactiscalledthefolktheorem. See Gibbonsfor details.In these games, to check whether a strategy profile s =(s1,s2,...,sn) is a subgame perfectequilibrium, we use the single-deviation principle,defined as follows.1Tak e any formation set,wheresomeplayeri is to move, and play a strategy a∗of the stage game according to thestrategy profile s. Assume that the information set is reached, each player j 6= i sticks to hisstrategy sjin the remaining game, and player i will stick to his strategy siin the remaininggame except for the information set at hand. given all these, we check whether the playerhas an incentive to deviate to some action a0at the information set (rather than playing a∗).[Note that all players, including player i, are assumed to stick to this strategy profile in theremaining game.] The single-deviation principle states that if there is no information set the1Note that a strategy profile siis an infinite sequence si=(a0,a1,...,at,...) of functions atdeterminingwhich “strategy of the stage game” to be played at t depending on which actions each player h as taken in theprevious p lays of the stage game.4player has an incentive to deviate in this sense, then the strategy profile is a


View Full Document

MIT 14 12 - Game Theory Lecture Notes

Download Game Theory Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Game Theory Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Game Theory Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?