论文标题
关于在完整图上对对称性的效果
On the effect of symmetry requirement for rendezvous on the complete graph
论文作者
论文摘要
我们考虑了一款经典的聚会游戏，其中两个玩家试图在一组$ n $的位置相遇。在每个回合中，每个玩家都会访问其中一个位置，并且当玩家在同一位置相遇时，比赛结束了。目的是为两位玩家制定策略，以最大程度地减少预期等待时间，直到会合时间为止。 在不对称的情况下，当玩家的策略可能有所不同时，众所周知，预期的$ \ frac {n+1} {2} $的最佳等待时间是通过等待 - 莫米对策略的策略来实现的，其中一对玩家在一个$ n $ nobles中保持在一个$ N $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $中的位置搜索。但是，如果我们坚持认为球员是对称的 - 预计他们将遵循相同的策略 - 那么，安德森和韦伯提出的最著名的策略将达到渐近的预期等待时间为0.829 n $。 我们表明，对称性的要求确实意味着预期的等待时间需要比不对称的情况大。确切地说，我们证明，如果玩家需要采用相同的策略，则每$ n \ geqslant 2 $，那么预期的等待时间至少为$ \ frac {n+1} {2} {2}+\ varepsilon n $，其中$ \ \ varepsilon = 2^{ - 36} $。
We consider a classic rendezvous game where 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 $\frac{n+1}{2}$ is achieved by the wait-for-mommy pair of strategies, where 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, achieves an asymptotic expected waiting time of $0.829 n$. 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\geqslant 2$, if the players need to employ the same strategy, then the expected waiting time is at least $\frac{n+1}{2}+\varepsilon n$, where $\varepsilon=2^{-36}$.
