返回题库

机器人举重

Robot Weightlifting

专题
Probability / 概率
难度
L6

题目详情

机器人举重世界锦标赛的决赛即将开始！3 号、2 号和 1 号种子共三名机器人仍在角逐中。他们从 3 号种子到 1 号种子轮流公开声明他们将尝试举起的确切重量（任何非负实数），并且没有机器人可以选择与之前的机器人完全相同的重量。一旦宣布了三个重量，机器人就会尝试举重，成功举起最大重量的机器人就是获胜者。如果所有机器人都失败了，它们只会重复相同的举重重量，直到至少有一名机器人成功。

假设如下：

  1. 所有机器人成功举起给定重量 w 的概率 p(w) 都是相同的；

  2. p(w) 被所有竞争者确切知道，它是连续的，随着 w 的增加而严格递减，p(0) = 1，并且当 w -> 无穷大时，p(w) -> 0；并且

  3. 所有竞争者都希望最大化他们赢得 RWWC 的机会。

如果 w 是 3 号种子应该请求的重量，求 p(w)。将你的答案精确到小数点后六位。

The Robot Weightlifting World Championship’s final round is about to begin! Three robots, seeded 1, 2, and 3, remain in contention. They take turns from the 3rd seed to the 1st seed publicly declaring exactly how much weight (any nonnegative real number) they will attempt to lift, and no robot can choose exactly the same amount as a previous robot. Once the three weights have been announced, the robots attempt their lifts, and the robot that successfully lifts the most weight is the winner. If all robots fail, they just repeat the same lift amounts until at least one succeeds.

Assume the following:

1) all the robots have the same probability p(w) of successfully lifting a given weight w;

2) p(w) is exactly known by all competitors, continuous, strictly decreasing as the w increases, p(0) = 1, and p(w) -> 0 as w -> infinity; and

3) all competitors want to maximize their chance of winning the RWWC.

If w is the amount of weight the 3rd seed should request, find p(w). Give your answer to an accuracy of six decimal places.

解析

Original Explanation

To solve this problem, it’s best to work backwards from the decision of the 1st seed, who selects their attempted weight last. We will work with the 1st, 2nd, and 3rd seed’s probability of successfully lifting their selected weights (we can ignore the actual weight amounts and just phrase everything in terms of these probabilities).

So the 1st seed knows the probability that the 3rd seed will successfully lift (call it x), and the probability that the 2nd seed will succeed (y). Given the 1st seed’s lift will only be judged against the other two lifts, there are three possible strategies to consider for the 1st seed, any other strategy is dominated by one of these:

  1. lift an arbitrarily small amount more than the 3rd seed, to have (x-ε) chance of success,
  2. lift an arbitrarily small amount more than the 2nd seed, to have (y-ε) chance of success, or
  3. lift zero weight with success probability 1.

Without loss of generality, we can assume x<y and compute the curves that separate the regions where each of these strategies is optimal by setting their payoffs equal. The probability of a 1st seed victory of the respective strategies, as ε -> 0+, are

  1. x/(1-(1-x)2(1-y))
  2. (1-x)y/(1-(1-x)(1-y)2)
  3. (1-x)(1-y)

Setting these pairwise equal divides the space into three regions. We can reflect this about the line x=y and get what the 1st seed will do in every circumstance (represented by the yellow, blue, and green regions in the graph). We then can optimize the 2nd seed’s choice conditional on the 3rd seed’s selection (represented by the red line in the graph).

Remarkably, the function for the 2nd seed’s optimal probability of lifting (y), dependent on x, is piecewise smooth with six different pieces and two jump discontinuities. Once we have these we can detect the optimal choice for the 3rd seed (the circled point on the graph). This ends up being 0.286833… which is one of the points of triple intersection of the three strategies listed above. That is, it turns out to be in the best interest of the 3rd seed to “collaborate” with the 2nd seed to make the 1st seed indifferent between the three strategies listed1. Unfortunately for the 3rd seed, the only way to get the 2nd seed to cooperate with this plan is to accept the worse of the two positions in this triple-intersection point. So the selections will be:

x = 0.286833…

y = 0.436041…

z = 1

Which leads to the following probabilities of winning:

3rd seed: 0.286833…

2nd seed: 0.310970…

1st seed: 0.402197…

[1] While the 1st seed is indifferent between the three idealized strategies, only one of them is achievable because the other two strategies are limiting as ε -> 0. So we can assume that if the 3rd seed and 2nd seed exactly measured their weights to perfect precision, the 1st seed would choose the zero weight lift.

Congrats to this month’s solvers who successfully found the answer!