Backward induction in games 2026-10-31
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.
Expectimax 2026-10-25
A game tree evaluation rule using maxima at the controlled player’s decision nodes and expected values at chance nodes:respectively. Terminal utilities fix the boundary values. These rules exactly optimize a finite-horizon expected utility objective by backward induction. For cyclic infinite-horizon reachability problems, a finite Markov decision process formulation and value iteration replace naive expansion of an infinite game tree. Start with one at successful terminal states and zero elsewhere, keep terminal values fixed, and apply the maximizing/expectation backups repeatedly. The th iterate is the greatest success probability achievable within transitions, by backward induction. These values are nondecreasing and bounded by one. For every policy, eventual success is the increasing set union of success within finite horizons, so its probability is the limit of those finite-horizon probabilities. Taking the supremum over policies and horizons in either order proves that the iterates converge to the optimal eventual-success probability. The limiting fixed-point equations can also admit larger solutions, so the initialization from terminal-success indicators matters.
Expectiminimax 2026-10-25
Backward induction on a finite game tree containing maximizing choices, minimizing choices and chance nodes. Terminal utilities are backed up by , and , respectively. Exact chance node evaluation generally needs every positive-probability outcome; ordinary alpha-beta pruning does not transfer unchanged because one child's value does not bound the full weighted sum.
With a unit cash asset, independent Gaussian price increments of mean and positive variance , and exponential terminal utility , the optimal predictable risky holding is the displayed constant number of shares. The one-step exponential-loss exponent is ; completing its square gives a minimal multiplier . Backward induction proves optimality among adapted strategies and gives value .
General-sum game Created 2026-10-24 Updated 2026-11-05
A game whose players' utility are specified separately, without assuming a fixed sum. Improving one player's utility need not worsen another's. A finite perfect-information game can be solved by backward induction using entire utility tuples and each moving player's own coordinate, as in max-n search.
Iterated prisoner's dilemma Created 2026-10-14 Updated 2026-10-20
The iterated prisoner's dilemma is a repeated game with a prisoner's dilemma at each round. Earlier choices can change later best responses: a present gain from defection may be outweighed by lost future cooperation. A pure strategy now specifies an action after every possible observed history, including histories that its own prescribed play would never reach. The horizon, observations, initial actions, and payoff convention must be specified before assessing a Nash equilibrium or subgame perfect equilibrium.
For the following worked example, repeat the prisoner's dilemma above infinitely at rounds . Assume public perfect monitoring: after each round both players observe both actions exactly, without error. They share a discount factor and evaluate a path of stage payoffs using the normalized discounted payoffThe round-zero weight is one before normalization, including when . A larger discount factor gives future payoffs more weight; the geometric series makes a constant stage payoff have the same normalized value. These assumptions and normalization follow [ref]
https://ocw.mit.edu/courses/6-254-game-theory-with-engineering-applications-spring-2010/5a158a7558165d0e22b5b27fcfa01713_MIT6_254S10_lec15.pdf. Asu Ozdaglar, MIT 6.254, lecture 15, slides 6–15
. The numerical payoffs here are our example; the lecture uses a different table.Suppose both players use grim trigger: play initially and while every past action of both players was ; after any observed , play forever. With no unilateral deviation, each gets normalized payoff . A first unilateral deviation to earns now, then at most each round because the opponent switches permanently to always defect. The deviator attains that continuation payoff by choosing thereafter. At any history of mutual cooperation, the comparison is thereforeCooperation is a best response precisely whenEquivalently, without normalization the geometric series givesMultiplying both unnormalized payoffs by the same positive factor leaves the best response comparison unchanged.
Repeated prisoner's dilemma: normalized cooperation and first-deviation payoffs cross at discount factor one half
. Details. For example, with discount factor , the first unilateral deviation gives normalized payoff , so mutual grim trigger is not a Nash equilibrium. At , it gives , so cooperation is preferable. At the two payoffs tie: the incentive to cooperate is weak, which is sufficient for a subgame perfect equilibrium.
The punishment is credible after every history containing a defection: the opponent's pure strategy then prescribes forever, and remains the stage best response, earning rather than . Together with the cooperative-history comparison, this establishes mutual grim trigger as a subgame perfect equilibrium for . Delaying the first unilateral deviation merely delays the same gain or loss; further cooperation during punishment only lowers the deviator's payoff. Mutual always defect also remains a subgame perfect equilibrium, so patience permits cooperation without making it inevitable.
This calculation assumes an infinite horizon and ; it does not define a discounted payoff at . With a finite, commonly known final round and positive weight on each round, backward induction instead gives mutual defection in every round of this stage game. Observational errors change the model too: one mistaken defection permanently activates grim trigger. Historical dependence, initial memories, and the payoff time convention also affect whether a cooperative rule resists or invades other pure strategies; the existing reactive strategy and Tit for tat discussions concern those additional questions.
John C. Cox 2026-11-05
John C. Cox developed mathematical methods for option pricing and risk-neutral pricing. With Stephen A. Ross and Mark Rubinstein, he introduced the Cox--Ross--Rubinstein model, whose binomial price tree gives a particularly transparent example of a replicating portfolio.[ref]
Option Pricing: A Simplified Approach by John C. Cox and others. 1979, author list and the one-period replication argument
At each node, the two possible next-step payments determine the holdings in a stock and a riskless asset. Repeating this calculation by backward induction values the final payment through the tree. For an American option, the calculation also compares continuation value with the value of immediate exercise. This turns the distinction between European and American exercise rules into a concrete computational decision.[ref]
Option Pricing: A Simplified Approach by John C. Cox and others. Multiperiod model and valuation of options permitting early exercise
Institutional profile: mitsloan.mit.edu/faculty/directory/john-c-cox
Portrait of John C. Cox
. Portrait selected from the matching MIT Sloan institutional profile. Source. Max-n search 2026-10-25
Backward induction with an -component utility vector. At a node controlled by player , evaluate each child, choose a child maximizing coordinate and copy its entire vector. A fixed tie rule makes the returned vector well defined. By mathematical induction from terminal positions, the selected continuation is a best response at every node of a finite perfect-information game, giving a pure strategy subgame perfect equilibrium. The vector must be copied intact; separate coordinatewise maxima need not describe any attainable outcome.
Minimax search 2026-10-25
Backward induction on a finite deterministic game tree of a two-player zero-sum game. Terminal payoffs are propagated by maximization at one player's decision nodes and minimization at the other's. With full information, the resulting choices give an optimal strategy against the opposing player's best response. A cyclic state graph requires a winning condition on infinite plays and a graph algorithm rather than unrestricted recursive unfolding.
For each history of the first two votes, voter 3 selects its favourite achievable winner. Writing rows for voter 1's vote and columns for voter 2's vote, the resulting continuation winners areFor example, after votes , voter 3 can make either or win, and prefers ; a vote for would instead produce the tie-break winner .
Voter 2 prefers to to . Optimizing each row therefore gives continuation winners after voter 1's respective choices . Voter 1 prefers to and therefore votes , giving winner in every subgame perfect equilibrium.
Some histories admit several equally good votes, but they produce the same winning candidate. Since each voter strictly ranks the three possible winners, unique outcome under strict outcome preferences makes this winner independent of those action ties. This is backward induction over outcomes, not a claim that the entire equilibrium strategy profile is unique.
The depth assertion is false. Each move occupies one new square, so the general bound is , not . On a board no knights attack, and a play has four moves. More generally, filling a single checkerboard colour gives a legal partial play of length , since knight moves always change colour.
The opponent-independent “best possible move” assertion is false. Minimax search maximizes the guaranteed utility against an opponent choosing the worst continuation. It need not maximize the outcome against a particular weaker opponent. If a winning strategy is available, its guaranteed win cannot be improved on in win/loss utility; if every root move loses against perfect play, all have the same minimax value, yet some may exploit a weaker opponent better. Thus the valid universal statement is that a minimax strategy guarantees its minimax value, not that its root choice is best for every possible opponent behavior.[ref]
CS 188 minimax notes. §3.2, opening assumption: the opponent chooses the move worst for the agent
The storage assertion is false for the usual minimax implementation. Here the maximum branching factor is and maximum depth is . A conventional depth-first search retaining pending successors uses the usual search-node bound. Generating successors lazily and applying/undoing moves in one board can reduce this to stack frames plus board storage; neither accounting should confuse the board side length with its squares.
The winning-strategy assertion is true. The game is finite, has perfect information, alternates two players, and has no draw under the normal-play convention. A terminal position is losing for the player to move. By backward induction, a nonterminal position is winning exactly when at least one legal move reaches a losing position; otherwise it is losing. This labels every position, including the initial board, so exactly one of the two players has a winning strategy.
Propagate an entire utility pair from a child chosen to maximize the component of the player whose turn it is. This is the two-player case of max-n search. At a terminal node let . At an A-node chooseand at a B-node replace by . Do not maximize the two coordinates independently: their separate maxima may belong to incompatible outcomes. Fix a tie rule, such as the first child in the specified order. The rule recursively gives a pure strategy subgame perfect equilibrium in a finite perfect-information game: backward induction makes the moving player's selected continuation a best response at every node.[ref]
CS 188 stochastic and general game notes. §3.4, entire utility tuples selected by the moving player's component
In the original Figure 2, each of the three children of the root belongs to B. The left B-node prefers its first leaf because , the middle B-node prefers its first leaf because , and the right B-node prefers its second leaf because . Their propagated utility pairs, from left to right, areAt the root A compares and chooses the left child. Thus the root pair is , with play following the root's left branch and then that B-node's first branch. No tie affects this outcome.
The equilibrium assignment is , with utility vector . Apply backward induction to the finite perfect-information game, accounting for the two friendship pairs in every terminal assignment. Student receives the last room and has no remaining choice. Given the first two rooms, chooses the remaining room maximizing their own room value plus if adjacent to .
The following complete third-stage comparisons summarize the continuations. The utility in the last column is 's resulting utility, after makes the indicated best response.
| room | room | Optimal room | Resulting |
|---|---|---|---|
| or | |||
For example, after takes and takes , student compares , giving , with , giving . Choosing also gives the adjacency bonus, making . The last room is adjacent to 's .
The table makes choose after first-stage choices , respectively. Their resulting consequences for are , and either or . Thus strictly prefers , proving the displayed outcome.
There is an off-path tie for after , so the entire subgame perfect equilibrium strategy profile need not be unique. Either choice, or any mixture of them, gives at most after choosing , below . The equilibrium assignment on the played path is therefore unaffected by this tie. Specifying these optimal continuations at every history, including the unplayed ones, supplies a subgame perfect equilibrium rather than merely a proposed path.
No. Strict room values do not remove the allocation externalities generated by friends. Consider the following new instance, with the same friendship pairs and and friendship bonus for each student:Each row is strictly ranked and every room value is positive. In picking order , backward induction gives the following continuations. Room numbers in a tuple are listed in student order.To check 's incentives behind these continuations, the resulting utilities for their available choices, in ascending room order, are respectively , , and . Student 's own best responses determine those figures, and again takes the remaining room. All comparisons selecting these continuations are strict.
Hence chooses and the subgame perfect equilibrium outcome isBut the feasible assignmentstrictly improves and and leaves unchanged. Thus is not Pareto optimal. This is compatible with equilibrium: a Pareto improvement can require several players' actions to change. If alone takes , the later best responses lead to , not to ; anticipating that reaction gives only .
Minimax search applies because this is a finite, deterministic two-player zero-sum game with perfect information. Each move assigns a previously unassigned Boolean variable, so play terminates after exactly moves. Both players observe the whole partial Boolean valuation, and there are no chance moves. Give terminal positions payoff when the propositional formula is true and when it is false, measured for . At an -node take the maximum child value and at a -node the minimum. Backward induction then computes the winner and a corresponding winning strategy.
Past exam of the mathematics course of the University of Cambridge 2005 iii Paper 27 3 Solution Created 2026-10-03 Updated 2026-10-14
The axiom of determinacy, , says that every infinite game of perfect information in which two players alternately choose natural numbers and Player I wins according to a specified payoff is a determined infinite game. A strategy specifies a move at every finite position where its player moves; it is winning if every compatible infinite play is won by that player.
Finite games are determined by backward induction. For infinite games, open determinacy has a direct proof. Let consist of the finite positions whose extension cylinder sets lie in the open payoff . Build the winning-position attractor in an infinite game by transfinite recursion: start with , add an I-position if some successor has already entered, add a II-position if every successor has already entered, and take unions at limit stages. The process stabilizes because there are only countably many finite positions.
At a position in the attractor but outside , I can choose a successor with strictly smaller entry rank, and every move of II has smaller entry rank. There is no infinite descending sequence of ordinals, so I forces entry into and wins. Outside the attractor, every I-move stays outside it, while II can choose a successor outside it; that strategy avoids forever. Since is open, a play belongs to exactly when some prefix belongs to . Thus II wins from outside the attractor. This proves determination for open payoffs; swapping the players proves it for closed payoffs too. The stronger Borel determinacy theorem gives determination for every Borel set payoff, whereas asserts this for arbitrary payoffs.
To contradict from choice, enumerate both players' strategies as and , where . There are strategies because the set of finite positions is countable; there are also plays following any fixed strategy because the other player's moves are arbitrary. At stage of the choice diagonalization of an undetermined game, choose a fresh play following and then a different fresh play following , avoiding all earlier reservations. This is possible because fewer than plays have been reserved at every ; regularity of is not required.
Set . Every loses on , and every loses on . Thus neither player has a winning strategy, and AD and AC are inconsistent together.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 44 3 b Solution Created 2026-10-03 Updated 2026-10-07
Take the nondegenerate case and an integer trading horizon . For exponential utility, maximize the negative of the exponential loss, equivalently minimize its expectation. Conditional on past information, a predictable choice hasComplete the square:Thus the minimum conditional multiplier is with . Backward induction starts with terminal loss and gives the minimal continuation loss . Independence of the next increment justifies the same conditional minimization for every history, not just deterministic trading plans. Hence exponential-utility trading with Gaussian increments givesThese are constant numbers of shares, not constant wealth fractions. Strategies with infinite exponential loss have expected utility and cannot improve this finite value. If , the usual formula is inapplicable: with trading has no effect, while a nonzero deterministic increment admits unbounded riskless gains and no finite maximizing position.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 44 3 c Solution Created 2026-10-03 Updated 2026-10-07
For a predictable position , the current net wealth increment is conditionally Gaussian with mean and variance . Its exponential-loss multiplier isDifferentiate its quadratic exponent. The unique minimizing position isThe first term is the speculative demand; the second offsets the part of the income correlated with the tradable price increment. Independent period vectors and backward induction justify using this same position at every date. Completing the square gives minimal exponent , whereTherefore hedging a Gaussian income stream with exponential utility has valueThe residual variance is ; it disappears for perfectly correlated income.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 39 4 Solution Created 2026-10-03 Updated 2026-10-06
We derive the probabilities for a sequential elimination all-pay contest from a discounted subgame perfect equilibrium, using backward induction, and only then take . This preserves the selection supplied by discounting.
First consider a two-player all-pay auction with effective prizes , so the incremental payoff is times winning probability minus effort. For , the independent mixed strategies have effort cumulative distribution functionsThe second player has an atom at zero. For positive bids on this support, the first player's payoff is and the second's is . Bids above cannot improve either payoff. The first has no zero atom, so the second's zero bid also earns zero. If the first deviates to zero, it can win only when the second bids zero; even with every such tie resolved in its favor, its payoff is at most . The two-player complete-information all-pay equilibrium therefore has winning probabilitiesThese follow by integrating against the uniform . A third player with effective prize at most cannot profit by entering: for , its winning probability is , giving payoff at most zero; above its effort exceeds its prize.
For the dynamic induction, relabel any remaining subgame's valuations as , with prizes left. Define the backward-induction threshold in an elimination all-pay contestFor the sum is empty and . The discounted continuation value in an elimination contest is obtained from the following net utilities:The base case is the one-prize all-pay auction: only the two highest valuations need positive effort, with prizes and payoffs . Every lower player has a nonprofitable deviation by the preceding calculation.
For , if either of the top two wins, the other becomes the highest player in a subgame with prizes. The continuation threshold in either such subgame is the same numberThe remaining top player's continuation payoff is . Its effective prize in a sequential contest, net of the discounted payoff from losing, is thereforeThus for , and the two-player distributions above apply. Adding the losing-state baselines giveswhich agree with the proposed formulas.
For a player of rank , the inductive continuation utility after either top player wins is identical: its new rank is , and the utility expression depends only on its own value and the lower-valued tail. Thus its current zero-effort payoff is that common continuation value multiplied by , exactly the stated . Its effective prize for deviating to win now is . For , direct subtraction givesFor , , since the coefficients in are nonnegative and sum to one. Such a player cannot gain by entering against the two active players. There is one additional zero-bid deviation to check for the highest player. If both active bids become zero, the tie could award a prize to any remaining player. Losing to any player below rank gives no greater continuation utility than losing to rank : deleting rank makes the ordered remaining rival list componentwise smallest, and its continuation threshold is a nonnegative weighted sum of that list. Thus even resolving every all-zero tie in the highest player's favor gives payoff at most its usual losing baseline plus . No tie rule can improve this deviation. This verifies all best responses and the continuation-utility formulas. Applying the construction to every remaining-player set proves a subgame perfect equilibrium of the discounted contest, not merely an on-path prescription.
Now take the vanishing-discount limit of an elimination all-pay contest. At every nonfinal subgame,Thus the two highest remaining players win with equal probabilities in a nonfinal stage. In the final stage the effective prizes are their actual valuations, so its lower-valued participant beats the higher one with probability equal to half their valuation ratio.
Return to the original ranks. Only the original top can ever win; at most higher players can have left before the final stage, so players of rank or worse never enter its top pair. Player must lose fair nonfinal contests to remain unawarded until the final stage, where its opponent has value . HenceA player first enters the top pair at stage , after higher-ranked winners have left. To remain unawarded, it must lose the nonfinal contests from then on, followed by the final contest against rank . ThereforeThere are exactly distinct winners, so the expected value of their indicator sum is . Combining these calculations givesThis proves the ranked winning probabilities in an undiscounted elimination contest. When , it reduces to the ordinary two-player all-pay winning probabilities; when , the repeated fair stages explain each power of .
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 4 28J b Solution Created 2026-09-24 Updated 2026-10-05
For any finite contingent claim measurable at the final date in the natural binomial tree, backward induction givesAt a node with stock , let be its two successor values. Hold, during the next period,The stock and bank holdings reproduce both successor values and cost . Rebalancing at every node is self-financing, and terminal value is . Thus every such claim is replicated and the no-arbitrage price is unique.

