BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Optimization and Incentives Seminar
SUMMARY:Searching for Multiple Hidden Objects - Thomas Lid
better (LSE)
DTSTART;TZID=Europe/London:20120611T150000
DTEND;TZID=Europe/London:20120611T160000
UID:TALK38231AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/38231
DESCRIPTION:Suppose k objects are hidden amongst n>k boxes\, e
ach with a designated search cost. A Searcher pay
s to open the boxes one by one until all the objec
ts have been found. We consider this as a zero-su
m 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 hid
den in a subset A of k boxes with probability prop
ortional to the product p(A) of the search costs o
f those boxes. It is optimal for the Searcher to
begin by opening a subset A of k boxes with probab
ility p(A)\, and then search the remaining boxes i
n a random order. We show how this game can be co
nsidered as specific example of a wider class of s
earch games for multiple objects on a network\, an
d we give the solution of the game for 2-arc-conne
cted networks (networks that cannot be disconnecte
d by removing fewer than 2 arcs).
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:Felix Fischer
END:VEVENT
END:VCALENDAR