Kavli Affiliate: Felix Fischer
| Summary:
In the symmetric rendezvous problem, two players follow the same (randomized) strategy to visit one of $n$ locations in each time step $t=0,1,2,dots$. Their goal is to minimize the expected time until they visit the same location and thus meet. A canonical strategy due to Anderson and Weber is known to be optimal for $n=2$ and $n=3$, but whether it remains optimal for larger values of $n$ has been an open question since 1990. We show that it does not remain optimal: for any finite $ngeq 4$, we construct an explicit symmetric strategy that achieves a strictly smaller expected meeting time than the Anderson–Weber strategy.
In the Anderson–Weber strategy players stay at a dedicated home location for $n-1$ steps with a certain probability $θ$ and with the remaining probability tour all non-home locations in a random order. Our improving strategy introduces carefully chosen correlations between consecutive tours of the non-home locations. The construction is uniform in $n$ and is guided by a graph-theoretic view in which tours correspond to permutations and meetings to edges in the complement of the derangement graph. By exploiting the clique structure of this graph we obtain a correlated strategy that improves on the Anderson–Weber strategy. For $n=4$, we give an exact expression for the improvement; for any $ngeq 5$, we obtain a lower bound on the expected improvement of $frac483(1-θ)^6(n-1)^8$, where $θin [0,1)$ is the probability of staying at the home location. The graph-theoretic framework we introduce may be useful more widely in the design and analysis of correlated strategies for rendezvous.
| Search Query: arXiv Query: search_query=au:”Fischer Felix”&id_list=&start=0&max_results=10
Read More