Browser does not support script.

How to contact us

Department of Mathematics

Columbia House

London School of Economics

Houghton Street

London WC2A 2AE, UK

**Email:** maths.info@lse.ac.uk

**Tel:** +44(0)207 955 7732/7925

**Connect with LSE Maths:**

Click here for information on how to get to LSE using public transport and maps of the campus

Below you'll find the program for the Lunchtime Seminar. The Seminar normally takes place on Fridays from 12.05 pm - 12.35 pm in room **32L.B.09** (32 Lincoln's Inn Fields, LSE).

Questions, suggestions, etc., about the seminar can be forwarded to the seminar administrator (Room COL 3.14), by sending an e-mail to: seminar@maths.lse.ac.uk

**Friday 27 November - Tom Lidbetter (LSE)
***Seminar will last one hour, from 12 noon***
Search games with submodular payoff functions**

Suppose an element of a finite set X is chosen and a Searcher inspects the elements of the set one by one until he finds the chosen element. For a given ordering x_1,...,x_n of X, the cost paid by the Searcher to find element x_i is f({x_1,...,x_i}), where f is a non-decreasing, submodular set function. We consider the problem faced by the Searcher of choosing an ordering of X to minimise the expected cost of finding an element of X chosen according to some known probability distribution. We give some examples of this problem, including the well-known problem in scheduling theory of minimising the sum of the weighted completion times of a set of jobs with precedence constraints. The latter problem is NP-hard (and therefore so is ours), and we give a 2-approximation to the optimal search strategy, generalising the analogous result for scheduling. The approximation makes use of what may be thought of as a version of "Smith's rule" for optimal scheduling. We go on to consider a zero-sum game where a cost-maximising 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 any optimal mixed (randomised) strategy of the Hider must lie in a well-known object called the base polyhedron of f.

This is joint work with Robbert Fokkink.

**Friday 4 December
** Speaker, title and abstract TBC

**Friday 11 December
** Speaker, title and abstract TBC

**Previous seminars in this series:** **2015****,** **2014****,** **2013****,** **2012****,** **2011****,** **2010****,** **2009****,** **2008****,** **2007****,** **2006**

Browser does not support script.

Browser does not support script.