On the Effect of Symmetry Requirement for Rendezvous on the Complete Graph

Marthe Bonamy (), Michał Pilipczuk (), Jean-Sébastien Sereni () and Richard Weber ()
Additional contact information
Marthe Bonamy: Centre national de la recherche scientifique, Laboratoire bordelais de recherche en informatique, Université de Bordeaux, F-33405 Talence, France
Michał Pilipczuk: Institute of Informatics, University of Warsaw, 00-927 Warszawa, Poland
Jean-Sébastien Sereni: Service public français de la recherche, Centre national de la recherche scientifique, Complex Systems and Translational Bioinformatics (ICube), Strasbourg, France
Richard Weber: Statistical Laboratory, University of Cambridge, Cambridge CB2 1TN, United Kingdom

Mathematics of Operations Research, 2023, vol. 48, issue 2, 942-953

Abstract: We consider a classic rendezvous game in which two players try to meet each other on a set of n locations. In each round, every player visits one of the locations, and the game finishes when the players meet at the same location. The goal is to devise strategies for both players that minimize the expected waiting time till the rendezvous. In the asymmetric case, when the strategies of the players may differ, it is known that the optimum expected waiting time of ( n + 1 ) / 2 is achieved by the wait-for-mommy pair of strategies, in which one of the players stays at one location for n rounds, while the other player searches through all the n locations in a random order. However, if we insist that the players are symmetric—they are expected to follow the same strategy—then the best known strategy, proposed by Anderson and Weber [Anderson EJ, Weber RR (1990) The rendezvous problem on discrete locations. J. Appl. Probab. 27(4):839–851], achieves an asymptotic expected waiting time of 0.829 n . We show that the symmetry requirement indeed implies that the expected waiting time needs to be asymptotically larger than in the asymmetric case. Precisely, we prove that for every n ⩾ 2 , if the players need to employ the same strategy, then the expected waiting time is at least ( n + 1 ) / 2 + ε n , where ε = 2 − 36 . We propose in addition a different proof for one our key lemmas, which relies on a result by Ahlswede and Katona [Ahlswede R, Katona GOH (1978) Graphs with maximal number of adjacent pairs of edges. Acta Mathematica Academiae Scientiarum Hungaricae 32(1–2):97–120]: the argument is slightly shorter and provides a constant larger than 2 − 36 , namely, 1 / 3600 . However, it requires that n be at least 16. Both approaches seem conceptually interesting to us.

Keywords: Primary: 90B40; secondary: 91A12; 93A14; rendezvous search; search games (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1288 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:2:p:942-953

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().