Extensive-form game
In game theory, an extensive-form game is a specification of a game allowing (as the name suggests) for the explicit representation of a number of key aspects, like the sequencing of players' possible moves, their choices at every decision point, the (possibly imperfect) information each player has about the other player's moves when they make a decision, and their payoffs for all possible game outcomes.
Extensive-form games also allow for the representation of incomplete information in the form of chance events modeled as "moves by nature".
Extensive-form representations differ from normal-form in that they provide a more complete description of the game in question, whereas normal-form simply boils down the game into a payoff matrix.
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.
At any given non-terminal node belonging to Chance, an outgoing branch is chosen according to the probability distribution.
(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).
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.
2) A complete extensive-form representation specifies: The game on the right has two players: 1 and 2.
To more easily solve this game for the Nash equilibrium,[3] it can be converted to the normal form.
In games with infinite action spaces and imperfect information, non-singleton information sets are represented, if necessary, by inserting a dotted line connecting the (non-nodal) endpoints behind the arc described above or by dashing the arc itself.
It may be the case that a player does not know exactly what the payoffs of the game are or of what type their opponents are.
In extensive form it is represented as a game with complete but imperfect information using the so-called Harsanyi transformation.
Consider a game consisting of an employer considering whether to hire a job applicant.
The job applicant's ability might be one of two things: high or low.
In this case, it is convenient to model nature as another player of sorts who chooses the applicant's ability according to those probabilities.
Nature's choice is represented in the game tree by a non-filled node.
Edges coming from a nature's choice node are labelled with the probability of the event it represents occurring.
In the case of private information, every player knows what has been played by nature.
If both play D, player 2 can only form the belief that they are on either node in the information set with probability 1/2 (because this is the chance of seeing either type).
If both types play U, player 2 again forms the belief that they are at either node with probability 1/2.
Formally, a finite game in extensive form is a structure
It may be that a player has an infinite number of possible actions to choose from at a particular decision node.
The device used to represent this is an arc joining two edges protruding from the decision node in question.
If the action space is a continuum between two numbers, the lower and upper delimiting numbers are placed at the bottom and top of the arc respectively, usually with a variable that is used to express the payoffs.
The subgame perfect Nash equilibria of this game can be found by taking the first partial derivative[citation needed] of each payoff function with respect to the follower's (firm 2) strategy variable (
The same process can be done for the leader except that in calculating its profit, it knows that firm 2 will play the above response and so this can be substituted into its maximisation problem.
