Dynamic Games
 14 minutes read  2906 wordsContext
 Strategic interactions and social dilemmas can sometimes be understood in terms of oneshot sandbox cases. In such settings, where time is neglected, promises, threats, and reputation play no role.
 However, players have many additional strategies available whenever there is a future, and they can use promises and threats to achieve very different outcomes compared to the atemporal cases.
 How does time affect the outcomes of social interactions?
 Why is reputation important whenever time is involved?
 How can players incorporate time into their strategies?
Course Structure Overview
Lecture Structure and Learning Objectives
Structure
 Buying an Empire (Case Study)
 Repeated Games
 Sequential Games
 Backward Induction and Subgame Perfect Equilibria
 Current Field Developments
Learning Objectives
 Illustrate the relevance of time in social interactions.
 Explain how incorporating time can affect the results of interactions.
 Describe the role of backward induction when analyzing dynamic interactions.
 Illustrate the concept of subgame perfect equilibrium in dynamic settings.
 Explain how move order and patience affect the bargaining power of interacting agents.
Buying an Empire
 Auctions are typical examples of economic interactions studied by game theory.
 One of the most significant historical auctions took place in 193 AD.
 The auction for the throne of an empire!
The Praetorian Guard
 The Praetorian guard was an elite unit of the Roman army.
 The guards were placed in Rome, mostly serving as bodyguards and spies of Roman emperors.
 Over the years, the Praetorian guard became very influential in Roman politics.
 On some occasions, they had overthrown emperors and proclaimed their successors.
The Palace Intrigues
 Commodus was the Roman emperor from 176 to 192 AD.
 He was assassinated in 192 AD by a wrestler in a bath.
 The assassination conspiracy was directed by one of his most trusted Praetorians, Quintus Aemilius Laetus.
 Pertinax, who was also a conspirator, ascended to power and paid the Praetorian guards \(3000\) denarii premium.
The Roman Empire up to Auction
 Pertinax was assassinated three months later by a group of guards!
 The Praetorian guards put the empire up to auction, taking place at the guards’ camp.
 The throne was to be given to the one who paid the highest price.
 Titus Flavius Claudius Sulpicianus, Pertinax’s fatherinlaw, made offers for the throne (in the camp).
 Didius Julianus arrived at the camp finding the entrance barred.
 He started shouting out offers to the guards.
Hail to the Highest Bidder
 The auction lasted for hours.
 In the end, Sulpicianus promised \(20000\) sesterces (\(5000\) denarii) to every soldier.
 Julianus then offered \(25000\) sesterces (\(6250\) denarii)
 The guards closed the deal with Julianus.
 They opened the gates and proclaimed Julianus as emperor.
But what evil have I done?
 Julianus ruled for \(66\) days!
 He was very unpopular with the Roman public because he acquired the throne by paying instead of conquering it.
 He was killed in the palace… by a soldier.
 His last words were: “But what evil have I done? Whom have I killed?”
Repeated Games
 Repeated games are games played on a finite or infinite number of dates, and at each date, the same strategic interaction is repeated.
 The repeated strategic interaction at each date is called a stage game.
 When there is a future, threats and promises can be used to sustain cooperation.
 Nevertheless, this can only happen if threats and promises are credible.
Prisoner’s Dilemma
 Consider the static prisoner’s dilemma again.
 There is a unique Nash equilibrium in which players do not coordinate (i.e., they both confess).
 Can this change if the game is repeated?
Repeated Prisoner’s Dilemma
 Suppose that the static prisoner’s dilemma is used as the stage game of a repeated game with an infinite time horizon.
 The payoff of all future dates is discounted by \(0 <\delta < 1\).
Non Coordinating Equilibrium
 One equilibrium is to play the stage game’s Nash equilibrium at each date.
 Player \(i\) gets a payoff of \(3\) at each date, so
\[u_{n,i} = \sum_{t=0}^{\infty} \delta^{t}(3)=\frac{3}{1\delta}\]
Trigger Strategies
 A trigger strategy is a strategy, where at each iteration of a repeated game an action is selected based on the coordination state of the game. If all players coordinated in the past then a coordinating action is chosen for the current iteration. Instead, past defections trigger players to choose punishing actions for the current iteration.
 Trigger strategies can be further specified as
 Grim trigger strategies, where the punishment continues indefinitely after a player defects.
 Tit for tat strategies, where the punishment is only applied for a limited number of dates after a defection.
Coordination in Prisoner’s Dilemma
 Players can coordinate by using trigger strategies.
 If at all previous dates the other player has denied, then deny. Otherwise, confess.
 If players coordinate, then each gets a payoff of \(1\) at each date, thus
\[u_{c,i} = \frac{1}{1  \delta}\]
Can Coordination be Supported?
 If player \(i\) deviates at the current date, then her payoff at the current date is \(0\).
 At every subsequent date, her payoff is \(3\), because her past deviation triggers the other player’s punishment.
 Therefore,
\[u_{d,i} = 3\frac{\delta}{1  \delta}\]
 Coordination can be supported if such a deviation is not profitable, i.e.
\[u_{c,i} \ge u_{d,i} \iff \delta \ge \frac{1}{3}\]
 As long as players are patient enough, the underlying threats of trigger strategies make coordination feasible.
Sequential Games
 A game is called sequential if its players play sequentially instead of simultaneously.
 Nash equilibria also exist in such games.
 We can find some of them using backward induction.
 The best action of the player that acts at the last date is calculated.
 Given this best response, the best action of the player that acts at the previous to last date is calculated.
 We continue in this fashion until we have calculated the best action of the player who acts at the initial date.
Backward Induction
 \(SPE = \left\{ \left\{Bottom, \left(Left’, Right \right)\right\}, \left\{Bottom, \left(Right’, Right \right)\right\}\right\}\)
Subgame Perfect Equilibria
 A subgame of a dynamic game is the restriction of the game starting from a particular decision node and including all subsequent decision nodes and branches (actions) of the original game.
 A collection of strategies, one for each player, such that its restriction to each subgame of the original game constitutes a Nash equilibrium of this subgame is called subgame perfect equilibrium.
 This implies that the past does not matter in optimal decisions once a decision node is reached.
 Equilibria of this type are typically abbreviated as SPE.
 Backward induction can be used to calculate subgame perfect equilibria.
Bargaining
 A process through which two or more people decide how to share a surplus is called cooperative bargaining (or simply bargaining).
 Players negotiate how to divide the surplus (a value) in one or more rounds.
Take it or Leave it Game
 There are two players negotiating how to share a surplus of unit value.
 Player \(A\) moves first and makes an offer \(x\in[0,1]\).
 Player \(B\) moves second and decides whether to accept or reject the offer.
 If the offer is accepted, player \(A\) gets \(x\), and player \(B\) gets \(1x\).
 If the offer is rejected, both players get zero.
First Move Advantage
 Player \(B\) accepts if \(1x \ge 0\) or, equivalently, if \(x\le 1\).
 Player \(A\) offers \(x = 1\).
CounterProposal
 Suppose that player \(B\) can make a counteroffer.
 She can offer \(y\in[0,1]\) if she rejects the offer of player \(A\).
 If the counteroffer is accepted, player \(A\) gets \(1y\), and player \(B\) gets \(y\).
 If the counteroffer is rejected, both players get zero.
Last Offer Advantage
 Player \(A\) accepts the counteroffer if \(1y \ge 0\) or, equivalently, if \(y\le 1\).
 Player \(B\) offers \(y = 1\).
 Player \(B\) accepts the first offer if \(1x \ge y = 1\) or , equivalently, if \(x \le 0\).
 Player \(A\) offers \(x = 0\).
Alternating Offers
 Suppose that the counterproposal game is infinitely repeated until a deal is reached.
 Every time a player rejects an offer, she makes a counteroffer.
 Players discount every offerround with factors \(\delta_{A},\delta_{B}\in[0,1)\).
A Recursive Equilibrium
 Suppose the game is at date \(t\) and player \(B\) makes an offer.
 Player \(A\) accepts if \(y\le 1\), so player \(B\) offers \(y=1\).
 At date \(t1\), player \(B\) accepts if \(x\le 1\delta_{B}\), so player \(A\) offers \(x=1\delta_{B}\).
 At date \(t2\), player \(A\) accepts if \(y\le 1  \delta_{A} + \delta_{A}\delta_{B}\), so player \(B\) offers \(y=1  \delta_{A} + \delta_{A}\delta_{B}\).
 Recursively, one can show that player \(A\) offers
\[x = \frac{1\delta_{B}}{1\delta_{A}\delta_{B}}.\]
The Role of Impatience
 If player \(A\) becomes more patient (\(\delta_{A}\ \uparrow\))
 she is more willing to postpone acceptance for the next date
 player \(B\) loses bargaining power
 player \(A\) gets a greater part of the surplus (\(x\ \uparrow\))
 If player \(B\) becomes more patient (\(\delta_{B}\ \uparrow\))
 she is more willing to postpone acceptance for the next date
 player \(A\) loses bargaining power
 player \(A\) gets a smaller part of the surplus (\(x\ \downarrow\))
Current Field Developments
 Much of modern work in game theory is dynamic.
 The folk theorem is a fundamental theoretical result stating that in infinitely repeated games, any feasible payoff vector can be achieved by a subgame perfect equilibrium if players are sufficiently patient.
 Since its development (Friedman, 1971), much subsequent work has focused on equilibrium refinements that give stricter predictions.
 Another active area of work in game theory focuses on extensions of preferences of players that include behavioral traits (e.g., regret, cognitive costs, etc.).
Comprehensive Summary
 Time is of the essence in strategic interactions.
 Many outcomes of simultaneous interactions can be overturned when time is taken into account.
 If there is a future, coordination can be supported even in cases when the corresponding simultaneous interaction results in non coordination (i.e. the prisoners’ dilemma).
 Patience is central in determining what types of coordination can be achieved and how the coordination gains can be split.
 Players can use strategies involving threats and promises to induce coordination.
 Nevertheless, these promises and threats have to be credible.
 The subgame perfect equilibrium is a refinement of the Nash equilibrium accounting for credibility issues.
Further Reading
Exercises
Group A

Consider a twoplayer game in which, at date \(1\), player \(A\) selects a number \(x>0\), and player \(B\) observes it. At date \(2\), simultaneously and independently, player \(A\) selects a number \(y_{A}\) and player \(B\) selects a number \(y_{B}\). The payoff functions of the two players are \(u_{A} = y_{A} y_{B} + x y_{A}  y_{A}^{2}  \frac{x^{3}}{3}\) and \(u_{B} = ( y_{A}  y_{B} )^{2}\). Find all the subgame perfect Nash equilibria.
We find the subgame perfect equilibrium using backward induction. At the last date, player \(B\) solves \[\max_{y_{B}} \left\{(y_{A}y_{B})^{2}\right\}\] and gets the best response \(y_{B}(y_{A})=y_{A}\). At the same date, player \(A\) solves \[\max_{y_{A}} \left\{y_{A}y_{B} + x y_{A}  y_{A}^{2}  \frac{x^{3}}{3}\right\}\] to get the best response \(y_{A}(y_{B};x)=x\). Solving the system of best responses, we find that \(y_{A}^{\ast}=y_{B}^{\ast}=x\) in equilibrium.
At the initial date, player \(A\) anticipates the behavior of date \(2\) and maximizes \[\max_{x} \left\{ x^{2}  \frac{x^{3}}{3}\right\}.\] This gives the first order condition \(2x  x^{2}=0\), from which we get the solution \(x = 2\).
Consequently, we have a unique Nash equilibrium given by \(\left\{(x=2,y_{A}=2), y_{B}=2\right\}\).

Find the subgame perfect equilibria of the following game. How many subgames does the game have?
There are two subgames. The subgame perfect equilibrium is \(\left\{(U,E,H),(B,C)\right\}\).
Group B

Consider the alternating offer bargaining game with two players \(A\) and \(B\) negotiating how to split surplus with a unitary value. Player \(A\) moves first and makes an offer \(x\in[0,1]\). Player \(B\) moves second and decides whether to accept or reject the offer. If the offer is accepted, player \(A\) gets \(x\), and player \(B\) gets \(1x\). If the offer is rejected, player \(B\) makes a counteroffer \(y\in[0,1]\). If the counteroffer is accepted, player \(A\) gets \(1y\), and player \(B\) gets \(y\). If the counteroffer is rejected, the game continues with player \(A\) making an offer. Players discount every offerround with factors \(\delta_{A},\delta_{B}\in[0,1)\).
 Calculate the recursive subgame perfect equilibrium.
 Show that if the discount factor of player \(A\) increases, then she can get a greater part of the surplus.
 Show that if the discount factor of player \(B\) increases, then player \(A\) gets a smaller part of the surplus.

Suppose that we are at time \(t\) and player \(B\) makes an offer. Player \(A\) accepts the offer if and only if \(1y \ge 0\). Thus, player \(B\), aiming at maximizing her share, solves \[\max_{1y \ge 0} y\] and offers \(y=1\). At time \(t1\), player \(B\) knows that if the game proceeds to time \(t\), player \(A\) will accept the offer \(y=1\). Therefore, if she waits for the next time point, player \(B\) can gain \(\delta_{B}\cdot 1\) in present value terms. Hence, she accepts any offer of player \(A\) securing her at least this gain, namely \(1x \ge \delta_{B}\). Player \(A\) anticipates this behavior, solves \[\max_{1x \ge \delta_{B}} x,\] and offers \(x=1\delta_{B}\).
At time \(t2\), player \(A\) knows that if she delays, she can gain \(1\delta_{B}\), which corresponds to gaining \(\delta_{A}(1\delta_{B})\) discounted in time \(t2\) terms. She, therefore, accepts an offer if \(1y \ge \delta_{A}  \delta_{A}\delta_{B}\). Thus, player \(B\) solves \[\max_{1y \ge \delta_{A}  \delta_{A}\delta_{B}} y\] and offers \(y = 1  \delta_{A} + \delta_{A}\delta_{B}\). In a similar manner, one argues that, at time \(t3\), player \(A\) solves \[\max_{1x \ge \delta_{B}  \delta_{A}\delta_{B} + \delta_{A}\delta_{B}^2} x,\] and offers \(x=1  \delta_{B} + \delta_{A}\delta_{B}  \delta_{A}\delta_{B}^2\).
Repeating the aforementioned recursive arguments, we find that player \(A\)’s offer at date \(t(2n1)\) (observe that, because we started with player \(B\), player \(A\) moves at odd offerrounds) is
\begin{align*} x &= 1  \delta_{B} + \delta_{A}\delta_{B}  \delta_{A}\delta_{B}^2 + \dots + \delta_{A}^{n1}\delta_{B}^{n1}  \delta_{A}^{n1}\delta_{B}^{n} \\ &= 1 + \dots + \delta_{A}^{n1}\delta_{B}^{n1}  \delta_{B}\left(1 + \dots + \delta_{A}^{n1}\delta_{B}^{n1}\right) \\ &= \left(1  \delta_{B}\right) \sum_{j=0}^{n1} \delta_{A}^{j}\delta_{B}^{j}. \end{align*}
Letting \(n\) go to infinity, the share of player \(A\) converges to
\begin{align*} x = \frac{1  \delta_{B}}{1  \delta_{A}\delta_{B}}. \end{align*}

We can find the effect of \(\delta_{A}\) on player \(A\)’s share by calculating
\begin{align*} \frac{\partial x}{\partial \delta_{A}} = \delta_{B}\frac{1  \delta_{B}}{\left(1  \delta_{A}\delta_{B}\right)^{2}}, \end{align*}
which is positive.

From
\begin{align*} \frac{\partial x}{\partial \delta_{B}} =  \frac{1  \delta_{A}}{\left(1  \delta_{A}\delta_{B}\right)^{2}} < 0, \end{align*}
we see that player \(A\)’s share is decreasing in \(\delta_{B}\).
References
References
Topic's Concepts
 bargaining
 cooperative bargaining
 subgame perfect equilibrium
 subgame
 sequential
 tit for tat strategies
 grim trigger strategies
 trigger strategy
 stage game
 repeated games