Extensive-form game

A game described by a game tree, with the acting player and available actions specified at each decision node, payoffs at terminal nodes, and information sets indicating which decision nodes a player can distinguish. A pure strategy specifies an action at every information set belonging to that player, including ones not reached during realized play.

Two players alternate proposals for dividing a pie, with a fixed final round. Agreement ends the game; rejection shrinks the next available pie by a factor $0<\alpha <1$. Final rejection gives both players zero. Offers range continuously over the entire available pie. Backward induction in games determines immediate agreement and the proposer's share through the continuous-offer bargaining acceptance lemma and the finite-horizon bargaining parity effect. Discrete offer grids can change both the boundary behavior and the exact shares.

In finite-horizon alternating-offer bargaining, the proposer with $k$ rounds left retains fraction $P_k$ of the currently available pie. Terminal acceptance gives $P_1=1$. After rejection, the responder becomes proposer and can obtain fraction $\alpha P_{k-1}$ of the current pie. The continuous-offer bargaining acceptance lemma therefore gives $P_k=1-\alpha P_{k-1}$. Summing the resulting finite geometric series proves the displayed formula.

Odd horizons give shares above $1/(1+\alpha )$, decreasing toward it; even horizons give shares below it, increasing toward it. Between two available horizons $k_1<k_2$, choose $k_1$ if $k_1$ is odd and $k_2$ if $k_1$ is even. This concerns the initial proposer and immediate agreement, rather than waiting until the selected final round to obtain its share.

Let a proposer divide a pie of size $M>0$ by continuously offering its responder $q\in [0,M]$. Rejection gives fixed continuation payoffs $b$ to the proposer and $c$ to the responder, with $0\le c<M$ and $b<M-c$. Then a subgame perfect equilibrium must have the responder accept $q=c$ with probability one. The proposer offers exactly $c$, retaining $M-c$.

Sequential rationality forces rejection for $q<c$ and acceptance for $q>c$. If acceptance at $c$ had probability $a<1$, that offer would give the proposer $a(M-c)+(1-a)b<M-c$. Every larger offer gives less than $M-c$ and can be improved by a smaller offer still above $c$; every smaller offer gives $b<M-c$. The supremum $M-c$ would therefore be unattained. Randomizing offers cannot attain it either: the nonnegative gap from $M-c$ would be strictly positive almost surely and hence have positive expectation. No best response would exist, contradicting equilibrium. Acceptance at $c$ removes this gap and makes $q=c$ the unique optimal proposal. The assumptions $c<M$ and $b<M-c$ exclude degenerate indifference of the proposer.

In a finite perfect-information game without chance moves, solve terminal decision points first. At each earlier decision point, its player chooses an action maximizing its own payoff among the already solved continuations. Record a choice in every subgame, including those not reached by the root choice. This constructs a subgame perfect equilibrium. Tied choices may yield several equilibrium strategies and several outcomes. The name refers to Ernst Zermelo; the computational procedure is an application of backward induction.

Suppose a finite perfect-information game has no chance moves, and every player strictly ranks the possible outcome labels. Different terminal histories may have the same outcome label and thus the same payoff. Every subgame then has a unique subgame perfect equilibrium outcome, even though its equilibrium strategy need not be unique.

The proof is backward induction. Each child subgame has a unique continuation outcome. The moving player's strict ranking selects exactly one best label among those outcomes. Several actions can tie only by leading to that same label, which proves uniqueness at the current node. For a sequential election, the labels may be winning candidates: a voter can have several optimal ballots, all producing its same favourite achievable winner. If preferences have ties between different labels, the conclusion can fail.

Two strategies for the same player are realization-equivalent when they induce the same probability distribution on terminal histories against every fixed opposing strategy profile. The requirement is stronger than having equal expected payoff against one particular opponent. For a finite extensive-form game with perfect recall, Kuhn's theorem gives this equivalence between appropriate mixed strategies and behavioural strategies.