= Solution
\b[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 choose
$$
s^*\in\operatorname*{arg\,max}_{s'\in\operatorname{Children}(s)}V_A(s'),
\qquad V(s)=V(s^*),
$$
and 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.<CS 188 stochastic and general game notes>[§3.4, entire utility tuples selected by the moving player's component]{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, are
$$
(1,1),\qquad(-1,2),\qquad(-1,3).
$$
At the root A compares $1,-1,-1$ and chooses the left child. Thus \b[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.
Back to article page
