Max-n search (${\max }^n$)

Backward induction with an $n$-component utility vector. At a node controlled by player $i$, evaluate each child, choose a child maximizing coordinate $i$ and copy its entire vector. A fixed tie rule makes the returned vector well defined. By mathematical induction from terminal positions, the selected continuation is a best response at every node of a finite perfect-information game, giving a pure strategy subgame perfect equilibrium. The vector must be copied intact; separate coordinatewise maxima need not describe any attainable outcome.

Suppose every terminal pair satisfies $|U_A+U_B|\le ϵ$. At a B-node with immediate A-parent, let $\alpha$ be the A-coordinate of a completed alternative already retained by the parent. If a completed B-child supplies B-coordinate $y$, then every eventual B-selected pair $(u,v)$ has $v\ge y$ and hence $u\le ϵ-y$. Therefore $ϵ-y<\alpha$ permits discarding this B-option and skipping its remaining children. Equality is also safe if the parent keeps its existing option on a tie.

The inequality remains valid at completed subtrees because max-n search copies one terminal pair. If the observed pair is $(x,y)$, then $x+y\ge -ϵ$, so $u\le x+2ϵ$ and $x+2ϵ\le \alpha$ is a weaker sufficient test. At $ϵ=0$ this reduces to the usual MIN-node alpha-beta pruning cutoff. A discarded option is not assigned a fabricated exact pair; the proof uses a certified alternative at the immediate parent.