Search Games Mock Exam
Search Games
Mock Exam Solutions|
Lecturer: |
Steve Alpern |
|
Room: |
B407 (fourth floor, Columbia House) |
|
Email: |
|
|
Office hours: |
Please see the office hours page |
This is a half-unit course, with lectures in the Lent Term. Classes
will start in Week 2 of the Lent Term.
There will also be revision lectures in the Summer Term. Full timetabling
details can be found on the Timetables webpage:
http://www.lse.ac.uk/admin/timetables/confirmed/module_sessional/ma/35.htm
Homeworks will be set weekly, and you will be given more information about when these will be set and when they should be submitted in the lectures. No late work will be accepted. If you don't finish the assignment, hand in whatever you have. Label all work with your name and the course number (MA419). Corrected work will be handed back and discussed in the classes. Solutions for some of the homework exercises will be given out as well. This means that not all exercises need to be discussed in class.
The course is based on the following monograph:
S. Alpern, S. Gal, The Theory of Search Games and Rendezvous, Springer, 2003.
An e-book form can be obtained inexpensively from the web. The following will also be useful.
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.
During the lectures, the theory will be developed and
explained, proofs given, and many examples demonstrated.
In the Summer Term there will be additional lectures, mainly for revision
purposes.
In this course, as in other courses in Mathematics, it is very important that all homework questions are attempted and handed in for grading. It is vital to get practice in the various techniques covered in the course. It is also important to hand in homework, so that feedback on it can be given. Corrected work will be handed back and discussed in the class.
The office hours are meant for any questions and problems
with the course material that have not or cannot be covered in the normal
lectures and classes. You are strongly recommended to make use of them.
The times of the office hours for all lecturers and class teachers can be found
on the departmental
office hours page.
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.
To give a flavour of the course, consider the following problem posed by Alpern in 1976: Two agents wish to meet at one of n locations. In each period t=0,1,2,., they can go to some location and the meeting time T is the first time t they go to the same location. A pure strategy for an agent is simply a list of locations. What randomized strategy, if followed by both players, minimizes the expected value of T? For n=2 the best strategy is to always stay where you are or move to the other location equiprobably. This is easy. It was just proved last year by R. Weber that for n=3 the best strategy is to do the following in each two move time period i=1,2, i=3,4, ., i=2k+1,2k+2: with probability 1/3, stay where you are for the next two moves, with probability 2/3 go to the remaining two locations in a random order. For n>3, the problem is still open.
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).
Search Games Mock Exam
Search Games
Mock Exam Solutions
Last changed: 12th January 2010
Send
comments to webmaster