Dynamic Games

Context

• 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

wikipedia

• 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

wikipedia

• 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

• Belleflamme & Peitz, 2010, sec. A.2
• Watson, 2008, Chapter 14
• Varian, 2010, secs. 29.5, 29.7

Exercises

Group A

1. 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\}\).

2. 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

1. 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)\).

   1. Calculate the recursive subgame perfect equilibrium.
   2. Show that if the discount factor of player \(A\) increases, then she can get a greater part of the surplus.
   3. Show that if the discount factor of player \(B\) increases, then player \(A\) gets a smaller part of the surplus.

   1. 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*}

   2. 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.

   3. 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