Overview
This lecture covers methods for solving extensive form games, focusing on finding Nash Equilibria and subgame perfect Nash Equilibrium (SPNE) through backward induction.
Normal Form Representation of Extensive Games
- Extensive form games can be represented in normal form with strategies for each player listed in matrices.
- Player 1 chooses between two decision points, having 6 possible strategies (combining choices at both points).
- Player 2 has one decision point with two possible actions, resulting in 2 strategies.
- Player 3 has two decision points, each with two actions, resulting in 4 strategies.
- The normal form matrix for three players may have 6 rows, 2 columns, and 4 matrix layers.
- Finding pure strategy Nash equilibria from the normal form is possible but complex.
Backward Induction and SPNE
- Backward induction is a simpler alternative for finding subgame perfect Nash equilibrium (SPNE).
- The process starts with the last moving players, determining their optimal actions at the end of the game.
- For each terminal node, players select actions that maximize their payoffs, assuming all are rational.
- Continue backward, determining optimal strategies for the second-to-last movers and so on until reaching the first player.
- The result is a strategy profile where every player’s strategy is optimal given the subsequent ones.
Constructing the Equilibrium Strategy Profile
- The optimal strategy profile combines each player's best action at every decision point per backward induction.
- Example: Player 1 chooses (c, n), Player 2 chooses y, Player 3 chooses (w, v).
- This profile yields the outcome (7, 0, 6) in payoffs.
Verifying Nash Equilibrium
- To check Nash equilibrium, verify that no player can unilaterally deviate and get a higher payoff, given others’ strategies.
- For each player, holding the others' strategies fixed, confirm their best response aligns with the backward induction strategy.
- Player 1 cannot get more than 7, Player 2’s choice doesn’t affect her payoff, and Player 3’s best possible payoff is 6.
- Since all are best-responding, the strategy profile is a Nash equilibrium.
Key Terms & Definitions
- Normal Form Game — Representation listing all players’ strategies and resulting payoffs in a matrix.
- Backward Induction — Method of solving games by sequentially determining optimal actions from the end of the game backward.
- Strategy Profile — Complete specification of a strategy for every player at every decision point.
- Subgame Perfect Nash Equilibrium (SPNE) — A strategy profile that yields a Nash equilibrium in every subgame of the original game.
- Nash Equilibrium — Set of strategies where no player can benefit from unilaterally changing their strategy.
Action Items / Next Steps
- Practice applying backward induction on different extensive form games.
- Verify SPNE by checking best responses for alternative strategy deviations.
- Prepare for upcoming exams or problem sets on subgame perfect Nash equilibrium and extensive form games.