Search games on trees with asymmetric travel times
Alpern, Steve. (2010) Search games on trees with asymmetric travel times. SIAM Journal on Control and Optimization, Vol.48 (No.8). pp. 5547-5563. ISSN 0363-0129Full text not available from this repository.
Official URL: http://dx.doi.org/10.1137/090781115
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|
|Page Range:||pp. 5547-5563|
Actions (login required)