返回题库

差 2 也算赢 I

2 Below I

专题
Algorithmic Programming / 算法编程
难度
L4

题目详情

你和朋友各自选择 1 到 100 的一个整数。赢家从输家那里赢 1 美元。

  • 若你选的数严格更大，你赢。
  • 若相等，没人赢。
  • 但如果你选的数恰好比对方小 2，你也算赢（例如你选 80，对方选 82，则你赢）。

双方都最优博弈时，最优策略是混合策略：从某个分布抽取随机变量 XX 作为选择。

求 Var(X)\mathrm{Var}(X)。

You and friend play a game where you both select an integer 1−1001-100. The winner receives 1 dollar from the loser. The winner is the player who selects the strictly higher number. If there is a tie, then nothing happens. However, a player can also win by selecting a value exactly 22 below the larger integer. For example, if you select 8080 and your friend selects 8282, you are the winner in this case. Assume both you and your friend play optimally. The optimal strategy here is a mixed strategy, where you select a random value XX from some appropriately determined distribution. Find Var(X)\text{Var}(X).

解析

注意到任何 n≤97n\le 97 都被 n+3n+3 严格支配：n+3n+3 至少能赢与 nn 相同的情形，并且还能额外赢过对方选 n+2n+2 的情形。

因此均衡的支持集只可能落在 {98,99,100}\{98,99,100\}。

在该 3 点支持集上，为避免被对手针对，必须使对手在这 3 点上的期望收益相同，从而得到唯一对称均衡为均匀分布：

P(X=98)=P(X=99)=P(X=100)=13.P(X=98)=P(X=99)=P(X=100)=\frac{1}{3}.

于是

E[X]=99,Var(X)=(98−99)2+(99−99)2+(100−99)23=23.\mathbb{E}[X]=99, \quad \mathrm{Var}(X)=\frac{(98-99)^2+(99-99)^2+(100-99)^2}{3}=\frac{2}{3}.

所以 Var(X)=23\boxed{\mathrm{Var}(X)=\frac{2}{3}}。