Tuesday 27th May 2014, 3.00pm
32LIF LG.03, LSE
Robbert Fokkink
TU Delft
Personal profile
Abstract:
In 1985, Alpern and Asic defined the search value of a network as the expected time of finding a hider in a search game, when time is scaled such that an exhaustive search takes unit time. The search value of a network is always in between ½ and 1. It has not been computed for many networks yet. I will try to explain why this is so. Extending the Alpern-Asic concept, one can define the search value of a set. This is remotely related to the Shapley value of a cooperative game. Again, the search value of a set is in between ½ and 1. Again, it is hard to compute. I will give you one such set, in which searching comes at a supermarket discount of 5 for the price of 3, and leave the computation of its value as a challenge.
This is joint work with Ken Kikuta (Kobe) and David Ramsey (Wroclaw).