Past exam of the mathematics course of the University of Cambridge / 2013 / ib / Paper 1 / 8H (Optimization)

In a zero-sum game with the row player maximizing, a sufficient saddle certificate is that $p,q$ are probability vectors andEvery row mixture then gains at most $v$ against $q$, and every column mixture concedes at least $v$ against $p$. Their pairing must equal $v$, proving optimality.

For the cost-weighted finite search game, order Colin's six columns as $123,132,213,231,312,321$ and Rowena's rows as $1,2,3$. The payoff matrix isUnder the proposed search mixture, an alternative location $i$ precedes the hiding location $j$ with probability $(c_i+c_k/2)/c$, where $k$ is the third location. The expected cost conditional on hiding at $j$ is consequentlyIt is independent of $j$, giving the upper bound $\mathrm{value}\le v$.

Choose $p_i=c_i/c$. Against any order $i,j,k$, its expected cost isThis gives the matching lower bound. ThusBoth strategies equalize the opponent's pure actions, giving the stated saddle certificate.