Extensive form games

What Is Extensive Form Games?

Extensive form games are a detailed representation within game theory that explicitly models sequential decision-making processes, particularly useful in analyzing dynamic strategic interactions. Unlike a payoff matrix used in normal form games, an extensive form game is typically depicted as a "game tree," illustrating the order of players' moves, their choices at each turn, and the information available to them when making a decision, culminating in a set of payoffs for each possible outcome²⁵, ²⁶. This structured approach allows for a granular understanding of how strategies unfold over time, incorporating factors like perfect information or imperfect information among players²⁴.

History and Origin

The conceptual foundations of extensive form games were significantly advanced by mathematician Harold W. Kuhn. In 1953, Kuhn formalized the extensive form representation, building upon earlier work in game theory, particularly by John von Neumann. His contributions provided a rigorous framework for analyzing sequential games, establishing key results like Kuhn's Theorem, which relates different types of strategies in games with "perfect recall." Kuhn's work was pivotal in developing the tools to understand decision processes where the timing and order of moves are crucial, moving beyond simultaneous-move game representations.

Key Takeaways

• Extensive form games visually represent sequential strategic interactions through a tree-like structure known as a game tree.
• They capture the order of moves, available actions at various decision nodes, and the information players possess.
• The concept of subgame perfect equilibrium is a primary solution concept, often found using backward induction.
• Extensive form games are essential for analyzing scenarios involving sequential decisions, such as bargaining, auctions, and corporate strategy.
• They can account for elements of chance and varying degrees of information among players, enriching the analysis of complex real-world situations.

Formula and Calculation

While there isn't a single "formula" for an extensive form game itself, its analysis often relies on algorithms to find equilibrium solutions. One common method for solving extensive form games with perfect information is backward induction.

Backward induction involves starting at the terminal nodes of the game tree and working backward through the decision nodes to the initial node. At each decision node, the player whose turn it is chooses the action that maximizes their payoff, assuming all subsequent players will also act optimally.

Consider a simple game with two players, 1 and 2, and their payoffs (u_1) and (u_2).
At any given decision node (x), if player (i) is to move, and the available actions lead to successor nodes with expected payoffs (E(u_i | a)) for each action (a \in A(x)), player (i) will choose:

This process is repeated backward from the end of the game, determining the optimal strategy at each node. The set of strategies derived through backward induction constitutes a subgame perfect equilibrium.

Interpreting the Extensive Form Game

Interpreting an extensive form game involves analyzing the strategic choices available to players at each stage and anticipating their rational responses. The game tree visualizes potential paths and outcomes, allowing for a deep understanding of strategic interdependence. Each branch represents an action, and the path from the initial node to a terminal node represents a complete play of the game.

Critical to interpretation are information sets, which group together decision nodes that a player cannot distinguish between when making a choice²³. If an information set contains more than one node, it indicates imperfect information, meaning a player is uncertain about previous moves or external events. Conversely, if every information set is a singleton (contains only one node), the game has perfect information, and all players know precisely what has transpired before their turn²². Analyzing these elements helps predict the optimal course of action for each player and the likely outcome of the strategic interactions.

Hypothetical Example

Consider a hypothetical market entry game between an incumbent firm (Player 1) and a potential entrant (Player 2).

1. Player 2 (Entrant) moves first, deciding whether to "Enter" or "Stay Out."
2. If Player 2 chooses "Stay Out," the game ends. Player 1 (Incumbent) gets a high payoff (e.g., 10), and Player 2 gets 0.
3. If Player 2 chooses "Enter," then Player 1 (Incumbent) moves second, deciding whether to "Fight" (e.g., by initiating a price war) or "Accommodate."
   • If Player 1 chooses "Fight," both players receive low payoffs (e.g., Player 1: 1, Player 2: 1).
   • If Player 1 chooses "Accommodate," both players share the market, receiving moderate payoffs (e.g., Player 1: 5, Player 2: 3).

To solve this extensive form game using backward induction:

• Step 1 (Player 1's decision if Player 2 enters): If Player 2 enters, Player 1 compares "Fight" (payoff 1) with "Accommodate" (payoff 5). Player 1 will choose "Accommodate" to maximize their payoff.
• Step 2 (Player 2's initial decision): Knowing Player 1's rational response, Player 2 considers their options:
  • "Stay Out": Player 2 gets 0.
  • "Enter" (knowing Player 1 will accommodate): Player 2 gets 3.

Player 2 will choose "Enter" because 3 is greater than 0. The predicted outcome is that the Entrant enters, and the Incumbent accommodates, leading to payoffs (5, 3). This demonstrates how sequential decisions are analyzed by anticipating future rational play.

Practical Applications

Extensive form games are widely applied in financial and economic analysis due to their ability to model complex, dynamic interactions. They are particularly useful in situations where the sequence of decisions significantly impacts outcomes²¹.

• Corporate Strategy: Firms use extensive form games to model competitive scenarios, such as product launches, pricing strategies in an oligopoly, or decisions about market entry and exit. For instance, an incumbent firm might analyze a potential entrant's strategic moves and determine the optimal response (e.g., fighting with a price war versus accommodating) to protect its market share¹⁹, ²⁰.
• Bargaining and Negotiation: From labor negotiations to international trade agreements, bargaining processes are often sequential, involving offers and counteroffers. Extensive form games help analyze optimal strategies and predict negotiation outcomes¹⁸.
• Auctions: Many auction formats, especially those with multiple bidding rounds or sequential bids, can be effectively modeled as extensive form games to understand bidders' strategies and predict final prices¹⁷.
• Investment Decisions: In finance, these games can model strategic interactions between investors, or between investors and firms, particularly in scenarios involving risk management or assessing the value of options that involve future contingent decisions. They can inform strategies for achieving a competitive advantage in dynamic markets.

Limitations and Criticisms

Despite their analytical power, extensive form games, and the solution concepts associated with them, have certain limitations. One notable criticism centers on the concept of "non-credible threats" or "incredible threats" when using the Nash equilibrium as a solution concept in sequential games¹⁶. A Nash equilibrium might suggest strategies that are optimal for players given the entire strategy profile, but are not optimal if a particular situation (an "off-path" information set) were actually reached¹⁴, ¹⁵.

For example, in the market entry scenario, a Nash equilibrium might exist where the incumbent threatens to "Fight" if the entrant enters, deterring entry. However, if the entrant does enter, actually fighting might be detrimental to the incumbent, making the threat non-credible. The subgame perfect equilibrium refinement addresses this by requiring strategies to be optimal in every possible subgame of the game, thus eliminating such incredible threats¹², ¹³.

Another limitation can arise in games with complex imperfect information or highly extended sequences, where the practical application of backward induction becomes computationally intensive or relies on strong assumptions about players' rationality and their ability to perfectly anticipate future moves¹¹. Furthermore, modeling situations where players have "unawareness" of certain actions or outcomes can add significant complexity beyond standard extensive form game frameworks¹⁰.

Extensive Form Games vs. Normal Form Games

The primary distinction between extensive form games and normal form games lies in their representation and the types of strategic interactions they are best suited to analyze.

While any extensive form game can theoretically be converted into a normal form game, the resulting normal form representation can be very large and may lose some of the intuitive visual details of the sequential decisions⁸, ⁹. Extensive form games are preferred when the sequence of moves and the information structure are central to understanding the strategic environment, providing a more comprehensive description compared to the summarized view of a normal form game⁶, ⁷.

FAQs

What is a game tree in extensive form games?

A game tree is a graphical representation of an extensive form game, resembling a tree diagram. It consists of decision nodes (where players make choices), branches (representing available actions), and terminal nodes (where the game ends and payoffs are received)⁴, ⁵. It visually maps out the sequence of moves and all possible outcomes.

What is the purpose of information sets in extensive form games?

Information sets in extensive form games indicate a player's knowledge (or lack thereof) about past moves when it's their turn to act. If a player cannot distinguish between multiple decision nodes at their turn, those nodes are grouped into an information set, signifying imperfect information about the precise history of play³.

How is an extensive form game typically solved?

An extensive form game, particularly one with perfect information, is typically solved using backward induction. This method involves analyzing the game from its end, determining the optimal moves for the last player, then the second-to-last player, and so on, working backward to the beginning of the game to identify the subgame perfect equilibrium¹, ². This solution concept ensures that all players are acting optimally at every point in the game, not just at the start.