This course is available on the MSc in Applicable Mathematics and MSc in Management Science (Decision Sciences). 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 minimize 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 maximize T. In the second half of the course we consider the Rendezvous Search Problem, in which the Hider also wants to minimize 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 minimize 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-minimizing Searcher seeks a T-maximizing Hider) and Rendezvous Games (common-interest games where two lost searchers want to mimimize 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 where the Searcher makes guesses and is given directional information about the Hider's location ('high-low search'), and the case of an unknown search region (maze).

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-maximizer) or another Searcher (T-minimizer).

20 hours of lectures and 10 hours of seminars in the LT. 2 hours of lectures in the ST.

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

S. Alpern, S. Gal, The Theory of Search Games and Rendezvous, Springer, 2003; S. Gal, Search Games, Academic Press, 1980; 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.

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