Rendezvous Search on the Line with Indistinguishable Players
Rendezvous Search on the Line with Indistinguishable Players
复制标题
与无法区分的玩家在线进行集合搜索
DOI：
10.1137/s0363012993260707
复制
发表时间：
1995
影响因子：
2.2
通讯作者：
Skander Essegaier
中科院分区：
文献类型：
--
作者：
E. Anderson;Skander Essegaier
阿尔珀恩（Alpern）引入了一个问题，其中两个玩家以从两者已知的有限分布$ f $中提取的距离放置在实际线路上。他们可以以最大的速度移动，并希望尽快见面。既不知道对方的方向，也不知道线上有正方向的共同概念。需要找到对称的会合值$ r^{s}（f）$，这是使用相同混合策略的玩家可以实现的最低预期会议时间。这与玩家无法区分的情况相对应，他们都从不知道自己的名字的控制器那里拿出指示。在本文中，我们提供了一种混合策略，其预期会议时间为$ 1.78D+\ mu /2 $，其中$ d $是$ f $的最大值和$ \ mu $的平均值。这导致上限$ r^{s}（f）\ le 1.78d+\ mu /2 $上的对称汇合值，该值大于上限$ r^s（f）\ le 2d+\ mu / 2 $由Alpern获得。
Alpern introduced a problem in which two players are placed on the real line at a distance drawn from a bounded distribution $F$ known to both. They can move at maximum velocity one and wish to meet as soon as possible. Neither knows the direction of the other, nor do they have a common notion of a positive direction on the line. It is required to find the symmetric rendezvous value $R^{s}(F)$, which is the minimum expected meeting time achievable by players using the same mixed strategy. This corresponds to the case where the players are indistinguishable they both take directions from a controller who does not know their names. In this paper we give a mixed strategy which has an expected meeting time of $1.78D+\mu /2$, where $D$ is the maximum of $F$ and $\mu$ its mean. This leads to an upper bound $R^{s}(F)\le 1.78D+\mu /2$ on the symmetric rendezvous value, which is better than the upper bound $R^s(F)\le 2D+\mu /2$ obtained by Alpern.