Search games with multiple hidden objects

Thomas Lidbetter

LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library

Abstract: We consider a class of zero-sum search games in which a Searcher seeks to minimize the expected time to find several objects hidden by a Hider. We begin by analyzing a game in which the Searcher wishes to find $k$ balls hidden among $n>k$ boxes. There is a known cost of searching each box, and the Searcher seeks to minimize the total expected cost of finding all the objects in the worst case. We show that it is optimal for the Searcher to begin by searching a $k$-subset $H$ of boxes with probability $\nu(H)$, which is proportional to the product of the search costs of the boxes in $H$. The Searcher should then search the $n-k$ remaining boxes in a random order. A worst-case Hider distribution is the distribution $\nu$. We distinguish between the case of a smart Searcher who can change his search plan as he goes along and a normal Searcher who has to set out his plan from the beginning. We show that a smart Searcher has no advantage. We then show how the game can be formulated in terms of a more general network search game, and we give upper and lower bounds for the value of the game on an arbitrary network. For $2$-arc connected networks (networks that cannot be disconnected by the removal of fewer than two arcs), we solve the game for a smart Searcher and give an upper bound on the value for a normal Searcher. This bound is tight if the network is a circle.

Keywords: search game; network; discrete optimization (search for similar items in EconPapers)
JEL-codes: J50 (search for similar items in EconPapers)
Date: 2013-08
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Published in SIAM Journal on Control and Optimization, August, 2013, 51(4), pp. 3056-3074. ISSN: 0363-0129

Downloads: (external link)
http://eprints.lse.ac.uk/55103/ Open access version. (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ehl:lserod:55103

Access Statistics for this paper

More papers in LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library LSE Library Portugal Street London, WC2A 2HD, U.K.. Contact information at EDIRC.
Bibliographic data for series maintained by LSERO Manager ().