Searching for Multiple Hidden Objects

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

• Thomas Lidbetter (LSE)
• Monday 11 June 2012, 15:00-16:00
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

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.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge talks
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Economics and Computer Science Talks
• Hanchen DaDaDash
• Interested Talks
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• Optimization and Incentives Seminar
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.