= Cost-weighted finite search game
{title2=$v=(c^2+\sum_i c_i^2)/(2c)$}
Consider a <zero-sum game> in which a hider selects one of $n$ locations and a searcher inspects locations until finding it. Inspection costs are $c_i>0$, paid also at the discovered location; the hider maximizes total cost and the searcher minimizes it. Put $c=\sum_i c_i$. The <value of a zero-sum game> is
$$
v=\frac{c^2+\sum_i c_i^2}{2c}.
$$
The hider uses <probabilities> $c_i/c$. Every complete search order then has the same <expected payoff>: summing each cost multiplied by the probability that its location or a later one hides the object gives $(\sum_i c_i^2+\sum_{i<j}c_ic_j)/c=v$.
For the searcher's matching guarantee, inspect location $i$ first with <probability> $c_i/c$, then inspect the remaining locations in a uniformly random order. For distinct $i,j$, the probability that $i$ precedes $j$ is
$$
\frac{c_i}{c}+\frac{c-c_i-c_j}{2c}=\frac12+\frac{c_i-c_j}{2c}.
$$
If the object is at $j$, expected total cost is therefore $c_j+\sum_{i\ne j}c_i\Pr(i\text{ precedes }j)=v$. Both guarantees hold for every opponent choice, proving optimality for any finite number of locations, including the three-location case.
Back to article page