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.
Articles by others on the same topic
There are currently no matching articles.