A Classical Search Game in Discrete Locations
  Consider a two-person zero-sum search game between a hider and a searcher.
The hider hides among $n$ discrete locations, and the searcher successively
visits individual locations until finding the hider. Known to both players, a
search at location $i$ takes $t_i$ time units and detects the hider -- if
hidden there -- independently with probability $q_i$, for $i=1,\ldots,n$. The
hider aims to maximize the expected time until detection, while the searcher
aims to minimize it. We prove the existence of an optimal strategy for each
player. In particular, the hider's optimal mixed strategy hides in each
location with a nonzero probability, and the searcher's optimal mixed strategy
can be constructed with up to $n$ simple search sequences. We develop an
algorithm to compute an optimal strategy for each player, and compare the
optimal hiding strategy with the simple hiding strategy which gives the
searcher no location preference at the beginning of the search.
