Article ID: | iaor2000399 |
Country: | Japan |
Volume: | 41 |
Issue: | 4 |
Start Page Number: | 629 |
End Page Number: | 642 |
Publication Date: | Dec 1998 |
Journal: | Journal of the Operations Research Society of Japan |
Authors: | Iida Koji, Hohzaki Ryusuke |
Keywords: | search, programming: convex, programming: nonlinear |
This paper investigates a search game of a searcher and a target. At the beginning of the search, the target selects his path from some options and the searcher determines the distribution of his available search resources into a search space which consists of discrete cells and discrete time points. The searcher gains a value on detection of the target while he expends the search cost depending on the allocation of the search resource. The payoff of the search is the expected reward which is defined as the expected value minus the expected search cost. The searcher wants to maximize the expected reward and the target wants to minimize it. We formulate the problem as a two-person zero-sum game and reduce it to a concave maximization problem. We propose a computational method to obtain an optimal solution of the game. Our method proceeds in such a way that one-sided problems generated from the original game are repeatedly solved and their solutions converge asymptotically to an optimal solution of the game. By some examples, we examine the effect of parameters included in the problem upon an optimal solution to elucidate some characteristics of the solution and the computational time of the proposed method.