禁漫天堂

Dr Thomas Lidbetter

This course is available on the MSc in Applicable Mathematics and MSc in Management Science (Operational Research). This course is available with permission as an outside option to students on other programmes where regulations permit.

In 禁漫天堂 Theory, a mobile 禁漫天堂er 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 禁漫天堂 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 禁漫天堂 Theory, a unit-speed 禁漫天堂er 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 禁漫天堂 Games (zero-sum games where a T-minimising 禁漫天堂er 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 禁漫天堂 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 禁漫天堂er starts in a location known to the Hider; then we remove this restriction. We then study 禁漫天堂 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 禁漫天堂er has to find several hidden objects.

The second part of the course studies the Rendezvous 禁漫天堂 Problem. We begin with the player-asymmetric form of the problem, where the two 禁漫天堂ers may meet before the game to decide what strategy each will adopt. We then consider the player-symmetric form, where the 禁漫天堂ers are constrained to follow a common mixed strategy. Finally, we consider the incomplete information problem where a 禁漫天堂er seeks an agent who might be a Hider (T-maximiser) or another 禁漫天堂er (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 禁漫天堂 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, 禁漫天堂 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, 禁漫天堂 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.