= Search game
A search game models a strategic interaction between a searcher and an opponent choosing what is hidden, where it is hidden, or how it moves. The searcher chooses a search policy; the payoff may be detection probability, discovery time or search cost. The information and allowed motion must be stated before solving the game.
For a simple <zero-sum game>, an object is hidden at one of two locations. Checking either location costs one time unit and always detects the object if present. Searching location one first with probability $p$ gives expected discovery times $2-p$ when the object is there and $1+p$ when it is at location two. Minimizing the worst case sets $p=1/2$, with value $3/2$.
A deterministic first choice permits the hider to force time two. Thus <mixed strategies> have a concrete value even in this small example. Adding unequal travel costs or an evading target changes both the strategy space and the optimization problem.
Back to article page
