EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2588. Optimal Pure Strategies for a Discrete Search Game

Invited abstract in session TC-36: Game Theory, Solutions and Structures VII, stream Game Theory, Solutions and Structures.

Tuesday, 12:30-14:00
Room: 32 (building: 306)

Authors (first author is the speaker)

1. Thomas Lidbetter
Rutgers Business School, Rutgers University

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 work 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. This is joint work with Thuy Bui and Kyle Lin.

Keywords

Status: accepted

Back to the list of papers