Solution

ID: past-exam-of-the-msc-in-advanced-computer-science-course-of-the-university-of-oxford/2022/computational-game-theory/3/a/solution

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 or . 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 be player 1's initial probability of and her later probability of . These are separate information sets, so and need not be equal; their random draws are independent. Name player 2's unlabeled branches left and right, and let be the probability of taking the left branch. The only unit-payoff paths are left–left–left and right–right–right. Consequently
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 is
For nonnegative numbers, their minimum is at most their geometric mean. Also and , hence
Taking makes both possible branch-conditioned success probabilities , so this upper bound is attained against every . Thus the optimal guaranteed behavioural strategy success probability is .
A mixed strategy can instead select the complete plan with probability and the complete plan with probability . The two choices within a sampled plan are correlated. If player 2 chooses left, exactly the sampled plan succeeds; if player 2 chooses right, exactly succeeds. Therefore the success probability is
against every opposing mixed strategy. It is optimal among mixed strategies too: player 2's uniform mixture gives success probability to each of and zero to , so no mixture of the four plans can exceed against that opponent. This establishes mixed and behavioural security levels without perfect recall directly.
Figure 1.
Independent behavioural choices guarantee at most , whereas a mixed plan correlates the choices and guarantees
. Details.
The guarantee qualification matters: if player 2's branch were known to be left, the deterministic plan would succeed with probability one. The number is not an upper bound against every fixed opposing choice separately.

New to topics? Read the docs here!