On the effect of symmetry requirement for rendezvous on the complete graph
In: ISSN: 0364-765X, 2023
Online
academicJournal
Zugriff:
International audience ; 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.829n. 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.
Titel: |
On the effect of symmetry requirement for rendezvous on the complete graph
|
---|---|
Autor/in / Beteiligte Person: | Bonamy, Marthe ; Pilipczuk, Michał ; Sereni, Jean-Sébastien ; Weber, Richard ; Laboratoire Bordelais de Recherche en Informatique (LaBRI) ; Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS) ; Institute of Informatics Warsaw ; Faculty of Mathematics, Informatics, and Mechanics Warsaw (MIMUW) ; University of Warsaw (UW)-University of Warsaw (UW) ; Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube) ; École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg) ; Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE) ; Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie - CNRS Chimie (INC-CNRS)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie - CNRS Chimie (INC-CNRS)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique ; Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS) ; Institut für Informatik München/Munich (LMU) ; Ludwig Maximilian University Munich = Ludwig Maximilians Universität München (LMU) ; ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016) ; ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017) ; European Project: 677651,H2020,ERC-2015-STG,TOTAL(2016) |
Link: | |
Zeitschrift: | ISSN: 0364-765X, 2023 |
Veröffentlichung: | HAL CCSD ; INFORMS, 2023 |
Medientyp: | academicJournal |
DOI: | 10.1287/moor.2022.1288 |
Schlagwort: |
|
Sonstiges: |
|