Article ID: | iaor20052562 |
Country: | United States |
Volume: | 51 |
Issue: | 7 |
Start Page Number: | 977 |
End Page Number: | 993 |
Publication Date: | Oct 2004 |
Journal: | Naval Research Logistics |
Authors: | Kikuta Kensaku |
Keywords: | game theory, graphs |
There is a finite cyclic graph. The hider chooses one of all node except the specified one, and he hides an (immobile) object there. At the beginning the seeker is at the specified node. After the seeker chooses an ordering of the nodes except the specified one, he examines each node in that order until he finds the object, traveling along edges. It costs an amount when he moves from one node to an adjacent one and also when he checks a node. While the hider wishes to maximize the sum of the traveling costs and the examination costs which are required to find the object, the seeker wishes to minimize it. The problem is modeled as a two-person zero-sum game. We solve the game when unit costs (traveling cost + examination cost) have geometrical relations depending on nodes. Then we give properties of optimal strategies of both players.