差 2 也算赢

2 Below I

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

你和朋友各自选择 1..100 的整数。若你选的数严格更大，则你赢 1；若相等则 0；但如果你选的数恰好比对方小 2，你也算赢。

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

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

You and friend play a game where you both select an integer $1-100$ . The winner receives $1 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 $2$ below the larger integer. For example, if you select $80$ and your friend selects $82$ , 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 $X$ from some appropriately determined distribution. Find $\text{Var}(X)$ .

解析

注意到任意 $n$ 都被 $n+3$ 支配（因为 $n+3$ 额外还能赢 $n+2$ ），因此均衡只会在 98、99、100 上混合。

为避免被对方针对，必须在 98、99、100 上取均匀分布。

于是 $X\sim\mathrm{Unif}\{98,99,100\}$ ，

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

Original Explanation

Suppose you were planning to select a value $n$ . Note that $n+3$ is strictly better than $n$ , as $n+3$ will beat all integers $n$ would beat, as well as the integer $n+2$ . Therefore, whenever you can select $n$ , you should select $n+3$ . This means that your strategy should be to select $98, 99,$ or $100$ with some probabilities.

By the symmetry of the game, your friend should also select those values with the same probabilities. In particular, if you select $98-100$ with equal probability, no matter what probabilities your friend selects $98, 99,$ and $100$ with, the expected payout for each player is $0$ by symmetry. This is because we see that $98$ is beat by $99$ , $99$ is beat by $100$ , and $100$ is beat by $98$ , so each of the three outcomes is dominated by one other outcome.

Furthermore, if you select a non-uniform distribution on $98, 99, 100$ for your values, there exists a strategy your friend can select that yields positive expected payout for them. The probabilities of selecting each of the values for you would be $p_1, p_2,$ and $1-p_1-p_2$ . For a numerical demonstration, say $p_1 = \frac{1}{5}$ and $p_2 = \frac{1}{2}$ . Then your friend should always select the value that maximizes their probability of winning. In this case, they should select $100$ , as the expected payout would be $(-1) \cdot \frac{1}{5} + (1) \cdot \frac{1}{2} + (0) \cdot \frac{3}{10} > 0$ . Namely, if $x$ is the value assigned to probability $\max\{p_1, p_2, 1-p_1-p_2\}$ , then your friend should always select the value that beats $x$ . Therefore, to eliminate this opportunity, you should select a uniform distribution among $98-100$ .

This means $X \sim \text{DiscreteUnif}\{98, 99, 100\}$ , so $\mathbb{E}[X] = 99$ and $\text{Var}(X) = \frac{(98-99)^2 + (99-99)^2 + (100-99)^2}{3} = \frac{2}{3}$ .