Dr Thomas Lidbetter

This course is available on the MSc in Applicable Mathematics. This course is available with permission as an outside option to students on other programmes where regulations permit.

In Search Theory, a mobile Searcher tries to minimise the time T taken to find something, which we call the Hider, in a known search space Q. The Hider may be stationary or mobile. In the zero sum game context (first half of the course), the Hider does not want to be found, or at least wants to maximise T. In the second half of the course we consider the Rendezvous Search Problem, in which the Hider also wants to minimise T. In both contexts the search space Q will often be taken as a finite network.

In Search Theory, a unit-speed Searcher wishes to minimise the time T required to find (meet) a lost object or agent hidden in a known search region Q. This course concentrates on cases where the lost object is an agent who has motives of his own. The course content will be based on both Search Games (zero-sum games where a T-minimising Searcher seeks a T-maximising Hider) and Rendezvous Games (common-interest games where two lost searchers want to minimise T).

The first part of the course will consider Search Games. We begin with the case where the Hider is immobile - he picks his position in Q at the start of the game. We solve this game for the case where Q is a tree or a 'weakly Eulerian' network, assuming the Searcher starts in a location known to the Hider; then we remove this restriction. We then study Search Games where the Hider is mobile, the so-called 'Princess and Monster' games of R. Isaacs. Several special games are then studied, for example the case of an unknown search region (maze), and games in which the Searcher has to find several hidden objects.

The second part of the course studies the Rendezvous Search Problem. We begin with the player-asymmetric form of the problem, where the two Searchers may meet before the game to decide what strategy each will adopt. We then consider the player-symmetric form, where the Searchers are constrained to follow a common mixed strategy. Finally, we consider the incomplete information problem where a Searcher seeks an agent who might be a Hider (T-maximiser) or another Searcher (T-minimiser).

22 hours of lectures and 10 hours of seminars in the LT.

An assignment is set each week and marked by the lecturer with feedback. Problem areas will be discussed in class.

S. Alpern, S. Gal, The Theory of Search Games and Rendezvous, Springer, 2003; S. Alpern, A new approach to Gal's theory of search games for immobile hiders on network, Dynamic Games and Applications 1 (2), 209-219, 2011; S. Ross, An Introduction to Stochastic Dynamic Programming. Academic Press, New York, 1983; S. Alpern, Rendezvous search: a personal perspective. Operations Research 50, no. 5, 2003; A. Y. Garnaev, Search Games and Other Applications of Game Theory, Springer-Verlag, 2000; S. Alpern, J. V. Howard, Alternating search at two locations. Dynamics & Control 10, 319-339, 2000; T. Lidbetter, Search games with multiple hidden objects, SIAM Journal on Control and Optimization 51(4), 3056-3074, (2013).

Exam (100%, duration: 2 hours) in the main exam period.