Dynamic Games
- 14 minutes read - 2906 wordsContext
- Strategic interactions and social dilemmas can sometimes be understood in terms of one-shot 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 father-in-law, 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 \(1-x\).
- If the offer is rejected, both players get zero.
First Move Advantage
- Player \(B\) accepts if \(1-x \ge 0\) or, equivalently, if \(x\le 1\).
- Player \(A\) offers \(x = 1\).
Counter-Proposal
- 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 \(1-y\), and player \(B\) gets \(y\).
- If the counteroffer is rejected, both players get zero.
Last Offer Advantage
- Player \(A\) accepts the counteroffer if \(1-y \ge 0\) or, equivalently, if \(y\le 1\).
- Player \(B\) offers \(y = 1\).
- Player \(B\) accepts the first offer if \(1-x \ge y = 1\) or , equivalently, if \(x \le 0\).
- Player \(A\) offers \(x = 0\).
Alternating Offers
- Suppose that the counter-proposal game is infinitely repeated until a deal is reached.
- Every time a player rejects an offer, she makes a counteroffer.
- Players discount every offer-round 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 \(t-1\), player \(B\) accepts if \(x\le 1-\delta_{B}\), so player \(A\) offers \(x=1-\delta_{B}\).
- At date \(t-2\), 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 two-player 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 \(1-x\). If the offer is rejected, player \(B\) makes a counteroffer \(y\in[0,1]\). If the counteroffer is accepted, player \(A\) gets \(1-y\), and player \(B\) gets \(y\). If the counteroffer is rejected, the game continues with player \(A\) making an offer. Players discount every offer-round 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 \(1-y \ge 0\). Thus, player \(B\), aiming at maximizing her share, solves \[\max_{1-y \ge 0} y\] and offers \(y=1\). At time \(t-1\), 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 \(1-x \ge \delta_{B}\). Player \(A\) anticipates this behavior, solves \[\max_{1-x \ge \delta_{B}} x,\] and offers \(x=1-\delta_{B}\).
At time \(t-2\), 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 \(t-2\) terms. She, therefore, accepts an offer if \(1-y \ge \delta_{A} - \delta_{A}\delta_{B}\). Thus, player \(B\) solves \[\max_{1-y \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 \(t-3\), player \(A\) solves \[\max_{1-x \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-(2n-1)\) (observe that, because we started with player \(B\), player \(A\) moves at odd offer-rounds) is
\begin{align*} x &= 1 - \delta_{B} + \delta_{A}\delta_{B} - \delta_{A}\delta_{B}^2 + \dots + \delta_{A}^{n-1}\delta_{B}^{n-1} - \delta_{A}^{n-1}\delta_{B}^{n} \\ &= 1 + \dots + \delta_{A}^{n-1}\delta_{B}^{n-1} - \delta_{B}\left(1 + \dots + \delta_{A}^{n-1}\delta_{B}^{n-1}\right) \\ &= \left(1 - \delta_{B}\right) \sum_{j=0}^{n-1} \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