Optimal pure strategies for a discrete search game

Thuy Bui, Thomas Lidbetter, Kyle Y. Lin

Research output: Contribution to journalArticlepeer-review

Abstract

Consider a two-person zero-sum search game between a Hider and a Searcher. The Hider chooses to hide in one of n discrete locations (or “boxes”) and the Searcher chooses a search sequence specifying which order to look in these boxes until finding the Hider. A search at box i takes ti time units and finds the Hider—if hidden there—independently with probability qi, for i=1,…,n. The Searcher wants to minimize the expected total time needed to find the Hider, while the Hider wants to maximize it. It is shown in the literature that the Searcher has an optimal search strategy that mixes up to n distinct search sequences with appropriate probabilities. This paper investigates the existence of optimal pure strategies for the Searcher—a single deterministic search sequence that achieves the optimal expected total search time regardless of where the Hider hides. We identify several cases in which the Searcher has an optimal pure strategy, and several cases in which such optimal pure strategy does not exist. An optimal pure search strategy has significant practical value because the Searcher does not need to randomize their actions and will avoid second guessing themselves if the chosen search sequence from an optimal mixed strategy does not turn out well.

Original languageEnglish (US)
Pages (from-to)767-775
Number of pages9
JournalEuropean Journal of Operational Research
Volume313
Issue number2
DOIs
StatePublished - Mar 1 2024

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Gittins index
  • Search games
  • Semi-finite games
  • Zero-sum games

Fingerprint

Dive into the research topics of 'Optimal pure strategies for a discrete search game'. Together they form a unique fingerprint.

Cite this