Ambush Strategies in Search Games on Graphs
Steve Alpern, Miroslav D. Ašić · SIAM Journal on Control and Optimization · 1986
A blind searcher and a blind hider move at below unit speed along a finite length graph Q known to both, until the first time T when they meet. A two person zero-sum game arises if the searcher pays the hider T units. We consider circumstances under which it may be optimal for the searcher to “lie in wait” at a node of Q, hoping the hider will come to him. We also explicitly define a notion of “equilibrium in distribution” for such games, which has been implicit in the literature. We show that for the graph consisting of two nodes connected by three arcs of equal length there are optimal ambush strategies but there is no equilibrium in distribution.