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

• 成果类型: Article
• 署名作者: Bonamy, Marthe; Pilipczuk, Michal; Sereni, Jean-Sebastien; Weber, Richard
• 署名单位: Universite de Bordeaux; Centre National de la Recherche Scientifique (CNRS); University of Warsaw; University of Cambridge
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1288
• 发表日期: 2023
• 页码: 942-953
• 关键词: search; agents

摘要

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 + epsilon n, where epsilon = 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 seemconceptually interesting to us.