The Library
Approximate solutions for expanding search games on general networks
Tools
Tools
Tools
Alpern, Steve and Lidbetter, Thomas (2019) Approximate solutions for expanding search games on general networks. Annals of Operations Research , 275 (2). pp. 259-279. doi:10.1007/s10479-018-2966-0
|
PDF
WRAP-approximate-solutions-expanding-games-Alpern-2018.pdf - Accepted Version - Requires a PDF viewer. Download (869Kb) | Preview |
Official URL: https://doi.org/10.1007/s10479-018-2966-0
Abstract
We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point H on a network Q moving from a known starting point. Rather than adopting the traditional continuous unit speed path paradigm, we use the dynamic “expanding search” paradigm recently introduced by the authors. Here the regions S(t) that have been searched by time t are increasing from the starting point and have total length t. Roughly speaking the search follows a sequence of arcs ai such that each one starts at some point of an earlier one. This type of search is often carried out by real life search teams in the hunt for missing persons, escaped convicts, terrorists or lost airplanes. The paper which introduced this type of search solved the adversarial problem (where H is hidden to maximize the time to be found) for the cases where Q is a tree or is 2-arc-connected. This paper’s main contribution is to give two strategy classes which can be used on any network and have expected search times which are within a factor close to 1 of the value of the game (minimax search time). These strategies classes are respectively optimal for trees and 2-arc-connected networks. We also solve the game for circle-and-spike networks, which can be considered as the simplest class of networks for which a solution was previously unknown.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||
| Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||||||
| Library of Congress Subject Headings (LCSH): | Two-person zero-sum games, National security | ||||||||
| Journal or Publication Title: | Annals of Operations Research | ||||||||
| Publisher: | Springer New York LLC | ||||||||
| ISSN: | 0254-5330 | ||||||||
| Official Date: | April 2019 | ||||||||
| Dates: |
|
||||||||
| Volume: | 275 | ||||||||
| Number: | 2 | ||||||||
| Page Range: | pp. 259-279 | ||||||||
| DOI: | 10.1007/s10479-018-2966-0 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Publisher Statement: | This is a post-peer-review, pre-copyedit version of an article published in Annals of Operations Research. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10479-018-2966-0 | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| RIOXX Funder/Project Grant: |
|
||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
