Optimal symmetric rendezvous among discrete locations
Let $n \ge 4$ and $[n] = \{1, \dots, n\}$. Two agents each visit one of $n$ locations at every time $t \in \mathbb{N}_0 = \{0, 1, 2, \dots\}$. They recognise locations they have visited, but their private labels of the locations are related by a correspondence neither knows; they observe nothing of each other's moves and can communicate only once they meet. Both must follow the same randomized strategy, with independent private randomness. Formally, a strategy is a probability law $\mu$ on sequences in $[n]^{\mathbb{N}_0}$, with the product $\sigma$-algebra. Draw $X = (X_t)$ and $Y = (Y_t)$ independently with law $\mu$, and independently a uniformly random permutation $\pi$ of $[n]$, and let $$T_{\mu,\pi} = \inf\{t \in \mathbb{N}_0 : \pi(X_t) = Y_t\}, \qquad r_n = \inf_{\mu} \mathbb{E}[T_{\mu,\pi}],$$ with $\inf \varnothing = +\infty$ and the expectation over all three random choices. The strategy may depend on $n$ and have arbitrary memory. The first visit is at time $0$ and may already be a meeting; sources that count the first visit as step one report values larger by one.
For two locations, Anderson and Weber showed that visiting a uniformly random location at every step is optimal. Their strategy for $n$ locations randomizes, in each block of $n - 1$ steps after the first, between staying at the initial location and touring the other $n - 1$ locations in random order. Weber proved it optimal for three locations, which in the convention here gives $r_3 = 5/3$. Weber gave a better strategy for four locations, and Cembrano, Fischer and Klimm constructed, for every $n \ge 4$, a strategy with strictly smaller expected meeting time than that of Anderson and Weber. Dani, Hayes, Moore and Russell proved $r_n \ge (0.6389\ldots - o(1))\, n$; the Anderson–Weber strategy has expected meeting time about $0.829\, n$.
Problem. Determine the exact value of $r_n$ for every $n \ge 4$.
Source: Alpern (1976, a seminar talk in Vienna), the Mozart Café problem; see Anderson and Weber (1990) and Alpern (2013), Problem 5. Stated by AIM — Open Applied Problems for n ≥ 4, with time starting at 0, after Cembrano, Fischer and Klimm (2026).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- PR
- Keywords
- AIM Open Applied Problems, rendezvous search, search games
References
@incollection{alpern2013,
author = {Alpern, Steve},
title = {Ten open problems in rendezvous search},
booktitle = {Search Theory: A Game Theoretic Perspective},
editor = {Alpern, Steve and Fokkink, Robbert and G{\k{a}}sieniec, Leszek and Lindelauf, Roy and Subrahmanian, V. S.},
publisher = {Springer},
address = {New York},
year = {2013},
pages = {223--230},
doi = {10.1007/978-1-4614-6825-7_14},
}
@article{anderson1990,
author = {Anderson, E. J. and Weber, R. R.},
title = {The rendezvous problem on discrete locations},
journal = {J. Appl. Probab.},
volume = {27},
number = {4},
year = {1990},
pages = {839--851},
doi = {10.1017/S0021900200028011},
}
@misc{cembrano2026,
author = {Cembrano, Javier and Fischer, Felix and Klimm, Max},
title = {Faster symmetric rendezvous on four or more locations},
year = {2026},
eprint = {2604.02058},
archivePrefix = {arXiv},
note = {Revised August 2026 (v2)},
}
@article{weber2012,
author = {Weber, Richard},
title = {Optimal symmetric rendezvous search on three locations},
journal = {Math. Oper. Res.},
volume = {37},
number = {1},
year = {2012},
pages = {111--122},
doi = {10.1287/moor.1110.0528},
}
@misc{weber2009,
author = {Weber, Richard},
title = {The {A}nderson--{W}eber strategy is not optimal for symmetric rendezvous search on {$K_4$}},
year = {2009},
eprint = {0912.0670},
archivePrefix = {arXiv},
}
@article{dani2016,
author = {Dani, Varsha and Hayes, Thomas P. and Moore, Cristopher and Russell, Alexander},
title = {Codes, lower bounds, and phase transitions in the symmetric rendezvous problem},
journal = {Random Structures Algorithms},
volume = {49},
number = {4},
year = {2016},
pages = {742--765},
doi = {10.1002/rsa.20691},
eprint = {1609.01582},
archivePrefix = {arXiv},
}
@misc{aim-symmetric-rendezvous-discrete-locations,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Optimal symmetric rendezvous among discrete locations}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/320-symmetric-rendezvous-discrete-locations.md},
note = {Entry 320 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00481, "Optimal symmetric rendezvous among discrete locations", clopen.solutions.