Searching for multiple objects in multiple locations

Thomas Lidbetter, Kyle Y. Lin

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

Many practical search problems concern the search for multiple hidden objects or agents, such as earthquake survivors. In such problems, knowing only the list of possible locations, the Searcher needs to find all the hidden objects by visiting these locations one by one. To study this problem, we formulate new game-theoretic models of discrete search between a Hider and a Searcher. The Hider hides k balls in n boxes, and the Searcher opens the boxes one by one with the aim of finding all the balls. Every time the Searcher opens a box she must pay its search cost, and she either finds one of the balls it contains or learns that it is empty. If the Hider is an adversary, an appropriate payoff function may be the expected total search cost paid to find all the balls, while if the Hider is Nature, a more appropriate payoff function may be the difference between the total amount paid and the amount the Searcher would have to pay if she knew the locations of the balls a priori (the regret). We give a full solution to the regret version of this game, and a partial solution to the search cost version. We also consider variations on these games for which the Hider can hide at most one ball in each box. The search cost version of this game has already been solved in previous work, and we give a partial solution in the regret version.

Original languageEnglish (US)
Pages (from-to)709-720
Number of pages12
JournalEuropean Journal of Operational Research
Volume278
Issue number2
DOIs
StatePublished - Oct 16 2019

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Discrete optimization
  • Game theory
  • Search games

Fingerprint Dive into the research topics of 'Searching for multiple objects in multiple locations'. Together they form a unique fingerprint.

  • Cite this