Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-09T01:33:53.460Z Has data issue: false hasContentIssue false
  • English
  • Français

Rendezvous Search with Revealed Information: Applications to the Line

Part of: Operations research and management science

Published online by Cambridge University Press:  14 July 2016

Steve Alpern
Steve Alpern*
Affiliation:
London School of Economics
*
∗ Postal address: Department of Mathematics, London School of Economics, London WC2A 2AE, UK. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 while playing the game. We consider the effect on rendezvous times of giving the players some information about past actions and chance moves, enabling each of them to apply Bayesian updates to improve his knowledge of the other's whereabouts. This technique can be used to give lower bounds on the rendezvous times of the original game (without any revealed information). We consider the case in which they are placed a known distance apart on the line graph Q (known as ‘symmetric rendezvous on the line’). Our approach is to concentrate on a general analysis of the effect of revelations, rather than compute the best bounds possible with our technique.

Keywords

Rendezvoussearchcommon interest gameteam theory

MSC classification

Primary: 90B40: Search theory
Type
Research Article
Information
Journal of Applied Probability , Volume 44 , Issue 1 , March 2007 , pp. 1 - 15
Copyright
Copyright © Applied Probability Trust 2007 

References

Alpern, S. (1995). The rendezvous search problem. SIAM J. Control Optimization 33, 673–683.Google Scholar
Alpern, S. and Gal, S. (1995). Rendezvous search on the line with distinguishable players. SIAM J. Control Optimization 33, 1270–1276.Google Scholar
Alpern, S. and Gal, S. (2003). The Theory of Search Games and Rendezvous (Internat. Ser. Operat. Res. Manag. Sci. 55). Kluwer, Boston, MA.Google Scholar
Alpern, S. and Gal, S. (2006). Two conjectures on rendezvous in K_{3}. Res. Rep. LSE-CDAM-2006-21, Department of Mathematics, London School of Economics. Available at http://www.cdam.lse.ac.uk/Reports/reports2006.html.Google Scholar
Alpern, S., Baston, V. and Essegaier, S. (1999). Rendezvous search on a graph. J. Appl. Prob. 36, 223–231.CrossRefGoogle Scholar
Anderson, E. J. and Essegaier, S. (1995). Rendezvous search on the line with indistinguishable players. SIAM J. Control Optimization 33, 1637–1642.Google Scholar
Anderson, E. J. and Weber, R. R. (1990). The rendezvous problem on discrete locations. J. Appl. Prob. 28, 839–851.Google Scholar
Baston, V. J. (1999). Two rendezvous search problems on the line. Naval Res. Logistics 46, 335–340.Google Scholar
Baston, V. and Gal, S. (2001). Rendezvous search when marks are left at the starting points. Naval Res. Logistics 48, 722–731.Google Scholar
Crawford, V. P. and Haller, H. (1990). Learning how to cooperate: optimal play in repeated coordination games. Econometrica 58, 571–596.Google Scholar
Han, Q., Du, D., Vera, J. and Zuluaga, L. F. (2006). Improved bounds for the symmetric rendezvous value on the line. To appear in Operat. Res. Google Scholar
Lim, W. S., Alpern, S. and Beck, A. (1997). Rendezvous search on the line with more than two players. Operat. Res. 45, 357–364.Google Scholar
Uthaisombut, P. (2006). Symmetric rendezvous search on the line using move patterns with different lengths. Submitted.Google Scholar
Weber, R. R. (2006). The optimal strategy for symmetric rendezvous search on K_{3}. Preprint, Statistical Laboratory, University of Cambridge. Available at http://www.statslab.cam.ac.uk/∼rrw1/research/weber-k3.pdf.Google Scholar