A SEARCH GAME WITH UNKNOWN EXAMINATION COSTS AND TRAVEL TIMES

作者：Kikuta Kensaku^*

来源：Asia Pacific Journal of Operational Research, 2014, 31(3): 1450013.

DOI：10.1142/S0217595914500134

• Search problem
• two-person zero-sum game
• expected cost
• examination cost
• traveling cost

A search game on a finite and complete graph is studied between a (immobile) hider and a seeker. A strategy for the hider is to choose a node where he hides, except for a specified node. A strategy for the seeker is an ordering of nodes in which the seeker starts at the specified node, examines each node in that order until he finds the hider, traveling along edges. Associated with an examination of a node is the examination cost, and associated with a movement from a node to a node is a traveling cost. These costs are unknown for both players when they choose strategies. They know only probability laws of them. While the hider wishes to maximize the expectation of the sum of these costs which are required to find the hider, the seeker wishes to minimize it. The game is solved when the nodes are classified into two groups depending on the examination costs, and the edges are classified into three groups depending on both costs.

• 出版日期2014-6