Search games on a network with travelling and search costs

The authors analyse two‐person zero‐sum search games in which play takes place on a network and in discrete time. The hider first chooses a node and remains there for the duration of the game. The searcher then chooses a node and searches there. At each subsequent time instant the searcher moves from the node he occupies to an adjacent node and decides whether or not to search it. Play terminates when the searcher is at the node chosen by the hider and searches there. The searcher incurs costs in moving from one node to another and also when a node is searched. The searcher wants to minimize the costs of finding the hider and the hider wants to maximize them. The paper has two main strands. The first investigates these games on directed, not necessarily strongly connected, networks; previous work has tended to concentrate on undirected networks. The second complements previous work on undirected networks by obtaining results for the case when the search cost is the same for all nodes.