University of Cambridge > Talks.cam > Optimization and Incentives Seminar > Searching for Multiple Hidden Objects

Searching for Multiple Hidden Objects

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Felix Fischer.

Suppose k objects are hidden amongst n>k boxes, each with a designated search cost. A Searcher pays to open the boxes one by one until all the objects have been found. We consider this as a zero-sum game between the Searcher who wishes to minimise the total search cost and a malevolent Hider. We show that it is optimal for the objects to be hidden in a subset A of k boxes with probability proportional to the product p(A) of the search costs of those boxes. It is optimal for the Searcher to begin by opening a subset A of k boxes with probability p(A), and then search the remaining boxes in a random order. We show how this game can be considered as specific example of a wider class of search games for multiple objects on a network, and we give the solution of the game for 2-arc-connected networks (networks that cannot be disconnected by removing fewer than 2 arcs).

This talk is part of the Optimization and Incentives Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2020 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity