### 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 a
_{i}
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.

Original language | English (US) |
---|---|

Pages (from-to) | 259-279 |

Number of pages | 21 |

Journal | Annals of Operations Research |

Volume | 275 |

Issue number | 2 |

DOIs | |

State | Published - Apr 15 2019 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Decision Sciences(all)
- Management Science and Operations Research

### Keywords

- Defense and security
- Networks
- Search games
- Zero-sum games

### Cite this

*Annals of Operations Research*,

*275*(2), 259-279. https://doi.org/10.1007/s10479-018-2966-0

}

*Annals of Operations Research*, vol. 275, no. 2, pp. 259-279. https://doi.org/10.1007/s10479-018-2966-0

**Approximate solutions for expanding search games on general networks.** / Alpern, Steve; Lidbetter, Thomas.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Approximate solutions for expanding search games on general networks

AU - Alpern, Steve

AU - Lidbetter, Thomas

PY - 2019/4/15

Y1 - 2019/4/15

N2 - 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 a i 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.

AB - 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 a i 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.

KW - Defense and security

KW - Networks

KW - Search games

KW - Zero-sum games

UR - http://www.scopus.com/inward/record.url?scp=85050318365&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85050318365&partnerID=8YFLogxK

U2 - 10.1007/s10479-018-2966-0

DO - 10.1007/s10479-018-2966-0

M3 - Article

AN - SCOPUS:85050318365

VL - 275

SP - 259

EP - 279

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - 2

ER -