Codes, Lower Bounds, and Phase Transitions in the Symmetric Rendezvous Problem

• Published in 2016
• Added on 2019-03-02

In the rendezvous problem, two parties with different labelings of the vertices of a complete graph are trying to meet at some vertex at the same time. It is well-known that if the parties have predetermined roles, then the strategy where one of them waits at one vertex, while the other visits all $n$ vertices in random order is optimal, taking at most $n$ steps and averaging about $n/2$. Anderson and Weber considered the symmetric rendezvous problem, where both parties must use the same randomized strategy. They analyzed strategies where the parties repeatedly play the optimal asymmetric strategy, determining their role independently each time by a biased coin-flip. By tuning the bias, Anderson and Weber achieved an expected meeting time of about $0.829 n$, which they conjectured to be asymptotically optimal. We change perspective slightly: instead of minimizing the expected meeting time, we seek to maximize the probability of meeting within a specified time $T$. The Anderson-Weber strategy, which fails with constant probability when $T= \Theta(n)$, is not asymptotically optimal for large $T$ in this setting. Specifically, we exhibit a symmetric strategy that succeeds with probability $1-o(1)$ in $T=4n$ steps. This is tight: for any $\alpha < 4$, any symmetric strategy with $T = \alpha n$ fails with constant probability. Our strategy uses a new combinatorial object that we dub a "rendezvous code," which may be of independent interest. When $T \le n$, we show that the probability of meeting within $T$ steps is indeed asymptotically maximized by the Anderson-Weber strategy. Our results imply new lower bounds, showing that the best symmetric strategy takes at least $0.638 n$ steps in expectation. We also present some partial results for the symmetric rendezvous problem on other vertex-transitive graphs.

Links

• http://arxiv.org/abs/1609.01582v1
• http://arxiv.org/pdf/1609.01582v1

Other information

BibTeX entry

@article{CodesLowerBoundsandPhaseTransitionsintheSymmetricRendezvousProblem,
	key = {CodesLowerBoundsandPhaseTransitionsintheSymmetricRendezvousProblem},
	type = {article},
	title = {Codes, Lower Bounds, and Phase Transitions in the Symmetric Rendezvous  Problem},
	author = {Varsha Dani and Thomas P. Hayes and Cristopher Moore and Alexander Russell},
	abstract = {In the rendezvous problem, two parties with different labelings of the
vertices of a complete graph are trying to meet at some vertex at the same
time. It is well-known that if the parties have predetermined roles, then the
strategy where one of them waits at one vertex, while the other visits all {\$}n{\$}
vertices in random order is optimal, taking at most {\$}n{\$} steps and averaging
about {\$}n/2{\$}. Anderson and Weber considered the symmetric rendezvous problem,
where both parties must use the same randomized strategy. They analyzed
strategies where the parties repeatedly play the optimal asymmetric strategy,
determining their role independently each time by a biased coin-flip. By tuning
the bias, Anderson and Weber achieved an expected meeting time of about {\$}0.829
n{\$}, which they conjectured to be asymptotically optimal.
  We change perspective slightly: instead of minimizing the expected meeting
time, we seek to maximize the probability of meeting within a specified time
{\$}T{\$}. The Anderson-Weber strategy, which fails with constant probability when
{\$}T= \Theta(n){\$}, is not asymptotically optimal for large {\$}T{\$} in this setting.
Specifically, we exhibit a symmetric strategy that succeeds with probability
{\$}1-o(1){\$} in {\$}T=4n{\$} steps. This is tight: for any {\$}\alpha < 4{\$}, any symmetric
strategy with {\$}T = \alpha n{\$} fails with constant probability. Our strategy uses
a new combinatorial object that we dub a "rendezvous code," which may be of
independent interest.
  When {\$}T \le n{\$}, we show that the probability of meeting within {\$}T{\$} steps is
indeed asymptotically maximized by the Anderson-Weber strategy. Our results
imply new lower bounds, showing that the best symmetric strategy takes at least
{\$}0.638 n{\$} steps in expectation. We also present some partial results for the
symmetric rendezvous problem on other vertex-transitive graphs.},
	comment = {},
	date_added = {2019-03-02},
	date_published = {2016-04-10},
	urls = {http://arxiv.org/abs/1609.01582v1,http://arxiv.org/pdf/1609.01582v1},
	collections = {Easily explained,Protocols and strategies},
	url = {http://arxiv.org/abs/1609.01582v1 http://arxiv.org/pdf/1609.01582v1},
	year = 2016,
	urldate = {2019-03-02},
	archivePrefix = {arXiv},
	eprint = {1609.01582},
	primaryClass = {math.CO}
}