一題機率遊戲中的策略設計 - 推理遊戲

誠如 ddavid 所說過的，這個問題是一個很標準的賽局理論問題。
要正確理解這個問題，就要知道什麼是純策略和混合策略。

http://en.wikipedia.org/wiki/Strategy_%28game_theory%29
http://zh.wikipedia.org/wiki/%E7%AD%96%E7%95%A5_(%E5%8D%9A%E5%BC%88%E8%AB%96)

先不要管十回合的問題，只考慮一回合，我們追求勝分的期望值就好。
(勝分 = 我方得分 - 對方得分)

首先如 ars1an 在原文的推文中所說，這題沒有純策略解， (這很好證)
而 John Nash 告訴我們平衡點一定存在，所以我們要追求的是一個混合策略。

那麼，

1.勝分是零和，所以最佳策略是 weak Nash equilibrium (頂多保證不敗)。

2.最佳策略必不敗於任何純策略 (廢話)。

3.若某策略不敗於任何純策略，則該策略不敗於任何策略。
(因為任何策略的勝分期望值都是純策略勝分期望值的加權平均)

4.由 2,3 兩點得知，我們只要檢查對所有純策略都不敗即可。



先算簡單的，若我方出 x 對方出 y， x < y 則勝分期望值為：

xy + x(1-y) - y(1-x) = x - y + xy

若 x > y 則反過來：

x - y - xy

假設在最佳策略中我方出數字 x 的機率為 p(x)，而對方出 y，勝分期望值為：

∫{0~y} p(t)(t-y+ty) dt + ∫{y~1} p(t)(t-y-ty) dt
= ∫{0~1} p(t)(t-y-ty) dt + 2∫{0~y} p(t)ty dt
= (1-y)∫{0~1} p(t)t dt - y∫{0~1} p(t) dt + 2y∫{0~y} p(t)t dt
= (1-y)∫{0~1} p(t)t dt - y + 2y∫{0~y} p(t)t dt

這時候當然要令 G(y) = ∫{0~y} p(t)t dt，則

= (1-y) G(1) - y + 2y G(y)

我們的目的是找到一個 p 使得上式恆不小於零。
後面的過程我忘了，有一部分可能是湊出來的：

1. G(1) >= 1/2
2. G(y) >= 1/2 - (1/2y - 1/2) G(1)
3. 假設 G(y) >= 3/4 - 1/(4y) 則可滿足 2.
4. 假設 G(y) = 3/4 - 1/(4y) → p(t) = 1/(4t^3) when t > 1/3
5. ∫{1/3~1} p(t) dt = 1, 機率分布剛好用完, 剩下 0~1/3 間都是 0

----

(後來我想起來這裡是怎麼算的了 XD

考慮對方使用相同策略的情況，得到
∫{0~1} p(y) [(1-y) G(1) - y + 2y G(y)] = 0

但是 p(y) >= 0, (1-y) G(1) - y + 2y G(y) >= 0
所以 p(y) = 0 or (1-y) G(1) - y + 2y G(y) = 0 almost everywhere

因為 y < 1/3 時 (1-y) G(1) - y + 2y G(y) > 0,
所以 0~1/3 間 p(y) 都是零 (a.e., 不過沒差)

然後再從 1/3 往上逐步逼到 1/(4t^3) )

----

所以若 p(t) = 0, when t < 1/3
1/(4t^3), otherwise

則
1. ∫{0~1} p(t) dt = 1, p 是個機率分布

2. G(y) = 0, when y < 1/3
3/4 - 1/(4y), otherwise

3. G 滿足 (1-y) G(1) - y + 2y G(y) >= 0

4. 事實上當 y >= 1/3 時 (1-y) G(1) - y + 2y G(y) = 0
而 y < 1/3 時 > 0

5. 也就是說，這個策略和出 1/3 以上任何數字的純策略打平，
而對出低於 1/3 的任何數字的純策略則會勝出。

6. 也就是說，這個策略和任何只用 1/3~1 之間數字混出來的策略都打平，
對其他則勝出。

--