1.3 — Sequential Games

# 1.3 — Sequential Games
## 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

### [Games in Extensive Form](#3)
### [Mover Advantages](#)
### [How Reasonable is Rollback Thinking?](#)

---

# The Century Mark Game

.pull-left[
.bg-washed-blue.b--dark-blue.ba.bw2.br3.shadow-5.ph4.mt5[
.hi-blue[Rules]: Two (teams of) players alternating turns

- The count starts at 0
  1. Team 1 adds a number 1-10 to the tally
  2. Team 2 adds a number 1-10 to the tally
- The first team to bring the tally to 100 wins
]
]

---

# Sequential Games with Perfect Information

- Strict order of play

- Perfect information
  - No **external uncertainty**: nature/probability does not interfere between choices `$\rightarrow$` outcomes
  - No **strategic uncertainty**: each player observes the history of other players’ moves

- Can be represented in .hi[extensive form], i.e. a .hi[game tree]
]

---

# Games in Extensive Form

---

# Games in Extensive Form

- .hi-red[Principal] starts with $100. If they .red[invest], with .hi-blue[Agent], it doubles to $200

- .hi-blue[Agent] then decides whether to .blue[share] or .blue[keep] it 
]

---

# Games in Extensive Form

1. .hi-red[Principal] (.red[Player 1]) moves first.

2. .hi-blue[Agent] (.blue[Player 2]) moves second (but only if .hi-red[Principal] has played .red[Invest]).

- The game ends.
]

---

# Games in Extensive Form

- .hi-purple[Decision nodes]: decision point for each player
  - Solid nodes, I've labeled and color-coded by player (.red[P.1], .blue[A.1])

- .hi-purple[Terminal nodes]: outcome of game, with payoff for each player
  - Hollow nodes, no further choices
]

---

# Games in Extensive Form: Outcomes

1. (.red[Don't]): .red[100], .blue[0]
2. (.red[Invest], .blue[Keep]): .red[0], .blue[200] 
3. (.red[Invest], .blue[Share]): .red[150], .blue[50]

]

---

# Strategies

.pull-left[
- .hi[(“Pure”) strategy]: a player’s **complete** plan of action for every possible contingency
  - i.e. what player will choose at **every possible decision node**, even if it’s never reached

- Think of a strategy like an .hi-turquoise[algorithm]:

> If we reach node 1, then I will play X; if we reach node 2, then I will play Y; if...
]

---

# Trust Game: Strategies

- .hi-red[Principal] has 2 possible strategies:
  1. .red[Don't] at .red[P.1]
  2. .red[Invest] at .red[P.1]

- .hi-blue[Agent] has 2 possible strategies:
  1. .blue[Keep] at .blue[A.1]
  2. .blue[Share] at .blue[A.1]

- Note .hi-blue[Agent]'s strategy only comes into play if .hi-red[Principal] plays .red[Invest] and the game reaches node .blue[A.1]

]

---

# Solving the Game: Backward Induction

- To determine the outcome of the game, start with the *last-mover* (i.e. decision nodes just before terminal nodes) and work to the beginning

- 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?”

- What is that mover's best choice to maximize their payoff?
]

]

---

# Solving the Game: Backward Induction

- We start at .blue[A.1] where .hi-blue[Agent] can:
  - .blue[Keep] to yield outcome (.red[0], .blue[200])
  - .blue[Share] to yield outcome (.red[150], .blue[50])

]

---

# Solving the Game: Backward Induction

- We start at .blue[A.1] where .hi-blue[Agent] can:
  - .blue[Keep] to yield outcome (.red[0], .blue[200])
  - .blue[Share] to yield outcome (.red[150], .blue[50])

- .hi-blue[Agent] only considers their own payoff
  - (.red[Invest], .blue[Keep]) `$\succ$` (.red[Invest], .blue[Share])
  - .blue[200] `$\succ$` .blue[50]
]

---

# Solving the Game: Backward Induction

- .hi-blue[Agent] will .blue[Keep] if the game reaches node .blue[A.1]

- Recognizing this, what will .hi-red[Principal] do?
]

---

# Solving the Game: Backward Induction

- Work our way up to .red[P.1] where .hi-red[Principal] can:
  - .red[Don't] to yield outcome (.red[100], .blue[0])
  - .red[Invest], knowing .hi-blue[Agent] will .blue[Keep], to yield outcome (.red[0], .blue[200])

- .hi-red[Principal] only considers their own payoff
  - (.red[Don't]) `$\succ$` (.red[Invest], .blue[Keep])
  - .red[100] `$\succ$` .red[0]

]

---

# Solving the Game: Backward Induction

- .hi.purple[Equilibrium]: (.red[Don't], .blue[Keep])
  - Defined by the strategy played by each player

]

---

# Solving the Game: Pruning the Tree

- As we work backwards, we can .hi-turquoise[prune] the branches of the game tree
  - Highlight branches that players **will** choose
  - Cross out branches that players will **not** choose

- .hi-purple[Equilibrium path of play] is highlighted from the root to one terminal node
  - (.red[Don't])
  - All other paths are not taken

]

---

# Another Example: Senate Race

- Challenger is .hi-green[Congresswoman Green]

- .hi-brown[Brown] moves first, must decide early-on to .brown[Run Ads] or .brown[No Ads]

- .hi-green[Green] moves second, must decide to .green[Enter] or .green[Stay Out]

]

---

# Another Example: Senate Race

.pull-left[
- Payoff considerations:
  - Ads are costly, .hi-brown[Brown] would prefer to not run ads
  - .hi-green[Green] will fare better if .hi-brown[Brown] does not run ads

- Use 1,2,3,4 for simple rankings
]

---

# Senate Race Game: Strategies

- .hi-brown[Brown] has 2 strategies:
  1. .brown[Ads] at .brown[B.1]
  2. .brown[None] at .brown[B.1]

]

---

# Senate Race Game: Strategies

- .hi-green[Green] has 4 strategies:

- Two decision nodes, two strategies at each node, hence `$2^2=4$`
  1. .green[Enter] at .green[G.1]; .green[Enter] at .green[G.2]
  2. .green[Enter] at .green[G.1]; .green[Stay Out] at .green[G.2]
  3. .green[Stay Out] at .green[G.1]; .green[Enter] at .green[G.2]
  4. .green[Stay Out] at .green[G.1]; .green[Stay Out] at .green[G.2]

]

---

# Senate Race Game: Strategies

- Remember, think about a strategy like an algorithm
  1. If .brown[Ads] then .green[Enter]; if .brown[None] then .green[Enter] (always Enter)
  2. If .brown[Ads] then .green[Enter]; if .brown[None] then .green[Stay Out]
  3. If .brown[Ads] then .green[Stay Out]; if .brown[None] then .green[Enter]
  4. If .brown[Ads] then .green[Stay Out]; if .brown[Stay Out] then .green[Stay Out] (always Stay Out)

]

---

# Senate Race Game: Solution

- To apply backward induction, begin with the last-mover

1. What will .hi-green[Green] choose...
  - If .hi-brown[Brown] were to run .brown[Ads]?
  - If .hi-brown[Brown] were to run .brown[None]?

]

---

# Senate Race Game: Solution

- To apply backward induction, begin with the last-mover

1. What will .hi-green[Green] choose...
  - If .brown[Ads] then .green[Stay Out] (at B.1)
  - If .brown[None] then .green[Enter] (at B.2)

2. Given this, what will .hi-brown[Brown] choose?
]

---

# Senate Race Game: Solution

- To apply backward induction, begin with the last-mover

1. What will .hi-green[Green] choose...
  - If .brown[Ads] then .green[Stay Out] (at B.1)
  - If .brown[None] then .green[Enter] (at B.2)

2. Given this, what will .hi-brown[Brown] choose?
  - (.brown[Ads], .green[Stay Out]) `$\succ$` (.brown[None], .green[Enter])
  - (.brown[3]) `$\succ$` (.brown[2])
]

---

# Senate Race Game: Solution

- .purple[Equilibrium:] (.brown[Ads], .green[(Stay Out, Enter)])

- Notation:
  - .hi-brown[Brown's] strategy shows his decision at .brown[B.1] only
  - .hi-green[Green]'s strategy shows her decisions at .green[(G.1,G.2)]
  
]

---

# Mover Advantages

---

# Mover Advantage: Senate Race Game

- Is there an .hi[order advantage] to the Senate Race game?

- We saw what happens when .hi-brown[Brown] moves first

- Change the rules so that .hi-green[Green] moves first and see what changes
  - Be careful how you write the payoffs!
]

---

# Mover Advantage: Senate Race Game

- .hi-green[Green] has 2 strategies:
  1. .green[Enter] at .green[G.1]
  2. .green[Stay Out] at .green[G.1]

]

---

# Mover Advantage: Senate Race Game

- .hi-green[Green] has 2 strategies:
  1. .green[Enter] at .green[G.1]
  2. .green[Stay Out] at .green[G.1]

- .hi-brown[Brown] has 4 strategies:
  1. .brown[Ads] at .brown[B.1]; .brown[Ads] at .brown[B.2]
  2. .brown[Ads] at .brown[B.1]; .brown[None] at .brown[B.2]
  3. .brown[None] at .brown[B.1]; .brown[Ads] at .brown[B.2]
  4. .brown[None] at .brown[B.1]; .brown[None] at .brown[B.2]

]

---

# Mover Advantage: Senate Race Game

- Apply backwards induction

1. What will .hi-brown[Brown] choose
  - If .hi-green[Green] were to .green[Enter]?
  - If .hi-green[Green] were to .green[Stay Out]?

]

---

# Mover Advantage: Senate Race Game

- Apply backwards induction

1. What will .hi-brown[Brown] choose
  - If .green[Enter] then .brown[None]
  - If .green[Stay Out] then .brown[None]
  
- Note .brown[None] becomes a .hi-purple[dominant strategy] for .hi-brown[Brown]!

2. Given this, what will .green[Green] choose?
]

---

# Mover Advantage: Senate Race Game

- .purple[Equilibrium:] (.green[Enter], .brown[(None, None)])
  - Payoffs of (.green[4], .brown[2])
  
- Recall original outcome (.brown[Ads], .green[(Stay Out, Enter)])
  - Payoffs of (.brown[3], .green[3])

- .hi-brown[Brown] is worse-off moving second vs. first; .hi-green[Green] is better off moving first vs. second
  - A .hi-purple[first-mover advantage] for either player
]

---

# When Order Matters

- In general, to see if order matters, reverse sequence of moves and see if outcomes differ

- Games with first-mover advantage:
  - Century Mark
  - Tic-tac-toe
  - Chess? Checkers?

- Games with second-mover advantage:
  - Free riders
  - Business?
]

---

# When Order Matters

Clayton Christensen
]
]

> “When you look across the sweep of business history, most companies that once seemed successful—the best practitioners of best practice—were in the middle of the pack (or, worse, the back of it) a decade or two later...What often causes this lagging behind are two principles of good management taught in business schools: that you should always listen to and respond to the needs of your best customers, and that you should focus investments on those innovations that promise the highest returns. But these two principles, in practice, actually sow the seeds of every successful company's ultimate demise,” (ix-x).

]

.source[Christensen, Clayton, 2016[1997], *The Innovator's Dilemma: When New Technologies Cause Great Firms to Fail*]
]

---

# When Order Matters

Peter Thiel
]
]

> “You've probably heard about 'first mover advantage': if you're the first entrant into a market, you can capture significant market share while competitors scramble to get started. But moving first is a tactic, not a goal...[B]eing the first mover doesn't do you any good if someone comes along and unseats you. It's much better to be the *last* mover—that is, to make the last great development in a specific market and enjoy years or even decades of monopoly profits.,” (57-58).

]

---

# Adding Players

---

# Adding Players

---

# Adding Players

---

# Adding Players

---

# Adding Players

---

# How About If We Change it to This

---

# How About If We Change it to This

---

# Summary

1. Construct a game tree
  - Place players in proper order
  - Specify which decisions are available to each player at each decision node
  - Specify payoffs to all players in terminal noides

2. Solve for rollback equilibrium
  - Start with last-mover, identify best response, prune all other branches
  - Work successively backwards to the root
  - Highlight equilibrium path of play
  - Equilibrium = set of (complete!) strategies all players are playing

---

# How Reasonable is Rollback Thinking?

---

# How Reasonable is Rollback Thinking?

- Useful for simple games with few players & moves

- More difficult for complex games (more moves and/or players)
  - Tic-tac-toe has `$9!$` or `$362,880$` possible moves
]

]
]

---

# How Reasonable is Rollback Thinking?

- Chess estimated to have `$10^{120}$` possible moves

- Players need rules to assign “payoffs” to *non-terminal* nodes, an “intermediate value function”
  - Humans `$<$` computers at anticipating future moves
  - Humans `$>$` computers at mid-game intuition and experience
]

---

# How Reasonable is Rollback Thinking?

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

---

# How Reasonable is Rollback Thinking?

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

How Richard Hatch won the first Survivor]

---

# How Reasonable is Rollback Thinking?

---

# Games on Moblab

---

# Split the Pie

---

# The Dictator Game

.pull-right[
- Famously called .hi[“The Dictator Game”]
  - .hi-red[Player 1] is given money (e.g. $100) and decides how much of that `$(x)$` to give to .hi-blue[Player 2]

- Used in experiments to measure altruism in societies

- What’s the .hi[rollback equilibrium]?

- What do we see in the real world?
]
---

# Split the Pie, Modified

---

# Split the Pie, Modified

---

# Ultimatum Game

- Equally famous game used in experiments, the .hi[Ultimatum game]
  - After .hi-red[Player 1] decides how much `$(x)$` to give to .hi-blue[Player 2], .hi-blue[Player 2] can .blue[Accept] or .blue[Reject] (where nobody gets anything)

- What’s the .hi[rollback equilibrium]?

- What do we see in the real world?
]

---

# Pass the Pumpkin

---

# Pass the Pumpkin

---

# Centipede Game

- Called the .hi[Centipede game]
  - Players take turns deciding between **taking** money out of a pot vs. **passing**; after each **pass**, the money in the pot grows, until a set final turn

- What's the .hi[rollback equilibrium]?

- What do we see in the real world?
]

---

# Centipede Game