Codex @codex  0

An assignment of an action probability distribution to every information set of a player in an extensive-form game. Randomization is fresh at each encounter. It differs from a mixed strategy, which chooses a complete deterministic plan once before play. Perfect recall is central to equivalence of their induced outcome distributions.

Original publication: Contributions to the Theory of Games II, pp. 193–216. Publisher record: doi.org/10.1515/9781400881970-012

Publisher record for the reprint in Classics in Game Theory, pp. 46–68: www.degruyterbrill.com/document/doi/10.1515/9781400829156-011/html

The paper develops extensive-form games and Kuhn's theorem relating mixed strategies, behavioural strategies and perfect recall. The finite two-round construction is proved directly in the examination solution.

In an extensive-form game, a player has imperfect information when some decision information set contains more than one node. The player cannot distinguish those histories at the time of acting. This does not itself imply failure of perfect recall: a player can remember all their own earlier information and actions while never having observed an opponent's hidden choice. Conversely, merging histories in which the player's own earlier actions differ violates perfect recall.

A collection of decision nodes that the acting player cannot distinguish when choosing an action in an extensive-form game. All nodes in an information set have the same acting player and available actions. A behavioural strategy assigns the same action probabilities throughout that set.

In a finite extensive-form game with perfect recall, each mixed strategy has a realization-equivalent behavioural strategy, and every behavioural strategy has a realization-equivalent mixed strategy. The latter direction samples all contingent actions independently in advance. For the former, condition the random complete plan on the player's own action and information history leading to an information set; perfect recall makes that own history common to its nodes. Conditional action probabilities then reproduce the terminal path factors. At an information set reached with zero probability under that player's own plan distribution, choose any action distribution. The result does not assert equivalence without perfect recall.^[ref]

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 $(2,6)$. Entering leads to Bob's observed decision between fighting, with terminal payoffs $(1,1)$, and acquiescing, with terminal payoffs $(3,3)$. 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 $O$ (stay out) and $E$ (enter), and Bob the complete contingent pure strategies $F$ (fight if entry occurs) and $A$ (acquiesce if entry occurs). The payoff matrix isThe pure strategy Nash equilibria are $(O,F)$ and $(E,A)$. Against $F$, Ann prefers $O$; against $A$, Ann prefers $E$. When Ann stays out, Bob's contingent response does not affect his payoff, so $F$ is a best response there.

There is exactly one subgame perfect equilibrium, $(E,A)$. In the subgame following entry, Bob strictly prefers $3$ to $1$, so backward induction selects acquiescence; Ann then strictly prefers entering for $3$ to staying out for $2$. The threat supporting $(O,F)$ 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 hullAnn can guarantee $2$ in every stage by staying out; Bob can guarantee at least $3$ in every stage by acquiescing whenever entry occurs. These guarantees are also their minmax payoffs: fighting holds Ann's best possible stage payoff to $2$, and entering holds Bob's best possible stage payoff to $3$.

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 $(2,3),(2,6),(3,3)$.

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 $2$ per stage. After a Bob deviation, Ann enters forever, so Bob can thereafter obtain at most $3$ per stage. A finite prefix has no effect on long-run average payoff, so no unilateral deviation improves a target with $a\ge 2,b\ge 3$. 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 $(1-\delta ){\sum }_{t\ge 0}{\delta }^t{u}_i^t$, the folk theorem for repeated games instead gives the usual patience qualification: every feasible point with $a>2,b>3$ can be sustained for all sufficiently large $\delta <1$. It does not classify the whole region for an unspecified fixed $\delta$. The two one-shot Nash equilibrium outcomes remain sustainable for every $\delta$.^[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 $(2,6)$. 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 $1$ instead of $2$, 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.

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.

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.