4.1 — Subgame Perfection

# 4.1 — Subgame Perfection
## ECON 316 • Game Theory • Fall 2021
### Ryan Safner<br> Assistant Professor of Economics <br> <a href="mailto:safner@hood.edu"><i class="fa fa-paper-plane fa-fw"></i>safner@hood.edu</a> <br> <a href="https://github.com/ryansafner/gameF21"><i class="fa fa-github fa-fw"></i>ryansafner/gameF21</a><br> <a href="https://gameF21.classes.ryansafner.com"> <i class="fa fa-globe fa-fw"></i>gameF21.classes.ryansafner.com</a><br>

---

# Outline

### [Subgame Perfection](#3)
### [Subgames](#9)
### [Entry Game Example](#27)
### [Strategic Moves](#40)

---

# Subgame Perfection

---

# A Motivating Example

- If you believe my threat, you will arrive on time, and I never have to carry out my threat

- *Sounds* like a Nash equilibrium:
  - I get what I want at no cost to me
  - You prefer being in class on time to failing
  - Nobody wants to change

]

---

# A Motivating Example

.pull-left[
- Implausible prediction: I would not actually want to carry out my threat if it came to it!
    - Big confrontation, you could complain to Dept. chair, Provost, etc

- A problem of “out-of-equilibrium” play
    - How can a threat *I will never carry out* change your behavior?
    - I can optimally choose bizarre behavior in situations I know will never happen!

]

---

# A Motivating Example

.pull-left[
- BUT: if you know what *would* happen in those unlikely scenarios, that *does* affect your behavior for things that *normally* happen
    - namely, if you know I will not *actually* fail you for coming late, you will sometimes come late

]

---

# Motivating Example

- Must learn another major refinement of Nash equilibrium

- First, return to seqential games

- Continue with assumption of perfect information (soon we will consider imperfect information)

]

---

# Motivating Example

- A new solution concept:

- .hi[Subgame perfect Nash equilibrium (SPNE)]: selects only Nash equilibria sustained by .hi-purple[credible] threats and promises, and rules out *non-credible* threats/promises
    - Formal definition: a set of strategies is **SP** if it induces a Nash equilibrium in *every subgame* of a game
    
- First, let’s understand what we mean by “subgame”

]

---

# Subgames

---

# Subgames

.pull-left[
- A .hi[subgame] is any portion of a game that contains one initial note and all of its successor nodes
  - e.g. .hi-turquoise[any decision node initiates its own subgame] through to the terminal nodes
  - The game itself counts as a subgame
    
- Idea: analyze a subgame as a game itself and .hi-turquoise[ignore any history] in the overall game and .hi-turquoise[find what is optimal in each subgame]

]

# Subgames: Example

.pull-left[
- In this example, there are 3 subgames:
  1. The full game itself (initiated by .red[Player 1]'s decision node .red[1.1])
  2. Subgame initiated by .blue[Player 2's] decision node .blue[2.1]
  3. Subgame initiated by .blue[Player 2's] decision node .blue[2.2]

]

---

# Aside: Subgames Can't Break Information Sets

.pull-left[
.smaller[
- Subgames cannot “break” .hi-purple[information sets]
  - Indicated by dashed line: .blue[Player 2] does not know what .red[Player 1] chose (consider it a simultaneous game)
  - More on information later

- Players must *know which* subgame they are in, so a subgame cannot “break” an information set
  - .blue[Player 2] here would not know what .red[Player 1] did, so .red[Player 1] can’t make a decision; could not “ignore history”
]
]
.pull-right[
.center[
![](../images/subgames_infosets.png)
]
]

---

# (Review) Strategies in this Example

.pull-left[
.smallest[
- Recall we defined a .hi[strategy] as a complete plan of what a player will do at *every* decision node they (might) face

- .red[Player 1] has 1 decision (.red[1.1]) with 2 choices, so `\(2^1\)` possible strategies:
  1. .red[X] at (.red[1.1])
  2. .red[Y] at (.red[1.1])
]
]
.pull-right[
.center[
![](../images/subgames_example.png)
]
]

---

# (Review) Strategies in this Example

.pull-left[
.smallest[
- Recall we defined a .hi[strategy] as a complete plan of what a player will do at *every* decision node they (might) face

- .red[Player 1] has 1 decision (.red[1.1]) with 2 choices, so `\(2^1\)` possible strategies:
  1. .red[X] at (.red[1.1])
  2. .red[Y] at (.red[1.1])
  
- .blue[Player 2] has 2 decision (.blue[2.1], .blue[2.2]) with 2 choices at each, so `\(2^2\)` possible strategies:
  1. .blue[A] at (.red[2.1]); .blue[C] at (2.2)
  2. .blue[A] at (.red[2.1]); .blue[D] at (2.2)
  3. .blue[B] at (.red[2.1]); .blue[C] at (2.2)
  4. .blue[B] at (.red[2.1]); .blue[D] at (2.2)
]
]
.pull-right[
.center[
![](../images/subgames_example.png)
]
]

---

# Converting Between Sequential and Normal Form

- We can convert any sequential game in extended form (game tree) into a normal game (payoff matrix)
  - Harder to go the other way around!

]

---

# Converting Between Sequential and Normal Form

- We can convert any sequential game in extended form (game tree) into a normal game (payoff matrix)
  - Harder to go the other way around!

- Payoff matrix of outcomes of all possible combinations of strategies for each player
]

![](../images/subgames_example_normal.png)
]
]

---

# Converting Between Sequential and Normal Form

- Solve the normal form for Nash equilibria
]

![](../images/subgames_example_normal.png)
]
]

---

# Converting Between Sequential and Normal Form

- Nash equilibria:
  1. {.red[Y], .blue[(A,D)]}
  2. {.red[X], .blue[(B,C)]}
  3. {.red[X], .blue[(B,D)]}
]

![](../images/subgames_example_normal_NE.png)
]
]

---

# Converting Between Sequential and Normal Form

- Nash equilibria:
  1. {.red[Y], .blue[(A,D)]}
  2. {.red[X], .blue[(B,C)]}
  3. {.red[X], .blue[(B,D)]}

- But remember, this is a sequential game! Which of these Nash equilibria is .hi[sequentially-rational]?
]

![](../images/subgames_example_normal_NE.png)
]
]

---

# Rollback Equilibrium

- Solve for rollback equilibrium via backwards induction

- A process of considering .hi-purple[“sequential rationality”]:

> “If I play x, my opponent will respond with y; given their response, do I really want to play x? ...”

]

![](../images/subgames_example_normal_NE.png)
]
]

---

# Converting Between Sequential and Normal Form

- Nash equilibria:
  1. {.red[Y], .blue[(A,D)]}
  2. {.red[X], .blue[(B,C)]}
  3. {.red[X], .blue[(B,D)]}

- .hi-purple[Rollback equilibrium:] {.red[X], .blue[(B,D)]}
]

![](../images/subgames_example_normal_NE.png)
]
]

---

# Converting Between Sequential and Normal Form

- Nash equilibria:
  1. {.red[Y], .blue[(A,D)]}
  2. {.red[X], .blue[(B,C)]}
  3. {.red[X], .blue[(B,D)]}

- Even though there are three Nash equilibria, only one is .hi-purple[subgame perfect]
  - .red[Player 1] and .blue[Player 2] are playing {.red[X], .blue[(B,D)]} respectively causes a .hi-turquoise[Nash equilibrium in .ul[every] subgame]
]

![](../images/subgames_example_normal_NE.png)
]
]

---

# Converting Between Sequential and Normal Form

- Nash equilibria:
  1. {.red[Y], .blue[(A,D)]}
  2. {.red[X], .blue[(B,C)]}
  3. {.red[X], .blue[(B,D)]}

.smallest[
- Consider the first NE: {.red[Y], .blue[(A,D)]}
  - Not on the equilibrium path of play
  - Not sequentially rational: if .red[Player 1] had played .red[X] (for whatever reason), .blue[Player 2] would want to switch from playing .blue[A] to playing .blue[B] at .blue[2.1]!
  - Thus, this strategy is not a NE in subgame initiated at node .blue[2.1] (.blue[Player 2] would want to change strategies)
]
]

![](../images/subgames_example_normal_NE.png)
]
]

---

# Converting Between Sequential and Normal Form

- Nash equilibria:
  1. {.red[Y], .blue[(A,D)]}
  2. {.red[X], .blue[(B,C)]}
  3. {.red[X], .blue[(B,D)]}

.smallest[
- Consider the second NE: {.red[X], .blue[(B,C)]}
  - Not on the equilibrium path of play
  - Not sequentially rational: if .red[Player 1] had played .red[Y] (for whatever reason), .blue[Player 2] would want to switch from playing .blue[C] to playing .blue[D] at .blue[2.2]!
  - Thus, this strategy is not a NE in subgame initiated at node .blue[2.2] (.blue[Player 2] would want to change strategies)
]
]

![](../images/subgames_example_normal_NE.png)
]
]

---

# Converting Between Sequential and Normal Form

- Nash equilibria:
  1. {.red[Y], .blue[(A,D)]}
  2. {.red[X], .blue[(B,C)]}
  3. {.red[X], .blue[(B,D)]}

.smallest[
- Consider the third NE: {.red[X], .blue[(B,D)]}
  - On the equilibrium path of play
  - Sequentially rational: these strategies lead to a NE in *every* subgame!
  - Conveniently: .hi-turquoise[the “rollback equilibrium” is always subgame perfect]
]
]

![](../images/subgames_example_normal_NE.png)
]
]

---

# Converting Between Sequential and Normal Form

- Subgame perfection rules out .hi-purple[non-credible threats or promises]

- Depending on context, .blue[Player 2] might threaten/promise that they will play .blue[C] if .red[Player 1] plays .red[Y]
  - But if that subgame were reached, .blue[Player 2] would *not* play .blue[C], they would want to play .blue[D]!
  - i.e. not a credible claim
]

![](../images/subgames_example_normal_NE.png)
]
]

---

# Entry Game Example

---

# Entry Game: Extensive Form

- Consider an .hi[Entry Game], a .hi-purple[sequential] game played between a potential .hi-red[Entrant] and an .hi-blue[Incumbent]
]

]

---

# Entry Game: (Pure) Strategies

- .hi-red[Entrant] has 2 pure strategies:
  1. .red[Stay Out] at .red[E.1]
  2. .red[Enter] at .red[E.1]

- .hi-blue[Incumbent] has 2 pure strategies:
  1. .blue[Accommodate] at .blue[I.1]
  2. .blue[Fight] at .blue[I.1]

]

---

# Entry Game: Backward Induction

- .hi-purple[Rollback/Subgame Perfect Nash Equilibrium]:

---

# Entry Game: Normal vs. Extensive Form

- Convert this game to Normal form

- Note, if .hi-red[Entrant] plays .red[Stay Out], doesn't matter what .hi-blue[Incumbent] plays, payoffs are the same

- Solve this for Nash Equilibria...

]

---

# Entry Game: Normal vs. Extensive Form

- Two Nash Equilibria:
1. (.hi-red[Enter], .hi-blue[Accommodate])
2. (.hi-red[Stay Out], .hi-blue[Fight])

- But remember, we ignored the *sequential* nature of this game in normal form
  - Which Nash equilibrium is **sequentially rational?**
]

---

# Entry Game: Subgames

1. Subgame initiated at decision node .hi-red[E.1] (i.e. the full game)
2. Subgame initiated at decision node .hi-blue[I.1]

]

---

# Entry Game: Subgame Perfect Nash Equilibrium

- Consider each subgame as a game itself and ignore the .hi-purple[“history”] of play that got a to that subgame
  - What is optimal to play in *that* subgame?

- Consider a set of strategies that is optimal for all players in *every* subgame it reaches

- That is a .hi[subgame perfect Nash equilibrium]

]

---

# Entry Game: Subgame Perfect Nash Equilibrium

- Recall our two Nash Equilibria from normal form: 
1. (.hi-red[Enter], .hi-blue[Accommodate])
2. (.hi-red[Stay Out], .hi-blue[Fight])

]

![:scale 80%](../images/entry_game_normal_BR.png)

]
]

---

# Entry Game: Subgame Perfect Nash Equilibrium

- Recall our two Nash Equilibria from normal form: 
1. (.hi-red[Enter], .hi-blue[Accommodate])
2. (.hi-red[Stay Out], .hi-blue[Fight])

- Consider the second set of strategies, where .hi-blue[Incumbent] chooses to .blue[Fight] at node .blue[I.1]

- What if for some reason, .hi-blue[Incumbent] is playing this strategy, and .hi-red[Entrant] unexpectedly plays .red[Enter]?
]

![:scale 80%](../images/entry_game_normal_BR.png)

]
]

---

# Entry Game: Subgame Perfect Nash Equilibrium

- It's **not rational** for .hi-blue[Incumbent] to play .blue[Fight] if the game reaches .blue[I.1]!
  - Would want to switch to .blue[Accommodate]!

- .hi-blue[Incumbent] playing .hi-blue[Fight] at .blue[I.1] is **not a Nash Equilibrium in this subgame!**

- Thus, Nash Equilibrium (.hi-red[Stay Out], .hi-blue[Fight]) is **not sequentially rational**
  - It *is* still a Nash equilibrium!
]

![:scale 80%](../images/entry_game_normal_BR.png)

]
]

---

# Entry Game: Subgame Perfect Nash Equilibrium

- Only (.hi-red[Enter], .hi-blue[Accommodate]) is a .hi-purple[Subgame Perfect Nash Equilibrium (SPNE)]

- These strategy profiles for each player constitute a Nash equilibrium in every possible subgame!

- Simple connection: rollback equilibrium is always SPNE!
]

![:scale 80%](../images/entry_game_normal_BR.png)

]
]

---

# Entry Game: SPNE and Credibility

- Suppose before the game started, .hi-blue[Incumbent] announced to .hi-red[Entrant]

> “if you .red[Enter], I will .blue[Fight]!”

- This **threat** is .hi-purple[not credible] because playing .blue[Fight] in response to .red[Enter] is not rational!

- The strategy is not Subgame Perfect!

]

![:scale 80%](../images/entry_game_normal_BR.png)

]
]

---

# Strategic Moves

---

# Strategic Moves AKA “Game Changers”

- In many strategic situations, players have incentives to try to affect the rules of the game for their own benefit
    - Order, available strategies, payoffs, repetition
    
- A .hi[strategic move] (“game changer”) is an action taken outside the rules an existing game by transforming it into a two-stage game
    - A strategic move is made in stage I (“pre-game” move)
    - A modified version of the original game is played in stage II
]
]

---

# Types of Strategic Moves

.pull-left[
.smallest[
1. .hi[Threats]: if other players don’t choose your preferred move, you will play in a manner that will be bad for them (in second stage)
  - .hi-purple[Conditional] response to other players’ actions

2. .hi[Promises]: if other players choose your preferred move, you will play in a manner that will be good for them (in second stage)
  - .hi-purple[Conditional] response to other players’ actions

3. .hi[Commitments]: irreversibly limit your choice of action, .hi-purple[unconditional] on other players’ actions
]
]

---

# Strategic Moves and Credibility

- Key: .hi-turquoise[threats and promises are often costly if you must carry them out against your own interest!]

- If a threat works and elicits the desired behavior in others, no need to carry it out

- If a promise elicits the desired behavior in others, cost of performing the promise
]

---

# Strategic Moves and Credibility

- For a strategic move to work, it must be:
  - observable to all players
  - irreversible so that it alters other players’ expectations

- Other players must believe you will *actually do* in the second stage what you threaten/promise you will do during the first stage
  - .hi[Credibility] of strategic moves open to question
]

---

# Strategic Moves and Credibility

.pull-left[
.smallest[
- Your parents probably (tried to) used strategic moves on you
  - “No dessert unless you eat your vegetables”
  - “We’ll buy you a new bike if you get a B GPA”
  
- You may have (rightly) questioned their credibility
  - Most parents *don’t actually want* to punish or discipline their kids (it’s painful *to the parents*)
  - (An empty) threat that changes their kid’s behavior is great, but costly if it actually has to be carried out
]
]
.pull-right[
.center[
![](../images/parentingthreat.jpg)
]
]

---

# Non-Credibility AKA “Cheap Talk”

- .hi-purple[“Talk is cheap”]
  - Low cost to making promises/threats you don’t intend to carry out

- Promises and threats .hi-turquoise[without commitment] will not change equilibrium behavior (with perfect information)

- If you try to bluff in poker, and your rivals know what cards you have, they will call your bluff

]

![:scale 80%](../images/bluff.jpeg)
]
]

---

# Non-Credibility AKA “Cheap Talk”

.pull-left[
.smaller[
- Promises or threats must be .hi[incentive-compatible] to work
  - Threat/promise-maker must actually stand to benefit from performing the threat/promise or suffer from not performing it

- In game theory terms: strategy must be .hi-purple[subgame perfect]

- .hi-purple[Subgame perfection] rules out Nash equilibria relying upon non-credible threats and promises; keeps only behavior that is optimal under every circumstance!
]
]

![:scale 80%](../images/bluff.jpeg)
]
]

---

# Credible Commitment

- A .hi[commitment] changes the game in a way that forces you to carry out your promise or threat
  - tying your own hands makes you stronger!
]

![:scale 80%](../images/bluff.jpeg)
]
]

---

# Credible Commitment

![:scale 75%](../images/odysseus.png)

*Odysseus and the Sirens* by John William Waterhouse, Scene from Homer's *The Odyssey*

]

---

# Commitments

.pull-left[
- A .hi[commitment] is an action taken .hi-purple[unconditional] on other players' actions that limits your own actions

- If credible, tantamount to changing the order of the game at Stage II, so that the player making the commitment moves first

- Can change outcomes of following games, since it changes other players' expectations of the consequences of their own actions

]

---

# Simple Commitment Example in Chicken

- Both players want to act tough from the beginning and project an image that they'll never back down, so the other player must

- But what makes a .hi-purple[credible commitment]?

]

---

# Simple Commitment Example in Chicken

.pull-left[
- Only a *visible* and *irreversible* action commits .red[Row] to going straight is **credible**
  - rip out steering wheel
  - tie the steering wheel
  
- Forces .blue[Column] to Swerve

]

---

# Simple Commitment Example in Chicken

.center[
<iframe width="980" height="550" src="https://www.youtube.com/embed/u7hZ9jKrwvo" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
]

---

# Simple Commitment Example in Chicken

.center[
<iframe width="980" height="550" src="https://www.youtube.com/embed/Fn7d_a0pmio" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
]

---

# “Total Commitment” in *Dr. Strangelove*

.center[
<iframe width="980" height="550" src="https://www.youtube.com/embed/PSofqNSuVy8" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
]