A search game on a cyclic graph

A search game on a cyclic graph

0.00 Avg rating0 Votes
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:
Keywords: game theory, graphs
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.