## 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 t_{i} time units and finds the Hider—if hidden there—independently with probability q_{i}, 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 language | English (US) |
---|---|

Pages (from-to) | 767-775 |

Number of pages | 9 |

Journal | European Journal of Operational Research |

Volume | 313 |

Issue number | 2 |

DOIs | |

State | Published - 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