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.
With ordered values and prizes remaining, define . In the recursively constructed discounted subgame perfect equilibrium, it is the second active player's effective prize and the effort-support upper endpoint. The highest player's utility is . The coefficients form a convex combination, so , allowing lower-player deviations to be bounded.
Let a proposer divide a pie of size by continuously offering its responder . Rejection gives fixed continuation payoffs to the proposer and to the responder, with and . Then a subgame perfect equilibrium must have the responder accept with probability one. The proposer offers exactly , retaining .
Sequential rationality forces rejection for and acceptance for . If acceptance at had probability , that offer would give the proposer . Every larger offer gives less than and can be improved by a smaller offer still above ; every smaller offer gives . The supremum would therefore be unattained. Randomizing offers cannot attain it either: the nonnegative gap from would be strictly positive almost surely and hence have positive expectation. No best response would exist, contradicting equilibrium. Acceptance at removes this gap and makes the unique optimal proposal. The assumptions and exclude degenerate indifference of the proposer.
A family of results describing the large set of Nash equilibrium payoffs available in indefinitely repeated interaction. For a finite game with observed past play, the discounted Nash version supports any feasible, strictly individually rational payoff in a repeated game when players are sufficiently patient.[ref]
The mechanism is to prescribe a path and punish the first deviator by holding that player's future payoff to its minmax payoff. With long-run average payoffs, a finite gain disappears from the average; with discounting, the promised future loss must outweigh the gain. Weak boundary points require care when a stated theorem assumes strict inequalities. A construction proving a Nash equilibrium need not prove a subgame perfect equilibrium, because the punishers' continuation incentives may fail.
Grim trigger 2026-10-14
A grim trigger is a history-dependent pure strategy in a repeated game that switches permanently to punishment after a trigger event. In the iterated prisoner's dilemma above, the trigger is any player's observed defection, and punishment is always defect. Unlike Tit for tat, grim trigger never restores cooperation after the opponent cooperates again. Whether mutual grim trigger is a subgame perfect equilibrium depends on the stage payoffs, discount factor, and monitoring assumptions; it is not an unconditional property of the rule. See Ozdaglar, lecture 15, slides 12–15.
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 payoff
The 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]. 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 therefore
Cooperation is a best response precisely when
Equivalently, without normalization the geometric series gives
Multiplying both unnormalized payoffs by the same positive factor leaves the best response comparison unchanged.
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.
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.
Suppose each participant has at most one mutual friend, each friendship pair chooses consecutively, room values lie in and are distinct for each participant, and each friendship bonus exceeds . Then every subgame perfect equilibrium outcome of serial dictatorship is Pareto optimal.
For a friend pair, if any remaining adjacent room pair exists, the leader chooses their uniquely best room having an available neighbor; the follower chooses their uniquely best available neighbor. Adjacency dominates every possible difference in own-room value for both friends. If no adjacent room pair remains, neither friend can obtain a bonus and each chooses their unique best available room. A participant without a friend also chooses their unique best available room.
For the proof, compare a purported Pareto improvement block by block, where a block is a single participant without a friend or one consecutive friendship pair. Earlier fixed blocks leave the same rooms available. A block receiving adjacency cannot lose it in a weak improvement. Its leader must retain the uniquely best eligible room, and its follower must retain the uniquely best neighboring room. Without available adjacency, both rooms are fixed by strict own-room rankings. Mathematical induction fixes every assignment, excluding a strict improvement.
A game tree is a rooted tree representing successive histories. A nonterminal vertex specifies the player who moves, its outgoing edges are the available actions, and each leaf specifies a terminal payoff for every player. A pure strategy specifies an action at every decision point belonging to that player, including decision points not reached by the eventual play.
For a perfect-information game, each player observes the exact preceding history. An extensive-form game with imperfect information additionally groups indistinguishable decision points into information sets, with compatible available actions. Chance moves, if present, carry specified probabilities; the displayed game has none. A subgame perfect equilibrium must prescribe a Nash equilibrium in every proper subgame as well as in the whole game.
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 are
For 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.
Yes: let the order be voter 2, then voter 3, then voter 1. When voter 1 moves last, it makes win whenever that is possible; otherwise it prefers to . For the first two votes in this new order, its optimal continuation winners are
Rows now record voter 2's initial choice and columns voter 3's choice. In a three-way split, the specified tie-break produces , which explains, for example, the off-diagonal entry.
Voter 3 optimizes its ranking in each row, giving the continuation winners . Voter 2 then chooses , its favourite of the three. The winner is therefore in every subgame perfect equilibrium, again by unique outcome under strict outcome preferences. In particular, if voter 2 starts with , voter 3 must also vote : either other vote lets the last voter force .
In the final round, player 1 strictly accepts every . In any subgame perfect equilibrium it must also accept with probability one. Otherwise, if that acceptance probability were , offering zero would give player 2 only . A sufficiently small positive offer would be accepted and yield more. No positive offer maximizes player 2's payoff either, because a smaller positive offer improves it. The same supremum argument rules out a mixed offer distribution attaining the missing maximum. Thus the final-round equilibrium uniquely has , accepted, with payoffs .
In round one, player 2 therefore rejects and accepts . At it is indifferent, but equilibrium again forces acceptance with probability one: if acceptance were less likely, player 1 could improve on any proposed optimum with an offer just above . Since , player 1 strictly prefers the resulting positive payoff to rejection.
Consequently the unique equilibrium outcome is immediate agreement at , giving payoffs . The full strategies are: player 1 offers initially and accepts every nonnegative final offer; player 2 accepts initial offers at least , rejects smaller ones, and offers zero in every reached final-round subgame. These prescriptions cover off-path histories too. Acceptance at indifference follows from the continuous-offer bargaining acceptance lemma, rather than an arbitrary tie-breaking convention.
Write , where . For three distinct sites , the left, middle and right firms receive respectively
These follow by counting the two midpoint boundaries, including split ties. Therefore, after two firms occupy , the final entrant compares at , at , and at every available interior site. Omit an unavailable region and retain every maximizing tie. This is the final entrant payoff in a discrete location game.
First suppose opens at the central site . If chooses , the final entrant's best possible payoffs on the left, right and interior are at most , exactly , and at most , respectively. Hence 's unique best response is . The resulting payoff to is , uniquely maximized on that side at . Reflection gives the other optimal choice , followed by . Under either choice, receives only . Any mixture of the tied optimal second-mover choices has the same consequence.
Now let deviate to . If chooses , the unique final best response is , yielding at most . If chooses , the unique final best response is , yielding only two. Both classes will be strictly inferior to an available alternative, independently of how later ties are resolved:
  • If , can choose . The final entrant compares , and , so uniquely chooses . This gives exactly .
  • If , can choose site four after chooses two. All three remaining sites are final-mover best responses; they give payoffs five, four and three. Thus guarantees at least three, exceeding the excluded choices' payoff two.
Accordingly, in every subgame perfect equilibrium continuation after , the second mover must choose a site . This remains true with mixed strategies: every excluded choice pays strictly less than the displayed guaranteed alternative, under every possible continuation tie policy.
For any such , every legal final site gives at least three. If lies left of , then is the middle firm and receives . If lies right of , then is the left firm and receives . Thus the deviation gives at least , against every subgame-perfect continuation, whereas the central opening gives it .
Figure 1.
Final-mover ties and the second mover's guarantee after the first firm deviates on a nine-building street
. Details.
In this original example, a final-mover tie produces the line segment for : its points are expected payoff pairs from a mixed strategy over two final best responses. The second mover can independently secure eight by choosing , so only the segment to the right of that guarantee can support its optimal choice. Mixing over a tied final response cannot make the first mover's payoff fall below three.
A subgame perfect equilibrium must prescribe optimal continuation play even after the first mover's off-path deviation. Since the deviation is strictly profitable under every such prescription, no subgame perfect equilibrium can have open centrally. The argument does not select favourable ties or assume that off-path players cooperate with the deviator.
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 choose
and 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]
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, are
At 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 roomOptimal roomResulting
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 is
But the feasible assignment
strictly 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 .
Every subgame perfect equilibrium outcome is Pareto optimal under the stated consecutive-friend and bonus conditions. Partition the choosing order into blocks: a single student without a friend, or two friends who choose consecutively. Their slots in the choosing order are adjacent; the proof must separately establish when their allocated rooms will be adjacent.
Let be the rooms remaining before a friend block, with leader and follower . Because and , each friend strictly prefers every adjacent-to-friend allocation to every nonadjacent one. After leader takes room with an available adjacent room, follower therefore takes their uniquely highest-valued room among the available neighbors of . The leader consequently knows they will receive the adjacency bonus.
If contains at least one pair of adjacent rooms, let be its nonisolated rooms: the rooms having an available neighbor. Leader must choose from , because choosing there guarantees utility greater than , whereas an isolated choice gives at most . Since the bonus is then fixed and room values are distinct, the leader chooses their unique maximum-value room in . The follower chooses their unique best neighbor. Later students cannot change either allocated room, so later play cannot alter these two students' utilities.
If contains no adjacent pair, neither friend can obtain the bonus under any allocation of rooms from . Both simply choose their uniquely most valuable remaining room in turn. Removing rooms cannot create a new physical adjacency, so no hidden later move can change that conclusion. A one-student block likewise chooses their unique best available room.
Now compare the equilibrium assignment with any proposed Pareto improvement . Induct over these blocks, assuming earlier blocks' rooms are already fixed. Thus and have the same remaining set at the present block. A lone student's room must stay fixed by strict preferences.
For a friend block obtaining adjacency in , both students must retain adjacency in : losing a bonus larger than cannot be compensated by any room-value increase. The leader's room in must therefore belong to . It cannot differ from the unique highest-valued room the leader selected there without reducing that leader's utility. Once the leader's room is fixed, the follower likewise must retain the uniquely best available neighbor. If has no adjacent pair, both rooms stay fixed by the ordinary strict-ranking argument.
Thus every block's rooms are unchanged. The only assignment weakly improving all students is itself, so no strict improvement is possible. This proves Pareto efficiency of serial dictatorship with consecutive friends. The proof applies to every subgame perfect equilibrium, since the required choices at each block are strict best responses determined by the available rooms.
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 functions
The 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 probabilities
These 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 contest
For 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 number
The remaining top player's continuation payoff is . Its effective prize in a sequential contest, net of the discounted payoff from losing, is therefore
Thus for , and the two-player distributions above apply. Adding the losing-state baselines gives
which 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 gives
For , , 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 . Hence
A 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 . Therefore
There are exactly distinct winners, so the expected value of their indicator sum is . Combining these calculations gives
This 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 .
Measure all payoffs in millions of dollars, in the order (Ann, Bob). Since both players maximize expected money, those numbers are already their expected utility scale.
In the extensive-form game, Ann moves first. Staying out terminates at . Entering leads to Bob's observed decision between fighting, with terminal payoffs , and acquiescing, with terminal payoffs . Each decision node is its own information set, so this is a perfect-information game.
The corresponding normal-form game gives Ann the pure strategies (stay out) and (enter), and Bob the complete contingent pure strategies (fight if entry occurs) and (acquiesce if entry occurs). The payoff matrix is
The pure strategy Nash equilibria are and . Against , Ann prefers ; against , Ann prefers . When Ann stays out, Bob's contingent response does not affect his payoff, so is a best response there.
There is exactly one subgame perfect equilibrium, . In the subgame following entry, Bob strictly prefers to , so backward induction selects acquiescence; Ann then strictly prefers entering for to staying out for . The threat supporting is not optimal in that one-shot subgame.
For infinite repetition, the paper specifies no discount factor. First take the long-run average payoff convention, with all past actions observed. The feasible payoff set is the convex hull
Ann can guarantee in every stage by staying out; Bob can guarantee at least in every stage by acquiescing whenever entry occurs. These guarantees are also their minmax payoffs: fighting holds Ann's best possible stage payoff to , and entering holds Bob's best possible stage payoff to .
Therefore the sustainable Nash equilibrium average payoffs are exactly the feasible, weakly individually rational payoffs in a repeated game:
This is the closed triangle with vertices .
Here is a direct sufficiency argument for this particular game. Choose a publicly known sequence of stage outcomes whose frequencies give the target point. Before any observed deviation, follow that sequence. After an Ann deviation, Bob fights forever, so Ann can thereafter obtain at most per stage. After a Bob deviation, Ann enters forever, so Bob can thereafter obtain at most per stage. A finite prefix has no effect on long-run average payoff, so no unilateral deviation improves a target with . Rational frequencies can be implemented periodically; arbitrary real frequencies can be implemented by a deterministic sequence with convergent frequencies. Thus even the weak boundary is covered here. In particular, staying out forever and entry followed by acquiescence forever are sustainable; fighting forever is not.
For discounted payoffs , the folk theorem for repeated games instead gives the usual patience qualification: every feasible point with can be sustained for all sufficiently large . It does not classify the whole region for an unspecified fixed . The two one-shot Nash equilibrium outcomes remain sustainable for every .[ref]
Finally consider the particular history-dependent pair in the paper. Initially Bob has never acquiesced, so Ann stays out. That preserves the same condition forever, giving payoffs . The pair is a Nash equilibrium. Holding Bob's strategy fixed, Ann cannot induce an acquiescence: he fights whenever she enters, and his rule never changes unless he has previously acquiesced. Every entry would give her instead of , so no unilateral deviation helps. Holding Ann's strategy fixed, Bob never reaches a decision node because she stays out; changing his strategy alone cannot create a history in which he actually acquiesces. Hence he also cannot improve.
This direct argument works for both discounted and long-run average payoffs. The outcome gives Ann exactly her minmax payoff and Bob more than his, so it is compatible with the folk theorem for repeated games. A version requiring strict gains above both minmax payoffs is a sufficient condition, and cannot be used to rule out this boundary example.
Perfect-information game 2026-10-24
An extensive-form game in which each information set contains a single decision node. Each acting player knows the entire preceding sequence of moves. Finite games with this property can be solved for a subgame perfect equilibrium by backward induction.