PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] three-cornered dual

看板Prob_Solve (計算數學 Problem Solving)作者pika0923 (宜安)時間10年前 (2014/09/24 19:39)推噓0(0推 0噓 0→)

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

我也沒正式學過賽局只稍微看過一些相關的文章就用一些土法鍊鋼的方法來看這題吧 ※ 引述《cckk3333 (皓月)》之銘言： : 我在某個面試遇到這個題目 : 今天剛好又在某本書看到類似的題目 : 想跟版友討論一下 : 現在有三個人 A、B、C 佔在三角型的三個角上 : A、B、C 依序射擊 (A優先開始) : 他們每個人都可以選擇射擊另外兩個的其中一個或放棄射擊 : (放棄射擊是某題答案的正解不過不是我討論的重點所以我直接把他當作選項) : 最後一個留下的人勝利 : (1) A B C 的命中率是 30% 100% 50% : A的最佳策略是 A射地板 B射C A跟C最後決鬥 : ( 答案說 B 一定會射 C 感覺好像很合理但不知道有沒有比較量化的解釋 : 可以說明 B 射 C 比較好而不是射地板 ) 其實我覺得加入放棄射擊加進來是一個很微妙的狀況先把這個題目稍微簡化讓其中一個人命中率變0% 這問題就縮減到雙人決鬥在這邊要先作一個假設：所有人作決策的時候都是依賽局本身的狀態來看的因此在同一狀態下決策不變 (避免p導至非p的無限矛盾) 所以這時候兩人的決策就是射擊和不射擊在存活率最大化的狀態可以畫出一張類似囚犯困境的圖逗號前是先手的存活率逗號後是後手的存活率 x是兩人命中率函數算出來的值 \先手 | 選擇射擊 | 放棄射擊後手\ | | ------------------------------------- | | 選擇射擊 | x , 1-x | 0 , 1 | | ------------------------------------- | | 放棄射擊 | 1 , 0 | 1 , 1 | | 至於說囚犯困境要怎樣說是最好的好像也有不只一種說法 -- 一樣的推回三人決鬥的時候也依然會出現類似的問題某人決定射擊而且射中了那麼他就會在雙人決鬥中擔任後手在這狀況下他就沒辦法取得雙人決鬥中對自己最有利的先手狀況一樣的可能會造成三個人都不進行射擊 -- 但如果是在快沉的船決定誰可以離開的這種情形都不攻擊會造成全死那這時候狀況又不同了在這時候雙人決鬥就顯然就一定要攻擊了 \先手 | 選擇射擊 | 放棄射擊後手\ | | ------------------------------------- | | 選擇射擊 | x , 1-x | 0 , 1 | | ------------------------------------- | | 放棄射擊 | 1 , 0 | 0 , 0 | | 回到一開始的 30% 100% 50% 的問題雙人狀態的決策一定是打對方沒問題三人的決策用<***>表示例<-AB> 代表A放棄射擊 B打A C打B <-??> 若A棄攻 <--?> 若B棄攻這時候如果C也放棄的話穩死所以C一定會打人在雙人決鬥中C必定後手那麼一定會選擇打100%的B <--B> 在這時候第一個死的一定是B 回到B的觀點如果不棄攻的話一定是選擇打C 然後C穩死的 <-Cx> 於是B一定會攻擊而非棄攻在A的棄攻視角會看到A先手對上B的賽局 (1st case: A vs B) <B??> 回到A的視角如果A打算打人會選擇B 這時候如果成功是A後手對上C的賽局 (2nd case: C vs A) <B-?> 而如果B存活下來了且選擇棄攻 <B--> 這時候C選擇棄攻會獲得最好的對決條件反過來說B不會讓這分枝出現 <BCx> 一樣的 B要攻擊一定打C 打A不會讓他有更好的雙人決鬥條件 (3rd case: A vs B) 基本上第一個結果和第三個結果是一樣的如果算出來A在第二個結果有比較高的存活率那麼他會選擇打B 否則棄攻計算： x先手y後手的先手勝率 = x/(x+y-xy) 後手勝率 = (y-xy)/(x+y-xy) (推導就省略了反正就是個樹狀結構) 1st/3rd: 0.3 2nd: 約0.23 所以A棄攻比較好解是<-Cx> -- : (2) A B C 命中率都是 P : 如果 P = 1 那就不會有人願意第一個射擊 : 但如果 P =/= 1 不知道情況有沒有不一樣類似上面講的囚犯困境重點仍在"如果大家都不射擊會怎樣" : (3) 面試的題目 A B C 命中率是 30% 50% 70% : 每個人的最佳策略 : --------------------------------------------------------------- : 這感覺跟賽局有點關係 : 不過小弟沒有學過 : 不知道有沒有版上的先進可以提點一下 : 感謝了最後這個依然可以用上面的作法分析而有沒有棄攻的選項其實多少會影響答案要算的時候大概就是先把6種雙人決鬥的狀況先算完再來推導比較能看出來只是這裡沒有100%可以拿來簡化計算就懶得算了XD -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.18.121 ※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1411558773.A.188.html