= Solution
There is \b[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. Consequently
$$
\Pr(u_1=1)=qpr+(1-q)(1-p)(1-r).
$$
Because 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)$ is
$$
g(p,r)=\min\{pr,(1-p)(1-r)\}.
$$
For nonnegative numbers, their minimum is at most their <geometric mean>. Also $p(1-p)\le1/4$ and $r(1-r)\le1/4$, hence
$$
g(p,r)\le\sqrt{p(1-p)r(1-r)}\le\frac14.
$$
Taking $p=r=1/2$ makes both possible branch-conditioned success <probabilities> $1/4$, so this upper bound is attained against every $q$. Thus \b[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> is
$$
\tfrac12q+\tfrac12(1-q)=\boxed{\tfrac12}
$$
against 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.
\Image[/past-exam-of-the-msc-in-advanced-computer-science-course-of-the-university-of-oxford/2022/computational-game-theory-imperfect-recall-security.png]
{title=Independent behavioural choices guarantee at most $1/4$, whereas a mixed plan correlates the choices and guarantees $1/2$}
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.
Back to article page
