An Evasion Game on a Finite Tree
V. J. Baston, F. A. Bostock · SIAM Journal on Control and Optimization · 1990
The paper considers the following two-person zero-sum multistage game. An evader starts at a given vertex of a tree and, at discrete intervals of time, chooses either to move to one of the vertices adjacent to him or stay where, he is. A gunner with a single bullet may, at each of the same discrete intervals of time, either fire the bullet at any of the vertices of the tree or hold his fire. The gunner always hits the vertex at which he aims and the bullet takes one unit of time to reach its target. The payoff to the gunner is 1 if he hits the evader, $\mu $ (where $| \mu | < 1$) if he fires and misses, and 0 if he never fires. It is shown that, whatever vertex the evader starts at, the value of the game is ${{(1 + \mu )} / 2}$.