A search game when a search path is given

In this paper, we investigate a search game in discrete time and space. A searcher is given a search path in advance and his look on the path is determined by a randomized look strategy. A target selects a path from some options. The searcher gains a value on the detection of the target but expends search cost by the look. A pay-off function of the game for the searcher is the expected reward which is defined as the expected value minus the expected search cost. First, we show a recursive relation for the conditional optimal look strategy of the searcher given a target path. We prove its NP-completeness, though it looks simple, and clarify some characteristics of the solution. Then our original continuous game is converted to a matrix game. From these facts, we consider a relationship between the game and the one-sided optimizing problem and examine some examples.