The Library
Hide-and-seek games on a tree to which Eulerian networks are attached
Tools
Alpern, Steve (2008) Hide-and-seek games on a tree to which Eulerian networks are attached. Networks, Vol.52 (No.3). pp. 162-166. doi:10.1002/net.20235 ISSN 0028-3045.
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.1002/net.20235
Abstract
We analyze the hide-and-seek game Γ(G) on certain networks G. The hider picks a hiding point yin Gand the searcher picks a unit speed path S(t) in G, starting at any point S(0). The payoff in this zero-sum game is the capture time T = T(S,y) = min{t: S(t) = y}. Such games have been studied before, but mainly with the simplifying assumption that the searcher's starting point S(0) is specified and known to the hider. We call a network partly Eulerian if it consists of a tree (of length aand radius r) to which a finite number of disjoint Eulerian networks (of total length b) are attached, each at a single point. We show that for such networks, a strategy consisting equiprobably of a minimal (Chinese Postman) covering path and its reverse path is optimal for the searcher, while the optimal hider strategy is to assume that the searcher must start at the center of the tree, and to optimize in that (known) game. The value of the game Γ(G) is a+b/2 -r. This simplifies and extends a similar result of Dagan and Gal for search games on trees. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008
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: | Networks | ||||
Publisher: | John Wiley & Sons Inc. | ||||
ISSN: | 0028-3045 | ||||
Official Date: | 2008 | ||||
Dates: |
|
||||
Volume: | Vol.52 | ||||
Number: | No.3 | ||||
Page Range: | pp. 162-166 | ||||
DOI: | 10.1002/net.20235 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |