Mathematical Sciences Seminar - Search games with submodular payoff functions
When:
—
Venue:
Birkbeck Main Building, Malet Street
No booking required
Suppose an object is hidden in a finite set X and a Searcher looks at the elements of the set one by one until he finds the object. The cost paid by the Searcher is given by some increasing, submodular set function, f: if the object is hidden at some element x, the cost paid by the Searcher is f(A), where A is the set of all elements searched so far. If the object is hidden in X according to some known probability distribution, the problem of finding an ordering of the elements to minimise the expected cost to the Searcher in finding the object is NP-hard. We give a 2-approximation to the optimal search strategy, and show that this generalises a well known result in scheduling theory. We go on to consider a zero-sum game where a malevolent Hider chooses an element of X, the Searcher chooses an ordering of X and the payoff is the cost to the Searcher in finding the object. We show that the optimal mixed (randomised) strategy of the Hider lies in a well-known object called the base polyhedron of f.
Contact name:
Department of Economics, Mathematics and Statistics