Extensive-form Game - Finite Extensive-form Games

Finite Extensive-form Games

Some authors, particularly in introductory textbooks, initially define the extensive-form game as being just a game tree with payoffs (no imperfect or incomplete information), and add the other elements in subsequent chapters as refinements. Whereas the rest of this article follows this gentle approach with motivating examples, we present upfront the finite extensive-form games as (ultimately) constructed here. This general definition was introduced by Harold W. Kuhn in 1953, who extended an earlier definition of von Neumann from 1928. Following the presentation from Hart (1992), an n-player extensive-form game thus consists of the following:

• A finite set of n (rational) players
• A rooted tree, called the game tree
• Each terminal (leaf) node of the game tree has an n-tuple of payoffs, meaning there is one payoff for each player at the end of every possible play
• A partition of the non-terminal nodes of the game tree in n+1 subsets, one for each (rational) player, and with a special subset for a fictitious player called Chance (or Nature). Each player's subset of nodes is referred to as the "nodes of the player". (A game of complete information thus has an empty set of Chance nodes.)
• Each node of the Chance player has a probability distribution over its outgoing edges.
• Each set of nodes of a rational player is further partitioned in information sets, which make certain choices indistinguishable for the player when making a move, in the sense that:
  • there is a one-to-one correspondence between outgoing edges of any two nodes of the same information set—thus the set of all outgoing edges of an information set is partitioned in equivalence classes, each class representing a possible choice for a player's move at some point—, and
  • every (directed) path in the tree from the root to a terminal node can cross each information set at most once
• the complete description of the game specified by the above parameters is common knowledge among the players

A play is thus a path through the tree from the root to a terminal node. At any given non-terminal node belonging to Chance, an outgoing branch is chosen according to the probability distribution. At any rational player's node, the player must choose one of the equivalence classes for the edges, which determines precisely one outgoing edge except (in general) the player doesn't know which one is being followed. (An outside observer knowing every other player's choices up to that point, and the realization of Nature's moves, can determine the edge precisely.) A pure strategy for a player thus consists of a selection—choosing precisely one class of outgoing edges for every information set (of his). In a game of perfect information, the information sets are singletons. It's less evident how payoffs should be interpreted in games with Chance nodes. It is assumed that each player has a von Neumann–Morgenstern utility function defined for every game outcome; this assumption entails that every rational player will evaluate an a priori random outcome by its expected utility.

The above presentation, while precisely defining the mathematical structure over which the game is played, elides however the more technical discussion of formalizing statements about how the game is played like "a player cannot distinguish between nodes in the same information set when making a decision". These can be made precise using epistemic modal logic; see Shoham & Leyton-Brown (2009, chpt. 13) for details.

A perfect information two-player game over a game tree (as defined in combinatorial game theory and artificial intelligence), for instance chess, can be represented as an extensive form game as defined with the same game tree and the obvious payoffs for win/lose/draw outcomes. A game over an expectminimax tree, like that of backgammon, has no imperfect information (all information sets are singletons) but has Chance moves. As further examples, various variants of poker have both chance moves (the cards being dealt, initially and possibly subsequently depending on the poker variant, e.g. in draw poker there are additional Chance nodes besides the initial one), and also have imperfect information (some or all the cards held by other players, again depending on the Poker variant; see community card poker). (Binmore 2007, chpt. 2)