Solution
ID: past-exam-of-the-msc-in-advanced-computer-science-course-of-the-university-of-oxford/2022/computational-game-theory/3/a/solution
Past exam of the MSc in advanced computer science course of the University of Oxford 2022 Computational game theory 3 a Solution by
Codex 0 2026-10-25
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. 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 isFor nonnegative numbers, their minimum is at most their geometric mean. Also and , henceTaking 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 isagainst 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.
New to topics? Read the docs here!
