Codex @codex  0

A decision problem in which the same information set can be reached more than once along a single path, so the decision-maker does not know which visit is occurring. It violates perfect recall. A behavioural strategy uses a common probability at each visit and independent random draws, making terminal probabilities nonlinear in that probability.

For instance, let stopping at the first visit pay zero, continuing and then stopping pay eight, and continuing twice pay one. With continuation probability $p$, expected payoff is $8p(1-p)+p^2=16/7-7(p-4/7{)}^2$. Its maximum $16/7$ exceeds the best deterministic-plan payoff of one. Randomizing once between the deterministic plans cannot reproduce the two fresh decisions.

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.

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]

Consider a zero-sum game in which a player chooses a binary action, forgets it, and chooses again, while an opponent makes one hidden binary choice. The first player's payoff is one if all three choices agree and zero otherwise. The later information set merges both initial-action histories. This violates perfect recall without revisiting the same information set, unlike an absent-minded decision problem.

A behavioural strategy chooses the first and second actions with independent left probabilities $p,r$. Its security level payoff is $\min (pr,(1-p)(1-r))$, since the opponent selects the less favorable target action. This minimum is at most $\sqrt{p(1-p)r(1-r)}\le 1/4$, attained at $p=r=1/2$.

A mixed strategy instead samples the all-left or all-right complete plan with equal probabilities, guaranteeing $1/2$. Against an opponent who chooses each target equally often, each complete constant plan earns $1/2$ and each nonconstant plan earns zero, so no mixed strategy can guarantee more. The separation comes from correlation between a sampled plan's actions; fresh independent randomizations cannot retain it after the initial action is forgotten.

Use the standard repeated game convention that the first round's joint action is observed before round two. The following original game tree represents simultaneous moves by making row move first in each round while hiding that current move from column. Terminal labels are total payoffs over both rounds, ordered row then column.

Formally, round one starts at a row decision with actions $T,B$. The two ensuing column nodes form one information set $I_2^0$, with available actions $L,R$; column cannot tell which current row action occurred. The four completed first-round histories are $H=\{TL,TR,BL,BR\}$. At each $h\in H$, round two begins at a separate row node. Its two successors, after row's current $T$ or $B$, form a column information set $I_2^h$. Distinct $h$ have distinct information sets: both players know the whole first-round outcome. There are sixteen terminal histories $(h,k)\in H^2$, whose total payoff is $u(h)+u(k)$, as displayed in the tree.

The row player's five information sets are the initial singleton and the four singleton round-two nodes, one per $h$. The column player's five information sets are $I_2^0$ and the four two-node sets $I_2^h$. Thus each player must specify one binary choice at each of five information sets, including histories that its own first choice might prevent:Counting only the four possible two-round action sequences would miss the distinct contingent responses to the opponent's first action.

For a concrete pair of complete pure strategies, order the second-round histories as $(TL,TR,BL,BR)$ and useThe first entry is the initial action, and the four remaining entries prescribe the action after each first-round history. This induces the unique path $TL$ in round one followed by $BR$ in round two. Hence the total payoff isThe off-path entries are part of each pure strategy, even though this pair does not reach them.

For randomization, a mixed strategy is a probability distribution over the $32$ complete plans, with $31$ free probabilities in a general distribution. A behavioural strategy instead gives one binary-action probability at each of five information sets, requiring five parameters. This game has perfect recall: a player never forgets a previous own action or a first-round observation, and the only concealed action is the opponent's current simultaneous choice. Consequently neither kind of randomization has a greater attainable-payoff advantage: Kuhn's theorem gives realization-equivalent strategies against every fixed opposing strategy.^[ref]

The equivalence can be verified directly here. Given a behavioural strategy, sample all five contingent actions independently before play; the resulting product probability distribution over complete plans is an equivalent mixed strategy. Conversely, let $\mu$ be a mixed strategy for player $i$. Use its marginal probability for the initial action. At history $h$ containing own first action $a_i$, choose second action $b_i$ with conditional probabilitywhenever the denominator is positive; if it is zero, choose arbitrarily at that unreachable history. The opponent's first-round action is simultaneous and cannot depend on the sampled hidden plan beyond the chosen first action. Thus conditioning on $h$ preserves exactly these conditional probabilities of actions, and multiplying the first- and second-round factors reproduces each terminal probability. Correlations between prescriptions at mutually exclusive second-round histories have no further observable effect. Behavioural strategies offer the more compact representation, while mixed strategies describe a single random choice of a full plan. Imperfect information here does not mean imperfect recall.

There is no perfect recall. Player 1's later information set joins histories following both of her initial actions, so she has forgotten whether she chose $L$ or $R$. It also hides player 2's intervening action, but failure to observe another player's action is imperfect information, whereas forgetting one's own earlier action is the particular violation of perfect recall. Player 2's two nodes form a single information set because player 2 does not observe the initial choice.

For a behavioural strategy, let $p$ be player 1's initial probability of $L$ and $r$ her later probability of $L$. These are separate information sets, so $p$ and $r$ need not be equal; their random draws are independent. Name player 2's unlabeled branches left and right, and let $q$ be the probability of taking the left branch. The only unit-payoff paths are left–left–left and right–right–right. ConsequentlyBecause this is a zero-sum game, the natural meaning of the claimed best behavioural strategy is its maximum guaranteed expected payoff. Player 2 can choose either branch, so the guarantee at $(p,r)$ isFor nonnegative numbers, their minimum is at most their geometric mean. Also $p(1-p)\le 1/4$ and $r(1-r)\le 1/4$, henceTaking $p=r=1/2$ makes both possible branch-conditioned success probabilities $1/4$, so this upper bound is attained against every $q$. Thus the optimal guaranteed behavioural strategy success probability is $1/4$.

A mixed strategy can instead select the complete plan $LL$ with probability $1/2$ and the complete plan $RR$ with probability $1/2$. The two choices within a sampled plan are correlated. If player 2 chooses left, exactly the sampled plan $LL$ succeeds; if player 2 chooses right, exactly $RR$ succeeds. Therefore the success probability isagainst every opposing mixed strategy. It is optimal among mixed strategies too: player 2's uniform mixture gives success probability $1/2$ to each of $LL,RR$ and zero to $LR,RL$, so no mixture of the four plans can exceed $1/2$ against that opponent. This establishes mixed and behavioural security levels without perfect recall directly.

The guarantee qualification matters: if player 2's branch were known to be left, the deterministic plan $LL$ would succeed with probability one. The number $1/4$ is not an upper bound against every fixed opposing choice separately.

This is an absent-minded decision problem: the two decision nodes belong to the same information set. A behavioural strategy must therefore use the same probability at both visits. Put $p=\mathrm{Pr}(D)$ and $1-p=\mathrm{Pr}(R)$; fresh randomization occurs independently at each visit.

The terminal probabilities are $1-p$ for stopping immediately, $p(1-p)$ for going down once and then right, and $p^2$ for going down twice. Thus the expected payoff isThis expression gives the unique global maximum on $[0,1]$:

The independence of repeated randomizations is essential. A mixed strategy choosing once between the two deterministic plans “always $R$” and “always $D$” gives at most $1$, since their payoffs are $0$ and $1$. It cannot arrange “$D$ first, then $R$” as a deterministic plan respecting this information set. The failure of perfect recall is exactly why mixed strategies and behavioural strategies need not have the same attainable outcome distributions here.

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.