Past exam of the computer science course of the University of Oxford / 2018 / Computational game theory / 2 / a / Solution

A game tree is a rooted tree representing successive histories. A nonterminal vertex specifies the player who moves, its outgoing edges are the available actions, and each leaf specifies a terminal payoff for every player. A pure strategy specifies an action at every decision point belonging to that player, including decision points not reached by the eventual play.

For a perfect-information game, each player observes the exact preceding history. An extensive-form game with imperfect information additionally groups indistinguishable decision points into information sets, with compatible available actions. Chance moves, if present, carry specified probabilities; the displayed game has none. A subgame perfect equilibrium must prescribe a Nash equilibrium in every proper subgame as well as in the whole game.