Faster Symmetric Rendezvous on Four or More Locations
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908933552078848 |
|---|---|
| author | Cembrano, Javier Fischer, Felix Klimm, Max |
| author_facet | Cembrano, Javier Fischer, Felix Klimm, Max |
| contents | 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. Anderson and Weber [J. Appl. Prob., 1990] proposed a strategy that operates in rounds of $n-1$ steps: a player either remains in one location for $n-1$ steps or visits the other $n-1$ locations in random order; the choice between these two options is made with a probability that depends only on $n$. The strategy is known to be optimal for $n=2$ and $n=3$, and there is convincing evidence that it is not optimal for $n=4$. We show that it is not optimal for any $n\geq 4$, by constructing a strategy with a smaller expected meeting time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_02058 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Faster Symmetric Rendezvous on Four or More Locations Cembrano, Javier Fischer, Felix Klimm, Max Optimization and Control Computer Science and Game Theory 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. Anderson and Weber [J. Appl. Prob., 1990] proposed a strategy that operates in rounds of $n-1$ steps: a player either remains in one location for $n-1$ steps or visits the other $n-1$ locations in random order; the choice between these two options is made with a probability that depends only on $n$. The strategy is known to be optimal for $n=2$ and $n=3$, and there is convincing evidence that it is not optimal for $n=4$. We show that it is not optimal for any $n\geq 4$, by constructing a strategy with a smaller expected meeting time. |
| title | Faster Symmetric Rendezvous on Four or More Locations |
| topic | Optimization and Control Computer Science and Game Theory |
| url | https://arxiv.org/abs/2604.02058 |