Competitive search in a network

Spyros Angelopoulos and Thomas Lidbetter

European Journal of Operational Research, 2020, vol. 286, issue 2, 781-790

Abstract: We study the classic problem in which a Searcher must locate a hidden point, also called the Hider in a network, starting from a root point. The network may be either bounded or unbounded, thus generalizing well-known settings such as linear and star search. We distinguish between pathwise search, in which the Searcher follows a continuous unit-speed path until the Hider is reached, and expanding search, in which, at any point in time, the Searcher may restart from any previously reached point. The former has been the usual paradigm for studying search games, whereas the latter is a more recent paradigm that can model real-life settings such as hunting for a fugitive, demining a field, or search-and-rescue operations. We seek both deterministic and randomized search strategies that minimize the competitive ratio, namely the worst-case ratio of the Hider’s discovery time, divided by the length of the shortest path to it from the root. Concerning expanding search, we show that a simple search strategy that applies a “waterfilling” principle has optimal deterministic competitive ratio; in contrast, we show that the optimal randomized competitive ratio is attained by fairly complex strategies even in a very simple network of three arcs. Motivated by this observation, we present and analyze an expanding search strategy that is a 54-approximation of the randomized competitive ratio. Our approach is also applicable to pathwise search, for which we give a strategy that is a 5-approximation of the randomized competitive ratio, and which improves upon strategies derived from previous work.

Keywords: Game theory; Search games; Competitive analysis; Networks (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720303210
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:286:y:2020:i:2:p:781-790

DOI: 10.1016/j.ejor.2020.04.003

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().