Centre for Discrete and Applicable Mathematics

CDAM Research Report, LSE-CDAM-2007-05

February 2007

Rendezvous Search with Revealed Information: Applications to the Line

Steve Alpern

The symmetric rendezvous problem on a network Q asks how two players, forced to use the same mixed strategy, can minimize their expected meeting time, starting from a known initial distribution on the nodes of Q. This minimum is called the (symmetric) `rendezvous value' of Q. Traditionally, the players are assumed to receive no information during the play of the game. We consider the effect on rendezvous times of giving the players some information about past actions and chance moves, enabling them to apply Bayesian updates to improve their knowledge of their partner's whereabouts. We consider the case where they are placed a known distance apart on the line graph Q (`symmetric rendezvous on the line'). These techniques can be used to give lower bounds on the rendezvous times of the original game (without any revealed information). Our approach is to concentrate on a general analysis of the effect of revelations, rather than compute the best bounds possible with our techniques.

A PDF file (171 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2007-05, together with your name and postal address to:

CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.

Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk