An Algorithmic Approach to Search Games: Finding Solutions Using Best Response Oracles.

We present efficient algorithms for computing optimal or approximatelyoptimal strategies in a zero-sum game for which Player I has n pure strategiesand Player II has an arbitrary number of pure strategies. We assume that forany given mixed strategy of Player I, a best response or "approximate" bestresponse of Player II can be found by an oracle in time polynomial in n. Wethen show how our algorithms may be applied to several search games withapplications to security and counter-terrorism.