The Library
Search games on trees with asymmetric travel times
Tools
Alpern, Steve (2010) Search games on trees with asymmetric travel times. SIAM Journal on Control and Optimization, Vol.48 (No.8). pp. 5547-5563. doi:10.1137/090781115 ISSN 0363-0129.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1137/090781115
Abstract
A point H is hidden in a rooted tree Q which is endowed with asymmetric distances (travel times) between nodes. We determine the randomized search strategy, starting from the root, which minimizes the expected time to reach H, in the worst case. This is equivalent to a zero-sum search game $\Gamma\left(Q\right)$, with minimizing Searcher, maximizing Hider, and payoff equal to the capture time. The worst Hiding distribution (over the leaves) from the Searcher's viewpoint is one where at every node i the probability of each branch is proportional to the minimum time required to tour it from i. The optimal randomized search is a mixture over depth-first searches. We also consider briefly some other networks and the possibility of a mobile Hider. Our formulation with asymmetric travel times generalizes that of Gal [SIAM J. Control Optim., 17 (1979), pp. 99–122] for symmetric travel times and also the search games of Kikuta [J. Oper. Res., 38 (1995), pp. 70–88] and Kikuta and Ruckle [Naval Res. Logist., 41 (1994), pp. 821–831], who posited search costs $c_i$ at each node i which were added to the travel time to obtain the payoff. We also briefly consider what happens if we allow the Searcher (Hider) to start (hide) at any leaf node. We determine when properties found by Dagan and Gal [Networks, 52 (2008), pp. 156–161] for the symmetric version of such games hold in our asymmetric context.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||
Journal or Publication Title: | SIAM Journal on Control and Optimization | ||||
Publisher: | Society for Industrial and Applied Mathematics | ||||
ISSN: | 0363-0129 | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Volume: | Vol.48 | ||||
Number: | No.8 | ||||
Page Range: | pp. 5547-5563 | ||||
DOI: | 10.1137/090781115 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |