Past exam of the computer science course of the University of Oxford / 2020 / Artificial intelligence / 3 / e / Solution

Propagate an entire utility pair from a child chosen to maximize the component of the player whose turn it is. This is the two-player case of max-n search. At a terminal node let $V(s)=(U_A(s),U_B(s))$. At an A-node chooseand at a B-node replace $V_A$ by $V_B$. Do not maximize the two coordinates independently: their separate maxima may belong to incompatible outcomes. Fix a tie rule, such as the first child in the specified order. The rule recursively gives a pure strategy subgame perfect equilibrium in a finite perfect-information game: backward induction makes the moving player's selected continuation a best response at every node.^[ref]

In the original Figure 2, each of the three children of the root belongs to B. The left B-node prefers its first leaf because $1>0$, the middle B-node prefers its first leaf because $2>-2$, and the right B-node prefers its second leaf because $3>1$. Their propagated utility pairs, from left to right, areAt the root A compares $1,-1,-1$ and chooses the left child. Thus the root pair is $(1,1)$, with play following the root's left branch and then that B-node's first branch. No tie affects this outcome.