Re: [討論] 一題機率遊戲中的策略設計

看板Inference (推理遊戲)作者isnoneval (天道)時間14年前 (2010/02/08 00:39)推噓3(3推 0噓 0→)

留言3則, 3人參與討論串5/5 (看更多)

誠如 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 之間數字混出來的策略都打平，對其他則勝出。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.217.110.59 ※ 編輯: isnoneval 來自: 61.217.110.59 (02/08 00:43)