6.1 Extensive form games and game trees

Extensive form games and game trees are powerful tools for analyzing sequential decision-making in strategic situations. They visually represent the order of moves, choices available to players, and resulting outcomes, allowing for detailed analysis of complex interactions.

Game trees map out all possible paths and outcomes in a sequential game. By breaking down the decision-making process step-by-step, they help identify optimal strategies and predict likely outcomes, connecting to the broader concepts of backward induction in sequential games.

Extensive form games: Structure and components

Key components and their roles

Top images from around the web for Key components and their roles

• 

  Extensive form - Simulace.info View original

  Is this image relevant?

• 

  Extensive form - Simulace.info View original

  Is this image relevant?

• 

  Extensive form - Simulace.info View original

  Is this image relevant?

• 

  Extensive form - Simulace.info View original

  Is this image relevant?

• 

  Extensive form - Simulace.info View original

  Is this image relevant?

1 of 3

Top images from around the web for Key components and their roles

• 

  Extensive form - Simulace.info View original

  Is this image relevant?

• 

  Extensive form - Simulace.info View original

  Is this image relevant?

• 

  Extensive form - Simulace.info View original

  Is this image relevant?

• 

  Extensive form - Simulace.info View original

  Is this image relevant?

• 

  Extensive form - Simulace.info View original

  Is this image relevant?

1 of 3

• An extensive form game is a detailed description of a sequential structure representing the players, moves, payoffs, and outcomes of a game
• The key components of an extensive form game:
  • Players: Individuals or entities who make decisions and take actions throughout the course of the game
  • Decision nodes: Points in the game where players make choices
  • Branches: Paths emanating from decision nodes, representing available actions or strategies
  • Terminal nodes: Endpoints of the game tree, specifying final outcomes and payoffs
  • Payoffs: Utility or value assigned by each player to the possible outcomes of the game
• The structure of an extensive form game is defined by the order of the players' moves and the information available at each decision point

Representation using game trees

• Extensive form games can be represented using a game tree, a directed graph illustrating the sequence of moves and outcomes
• The game tree starts with an initial node, representing the first move, and branches out to subsequent nodes until it reaches the terminal nodes
• Nodes are connected by directed edges, indicating the sequence of moves from one decision point to the next
• Terminal nodes specify the final outcomes and payoffs for each player

Game trees for sequential games

Constructing game trees for perfect information games

• To construct a game tree, begin by identifying the players and the order in which they make their moves
• Each decision point is represented by a node in the game tree, with branches emanating from the node representing the available actions or strategies
• The nodes are connected by directed edges, indicating the sequence of moves from one decision point to the next
• Perfect information games are those in which all players have complete knowledge of the previous moves and the current state of the game at each decision point
• When constructing a game tree for a perfect information game:
  • Nodes are labeled with the player whose turn it is to move
  • Branches are labeled with the available actions
  • Terminal nodes represent possible outcomes and are labeled with corresponding payoffs for each player

Labeling and interpreting game trees

• Players are typically labeled with letters or numbers (Player 1, Player 2) to distinguish their roles and decision points
• Branches are labeled with the specific actions available to the player at each node (Cooperate, Defect)
• Payoffs at terminal nodes are listed in the order of the players, often separated by commas or parentheses (2, 1)
• The path from the initial node to a terminal node represents a complete sequence of moves and the resulting outcome
• By tracing different paths through the game tree, one can analyze the possible strategies and outcomes of the game

Players, strategies, and payoffs in extensive form games

Defining players, strategies, and payoffs

• Players in an extensive form game are the individuals or entities who make decisions and take actions throughout the course of the game
• Each player has a set of strategies, which are complete plans of action that specify the moves they will make at each decision point, contingent on the information available to them
• A player's strategy in an extensive form game must account for all possible moves by the other players and the resulting outcomes
• Payoffs in an extensive form game represent the utility or value that each player assigns to the possible outcomes of the game
• Payoffs are typically represented numerically and are specified at the terminal nodes of the game tree

Strategic interactions and conflicts of interest

• The payoffs for each player may differ based on their preferences and objectives, leading to potential conflicts of interest and strategic interactions
• Players must consider not only their own payoffs but also the potential actions and payoffs of their opponents when making decisions
• The extensive form representation allows for the analysis of strategic interactions, such as:
  • Anticipating and responding to the moves of other players
  • Identifying dominant strategies or equilibrium outcomes
  • Evaluating the credibility of threats or promises in sequential games
• By examining the payoff structure and the sequence of moves, players can make informed decisions and adapt their strategies accordingly

Simultaneous vs sequential games

Characteristics of simultaneous games

• Simultaneous games are those in which players make their moves or choose their strategies at the same time, without knowledge of the other players' actions
• In simultaneous games, players cannot observe or react to the moves of their opponents, and the outcome is determined by the combination of strategies chosen by all players
• Examples of simultaneous games:
  • Prisoner's Dilemma: Two suspects must independently decide whether to confess or remain silent
  • Battle of the Sexes: A couple must independently choose between two entertainment options
  • Matching Pennies: Two players simultaneously choose heads or tails, with payoffs based on matching or mismatching choices

Characteristics of sequential games

• Sequential games are those in which players make their moves in a specific order, with each player aware of the previous moves made by other players
• In sequential games, players have the opportunity to observe and respond to the actions of their opponents, allowing for strategic adaptation and anticipation
• Extensive form games are typically used to model and analyze sequential games, as they capture the dynamic nature of the decision-making process and the flow of information
• Examples of sequential games:
  • Ultimatum Game: One player proposes a division of a resource, and the other player must accept or reject the proposal
  • Stackelberg Competition: A leader firm makes a decision, followed by a follower firm's decision based on the leader's action
  • Centipede Game: Players alternately choose whether to continue or stop, with payoffs increasing as the game progresses

Distinguishing between simultaneous and sequential games

• The key distinction between simultaneous and sequential games lies in the timing of moves and the information available to players when making their decisions
• In simultaneous games, players act independently without knowing the actions of others, while in sequential games, players make decisions based on the observed actions of previous players
• The choice between modeling a situation as a simultaneous or sequential game depends on the nature of the strategic interaction and the availability of information
• Simultaneous games are often analyzed using normal form representations (payoff matrices), while sequential games are more commonly represented using extensive form games and game trees