Extensive Form Games

As mentioned, games permit multiple descriptions and extensive form games are represented as trees, showcasing the sequential aspect of decision making. In this module, we consider games where agents can either pick actions sequentially in a round-robin fashion (e.g., tic-tac-toe) or simultaneously over multiple rounds (e.g., best two-out-of-three rock-paper-scissors).

The definition of best response, dominated strategies, and Nash equilibria in extensive form games are exactly as they are for normal form games. Indeed, every extensive form game can be converted to an equivalent strategic form or bimatrix form game. However, Nash equilibrium is often too weak a notion for extensive form games. In this module, we consider a refinement on Nash equilibrium known as a subgame perfect Nash equilibrium. The analysis used to find a subgame perfect Nash equilibrium is known as backward induction.

Elements

1. 3.2.aBackward Induction

   The ability to determine the best action given the subsequent optimal actions working backwards from the end of the game.

2. 3.2.bSubgame-Perfect Nash Equilibrium

   The ability to compute and select strategies in a Nash equilibrium not just for the game as a whole but also for every point in the game where the agent takes an action, regardless of the previous moves.