A Classical Search Game in Discrete Locations

DOI10.1287/MOOR.2022.1279MaRDI QIDQ6199267zbMATH OpenOpenAlexFDO

Authors Jake Clarkson, Kyle Y. Lin, Kevin D. Glazebrook

Publication date 23 February 2024

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.09310, https://eprints.lancs.ac.uk/id/eprint/170191/1/SearchGame_resub_2_to_KG.pdf

zbMATH Keywords

Gittins indexsearch and surveillancesearch gamessemifinite games

Mathematics Subject Classification ID

2-person games (91A05) Noncooperative games (91A10)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 18884
• More on the search for an infiltrator
• scientific article; zbMATH DE number 1023202
• Manhunting -- a simple search game
• Publication:3204351

Cited in

(7)

• A competitive search game with a moving target
• Optimal pure strategies for a discrete search game
• Hide-and-seek game with capacitated locations and imperfect detection
• Overcoming probabilistic faults in disoriented linear search
• Inspection game with imperfect detection technology
• Traveling between dispersed locations to search for a hidden object
• Searching for a mobile hider in a directed bipartite graph

This page was built for publication: A Classical Search Game in Discrete Locations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199267)