Premium
Network search games, with arbitrary searcher starting point
Author(s) -
Dagan Ar,
Gal Shmuel
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20241
Subject(s) - stochastic game , zero sum game , point (geometry) , simple (philosophy) , mathematics , computer science , mathematical optimization , game theory , mathematical economics , philosophy , geometry , epistemology
We analyze a zero‐sum game between a blind unit‐speed searcher and a stationary hider on a given network Q , where the payoff is the time for the searcher to reach the hider. In contrast to the standard game studied in the literature, we do not assume that the searcher has to start from a fixed point (known to the hider) but can choose his starting point. We show that for some networks, including trees, the optimal searcher, and hider strategies have a simple structure. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008