返回题库

三人选点游戏

Three-Player Number Game

专题
Strategy / 策略
难度
L4

题目详情

三名玩家（P1、P2、P3）依次从区间 [0,1][0,1] 中选择互不相同的数 x,y,zx,y,z。随后从 [0,1][0,1] 上均匀随机抽取 rr，离 rr 最近的玩家获胜。三人都以最大化自己的获胜概率为目标并采取最优策略。

  1. 若 P1 选择 x=0.25x=0.25，P2 应该选择什么？
  2. P1 的最优先手选择是什么？

Three players (P1, P2, P3) pick distinct numbers x,y,zx, y, z from the interval [0,1][0, 1]. A random number rr is drawn uniformly from [0,1][0, 1], and the player whose number is closest to rr wins. All players play optimally to maximize their win probability.

  1. If P1 chooses x=0.25x=0.25, what should P2 choose?
  2. What is the optimal first move for Player 1?
解析

选定若干点后，每个人的胜率就是其 Voronoi 区间长度。

给定前两步选点 x<yx<y，P3 的最优选择只与三个“空隙”有关：(0,x)(0,x)、(x,y)(x,y)、(y,1)(y,1)。

  • 若 P3 把点放在左端空隙并尽量贴近 xx（取 z<xz<x 且 z→xz\to x），其胜率可逼近 xx。
  • 若放在右端空隙并贴近 yy（z>yz>y 且 z→yz\to y），其胜率可逼近 1−y1-y。
  • 若放在中间空隙 (x,y)(x,y) 内，则无论放在何处，其胜率恒为
y−x2.\frac{y-x}{2}.

所以对给定 x<yx<y，P3 可获得的最大胜率为

M(x,y)=max⁡{x, 1−y, y−x2}.M(x,y)=\max\left\{x,\ 1-y,\ \frac{y-x}{2}\right\}.

(1) 令 x=0.25x=0.25。P2 选择 yy 时，要避免给 P3 留下明显更大的空隙。令三项相等：

0.25=1−y=y−0.252⇒y=0.75.0.25=1-y=\frac{y-0.25}{2}\Rightarrow y=0.75.

因此 P2 应选 y=0.75\boxed{y=0.75}。

(2) 从上式也可看出：P1 选择 xx 后，P2 总能把 P3 的最大可得胜率压到至少为 max⁡{x,12−x}\max\{x,\frac{1}{2}-x\} 的量级；当 x=0.25x=0.25 时可把三项精确拉平到 0.250.25。

因此 P1 的最优先手是把点放在 x=0.25\boxed{x=0.25}（对称地也可选 x=0.75x=0.75）。