The Library
Hide-and-seek games on a network, using combinatorial search paths
Tools
Tools
Tools
Alpern, Steve (2017) Hide-and-seek games on a network, using combinatorial search paths. Operations Research, 65 (5). pp. 1207-1214. doi:10.1287/opre.2017.1594 ISSN 0030-364X.
|
PDF
WRAP-hide-seek-games-combinatorial-paths-Alpern-2017.pdf - Accepted Version - Requires a PDF viewer. Download (485Kb) | Preview |
Official URL: https://doi.org/10.1287/opre.2017.1594
Abstract
This paper introduces a new search paradigm to hide-and-seek games on networks. The Hider locates at any point on any arc. The Searcher adopts a “combinatorial” path when searching the network: a sequence of arcs, each adjacent to the last, and traced out at unit speed. In previous literature the Searcher was allowed “simple motion,” any unit speed path, including ones that turn around inside an arc. The new approach more closely models real problems such as search for improvised explosive devices using vehicles that can only turn around at particular locations on a road. The search game is zero sum, with the time taken to find the Hider as the payoff.
Using a lemma giving an upper bound for the expected search time on a semi Eulerian network, we solve the search game on a network Q3 consisting of two nodes connected by three arcs of arbitrary lengths. When two Q3 networks with unit length arcs are linked by two small central arcs incident at the start node, one of these arcs must be traversed at least three times in an optimal search. This property holds for both combinatorial paths and simple motion paths, and the latter makes it a counterexample to a conjecture of Gal, which said that two traversals were always sufficient.
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||
| Divisions: | Faculty of Social Sciences > Warwick Business School | ||||||
| Library of Congress Subject Headings (LCSH): | Game theory, Two-person zero-sum games | ||||||
| Journal or Publication Title: | Operations Research | ||||||
| Publisher: | Institute for Operations Research and the Management Sciences (I N F O R M S) | ||||||
| ISSN: | 0030-364X | ||||||
| Official Date: | 19 April 2017 | ||||||
| Dates: |
|
||||||
| Volume: | 65 | ||||||
| Number: | 5 | ||||||
| Page Range: | pp. 1207-1214 | ||||||
| DOI: | 10.1287/opre.2017.1594 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Date of first compliant deposit: | 20 December 2016 | ||||||
| Date of first compliant Open Access: | 28 April 2018 | ||||||
| Funder: | United States. Air Force. Office of Scientific Research (AFOSR) | ||||||
| Grant number: | Grant FA9550-14-1-0049 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
