Search–hide games on trees

Search–hide games on trees

0.00 Avg rating0 Votes
Article ID: iaor19981176
Country: Netherlands
Volume: 80
Issue: 1
Start Page Number: 175
End Page Number: 183
Publication Date: Jan 1995
Journal: European Journal of Operational Research
Authors:
Abstract:

In this paper we consider search–hide games on trees. There are two players. Player H (the hider or inspectee) selects one of m vertices of the tree for hiding ‘undeclared objects’ permanently. Player I (the inspector) is allowed to search some vertices of the tree trying to find the hidden objects. However, player I can only examine exactly k(<m) vertices lying on a subtree with k vertices because of certain limitations. Player I wants to maximize the probability of detecting the undeclared objects and player H to minimize it. This problem can be described by a fractional covering problem (FC) and its dual (DFC). An algorithm based on the revised simplex method with implicit column generation is proposed for solving FC and DFC. The set of all possible strategies of the player I (all possible subtree with k vertices) is not necessarily listed explicitly. In order to find a profitable column, a polynomial algorithm is developed by utilizing the structure of the underlying tree.

Reviews

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