3.1 Extensive Form Games and Decision Trees

Extensive form games use game trees to map out sequential decision-making in strategic interactions. These trees show players, moves, and payoffs, allowing for analysis of complex scenarios where timing and information matter.

Perfect information games give players full knowledge of past moves, while imperfect information games introduce uncertainty. Understanding these differences is crucial for solving games through techniques like backward induction and predicting optimal strategies.

Extensive Form Games

Game trees for sequential moves

• Extensive form games use game trees to represent sequential-move games
  • Nodes depict decision points or outcomes in the game
  • Edges illustrate the actions or moves available to players
• The initial node serves as the root or starting point of the game tree
• Terminal nodes indicate the end of the game and specify the payoffs for each player
• Subgames are smaller extensive form games embedded within the larger game tree
  • Originate at decision nodes and encompass all subsequent nodes and edges

Components of extensive form games

• Players are the individuals or entities making decisions in the game
  • Identified by labels or symbols at each decision node (Player 1, Player 2)
• Strategies refer to the complete set of actions available to a player at each decision point
  • Determined by the edges extending from a player's decision nodes (Cooperate, Defect)
• Payoffs represent the outcomes or rewards for each player at the terminal nodes
  • Expressed as a tuple for multi-player games (3, 5) for a two-player game

Perfect vs imperfect information

• Perfect information games:
  • Players have complete knowledge of all prior moves and the current game state
  • Represented by single decision nodes for each player (Chess, Go)
• Imperfect information games:
  • Players may lack complete knowledge of previous moves or the current state
  • Represented by information sets connecting decision nodes with dashed lines or ovals
    • Players cannot differentiate between nodes within the same information set (Poker, Battleship)

Move order and player knowledge

• The order of moves follows the sequence of nodes in the game tree
  • Earlier moves appear at the top, with later moves below
• The information available to players varies based on the type of game:
  • Perfect information games:
    • Players have complete knowledge at each decision node
  • Imperfect information games:
    • Players may have incomplete knowledge at certain decision nodes
    • Information sets signify the player's uncertainty about the current state
• Backward induction solves extensive form games by working backwards from terminal nodes
  • At each decision node, the player selects the action leading to their best payoff
  • Assumes optimal play by all players in subsequent moves (Minimax algorithm)