How to contact us


LSE 10 logo master_6

Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE




Follow us online



The search value of a set

Tuesday 27th May 2014, 3.00pm

32LIF LG.03, LSE

Robbert Fokkink

TU Delft

Personal profile


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).