文章目錄
- 博弈論
- 什么是博弈論？
- 博弈的前提
- 博弈的要素
- 博弈的分類
- 非合作博弈——有限兩人博弈囚徒困境
- 合作博弈——無限多人博弈囚徒困境
- 常見的博弈定律
- 零和博弈
- 重復博弈
- 智豬博弈
- 斗雞博弈
- 獵鹿博弈
- 蜈蚣博弈
- 酒吧博弈
- 槍手博弈
- 警匪博弈
- 海盜分金
- 巴什博弈
博弈論
什么是博弈論？
我個人的理解是，通過分析與事情有關的所有元素，在力所能及的范圍內尋求最好的結果 ，前半句即博弈，后半句為博弈的意義。
博弈的深層意義在于，所得的最優策略與對手在博弈中的操作沒有依存關系。簡言之，其理性思想就是 抱最好的希望，做最壞的打算。
博弈的前提
博弈理論假定參與博弈的人必須是理性的，理性的人在博弈過程中會將 自身利益最大化 作為目標。其實這未必不是博弈的局限性，記得前段時間看到的一篇博客很有意思：在一個狼吃羊的AI智障游戲中，狼發現自己吃不到羊，直接選擇了「自殺」。然而，狼選擇撞石的原因竟是「自殺分數高」！（全文在這里）
出現自殺這一博弈結果的主要原因當然是在訓練過程中將分數設置成了權重最大的項，甚至重于生命，但也側面印證了 局中人的絕對理性 。
博弈的要素
博弈需要具備的要素通常有五個方面：
局中人
兩人博弈 or 多人博弈
策略
- 有限博弈：每個參與人明確的知道交易次數。不用給自己留后路，此種博弈下信譽沒有保障。
- 無限博弈：每個參與人不知道博弈會在什么時候停止，誰都考慮為自己留后路。此種博弈中妥協會比較多，信譽也比較好。
得失
局中人博弈的得失與兩個因素相關：一是其自身所選定的策略，二是其他局中人所選定的策略。每個局中人在博弈結束時的得失可根據所有局中人選定的一組策略函數來判定，這個函數稱為 支付函數 。
次序
- 動態博弈：局中人的行動有先后順序，且 后做出選擇的人 知道 先做出選擇之人 的行動。
- 靜態博弈：局中人同時選擇要采取的策略。或者 后做出選擇的人 不知道 先做出選擇之人 的行動。
均衡
博弈通常都有一個 穩定的結果 ，謂之均衡，或稱平衡。
博弈的分類
上面講到的 動態博弈 與 靜態博弈 的劃分；有限博弈 與 無限博弈 的劃分。都是博弈的分類方法。而經濟學中通常將博弈分為：非合作博弈 和 合作博弈。
非合作博弈比合作博弈更簡單，理論也更成熟。根據復合特征來劃分，非合作博弈可分為四類：
-
完全信息靜態博弈： 對應的均衡概念是 納什均衡 。
-
完全信息動態博弈： 對應的均衡概念是 子博弈精煉納什均衡 。
-
不完全信息靜態博弈： 對應的均衡概念是 貝葉斯納什均衡 。
-
不完全信息動態博弈： 對應的均衡概念是 精煉貝葉斯納什均衡 。
-
完全信息博弈：每位參與者都能準確地知道所有其他參與者的行為，以及整個博弈結構；
-
不完全信息博弈：在這類博弈中，每位參與者對所有其他參與者的信息不夠了解，或不了解整個博弈結構。
非合作博弈——有限兩人博弈囚徒困境
在上文中提到，博弈的意義在于找到 最好結果，但要明白的是，在 有限博弈 中，這個最好結果是是個人最優解而非團體最優解。也就是 在保障自身利益的前提下，每個人的策略都是對其他人的策略的最優反應。 我們通過 約翰·納什 創造的 囚徒困境 博弈故事進一步解釋：
- 兩個共謀犯罪的人被關入監獄，不能互相溝通情況。如果兩個人都不揭發對方，則由于證據不確定，每個人都坐牢五年；
- 若一人揭發，而另一人沉默，則揭發者因為立功而坐牢一年，沉默者因不合作而判十年；
- 若互相揭發，則因證據確鑿，二者都判刑八年。
雖然對于團體而言最優解是大家都不揭發對方，然而對于囚徒而言：
- 如果對方沉默，自己揭發的話判一年、沉默的話判一年，揭發更好；
- 如果同伙揭發，自己揭發的話判八年、沉默的話判十年，揭發更好。
這個結果說明了 納什平衡 的存在，即在非合作博弈中存在一個均衡解，這個解可使博弈雙方的利益都獲得保障，這個解并非團隊最優解，卻是個人最優解。
囚徒困境是一個 非合作博弈 ，原因在于博弈次數只有一次，即有限博弈。有限博弈下，無論之前選擇了多少次合作，最后一次局中人必然會選擇背叛對方以尋求個人利益最大化，可以理解為：
- 如果不是最后一次博弈，你背叛人家的話人家一定會報復你，對方也一樣，大家都怕背叛對方的話下一次博弈中對方的報復，導致本來可以拿到的團隊最優解拿不到了。
- 但如果是最后一次博弈的話，萬一對方背叛你，你就沒有報復機會了，那不如我先報復他。
但是，如果是 無限博弈 ，并且是 多人博弈 的話，就會呈現 合作博弈 。
合作博弈——無限多人博弈囚徒困境
在上一個囚徒困境的基礎上，如果抓緊來的是犯罪團伙，并且不告訴它們要審問他們多少次，只告訴他們還是剛才的規矩，不過每個人的坐牢時間是根據每次審訊結果累加。在這種情況下，囚徒們就會意識到：如果持續選擇都沉默，大家一起每輪多坐五年牢；如果持續選擇彼此揭發，大家每輪多坐八年牢。通過這樣的思考，參與者之間合作的動機就非常明顯了。
針對 無限多人博弈 ，羅伯特·阿克塞爾羅德制定了類似的實驗，最終取得 最好結果（對于變種囚徒困境而言就是坐牢時間最少的囚徒，阿克塞爾羅德的實驗中是得分最高的程序） 的程序一般具有三個特點：
- 善良性：從不主動背叛別人；
- 可激怒性：對于別人的背叛會進行報復；
- 寬容性：對于別人的背叛不會無休止的報復。
這種一報還一報的策略不僅優秀而且清晰，其特性通常在幾次博弈后就能被清晰地辨識出來（其他程序：這個程序是個狼滅，不好惹，只有主動和他合作才能贏！），而其他復雜的策略并沒有得到優秀的結果，對手無法總結與其相處的規律。
羅伯特·阿克塞爾羅德的研究揭示了合作的必要條件：
- 博弈要持續進行下去，參與者在一次或幾次的博弈中是找不到合作動機的；
- 要對對手的行為做出回報，這個回報可以是好的，也可以是壞的，若一個人永遠選擇合作，那么是不會有太多人與他合作的。
常見的博弈定律
零和博弈
零和博弈是最常見的博弈，零和博弈屬于非合作博弈。即參與博弈賽局的雙方，在嚴格遵守博弈規則的前提條件下，若是其中一方可以獲得利益，也就意味著另一方的利益必然受損。所以，博弈雙方的收益和損失之和永遠為零，即博弈雙方不存在合作的可能。
與之對應的是 合作雙贏，即在某種程度上保證雙方達成 利己且不損人 的合作關系。通常是因為在零和博弈中雙方都沒有很大把握能一定勝出、而失敗的成本太大的情況下。
重復博弈
通過兩種囚徒困境的探討，我們發現當博弈僅進行一次，人們往往更加關心它的最終結果；當博弈重復多次，人們將舍棄眼前利益而選取更長遠的利益，即如單次博弈結果的利益讓步與總體博弈結果的利益。影響重復博弈最終結果的因素，主要是重復博弈所進行的次數以及信息的完整性。
可以將重復博弈總結成三個基礎特征：
- 在進行重復博弈的過程中并沒有結果上的關聯，簡言之就是 上一個階段所進行的博弈，并不會改變接下來所要進行的博弈結構。
- 在進行重復博弈的每個階段，所有的參與者都能夠看到前面的參與者所做出的決策。
- 對于參與重復博弈的參與者而言，他們所獲得的收益是在每個階段所獲得收益的加權平均數。
智豬博弈
智豬：有智慧的豬，哼哼~
智豬博弈是納什理論中的一個經典例子。若一個豬圈里有一頭大豬，還有一頭小豬，在豬圈的一邊有一個投放飼料的豬槽，豬槽旁邊安放著一個可以控制豬槽投食量的按鈕，假設我們按一下這個投食按鈕，豬槽內便會出現 10 個單位的豬食，但是想要按這個按鈕，則需要拿出 2 個單位的豬食作為成本。在此種情況下，
- 假設大豬先走到豬槽邊，它跟小豬的進食量之比為
9:1； - 假設大豬和小豬同時到達豬槽，它們的進食量之比則為
7:3； - 若是小豬先走到豬槽，那么它們的進食量之比則為
6:4。
若是兩頭豬都非常有智慧，那么小豬便會在豬槽邊等待著。
- 若是小豬去按投食開關，大豬在豬槽邊等待，那么大豬小豬的進食量之比為
9:1，這樣計算得出小豬最后的凈收益為吃掉的1個單位減去按開關損失的2個單位（1-2=-1）單位的豬食。 - 即當大豬去按下按鈕時，大豬小豬的進食量之比為
6:4，扣除按開關所需要的2個單位的豬食，大豬最終得到的只有4個單位的豬食； - 若是小豬和大豬同時去按開關，同時到達豬槽，那么它們所獲得豬食的比例為
1:5（減去按開關的成本）。 - 假設兩頭豬不去按開關，那么他們的純收益都將為
0。
而對于博弈中的劣勢方小豬來講，自己去按開關，得到的純收益必定是 -1，但是如果自己不去按開關，一、大豬按開關，得到的純收益為 4。二、大豬也不按開關，兩只豬的純收益都是 0 .由此看來，不論大豬是選擇主動行動還是等待，小豬都選擇等待的收益要高于選擇行動所獲得的利益，這便是小豬在此次博弈中的占優策略。
通常將小豬的這種方法稱為 坐船 或 搭便車 ，暗示人們在博弈中如果占據劣勢，且時間損失不會對最終受益造成影響時，等待也是一種明智之舉。
斗雞博弈
Chicken Game 又名懦夫博弈。假定這樣一種情景：狹路相逢，
- 一方后退、另一方前進，稱前進一方勝利；
- 兩方都后退，則稱平局；
- 兩方都前進，則都失敗。
這種博弈思想的價值，私以為在于進一步證明納什均衡原理。在此博弈中，有兩個納什均衡點：A 進 B 退；A 退 B 進。
納什均衡點：其他參與者策略保持不變時，當前參與者的選擇是最優的，這樣就組成了一個混合收益最大化的策略組。
獵鹿博弈
最早出現在盧梭的《論人類不平等的起源和基礎》一書中，又名安全博弈、協調博弈。
獵鹿博弈源于一則故事：在一個村莊中有兩個獵人，這個村莊主要有兩種獵物：鹿和兔子。一個獵人只能捕捉到 4 只兔子，如果兩個獵人合作就能捕到 1 只鹿。而站在填飽肚子的角度看，捕到 4 只兔子能夠成為 4 天的食物，但是 1 只鹿足以讓兩個獵人在 10 天內都不用外出捕獵。
由此一來，這兩個獵人的行動策略就會產生兩個納什均衡點，即：
- 兩個獵人單獨行動，每個人獲得4只兔子，并且每人能夠吃飽4天；
- 或者兩個獵人建立合作，那么每個人可以吃飽10天。
雖然兩個獵人合作可以獲得的收益遠超單獨行動的收益。但是這要求兩個獵人在合作過程中，個人能力和付出是相等的。（能力不等的情況下大家都是理性人，當然會要求付出多的收獲占比多啦。）
蜈蚣博弈
蜈蚣博弈的提出者是羅森塞爾，它指參加博弈的 A 和 B ，分別有 合作、背叛 兩種策略可供選擇。規則是 A 先進行選擇，再由 B 做出選擇，再輪 A 做出選擇……
舉個例子，如果雙方需要博弈十輪：
網上的資料中沒有對收益結果進行解釋，所以我一直對最后一次不合作的結果是 （8，11）而不是（9，11）而感到困惑，我個人分析收益是這樣計算的：
- 根據第一輪
A就不合作雙方的收益仍是（1，1）可以推測博弈開始前，雙方手里就各有一個籌碼。 - 根據第一輪
A合作、B 不合作雙方的收益是（0，3），會發現A手里的一個籌碼沒了，但B多了兩個籌碼。
因此合作的前提可能是 A、B 都拿出來一個籌碼，如果雙方選擇合作則都收獲一個籌碼，之前拿出來的籌碼也可以收回；如果 A 選擇背叛則 B 不需要拿出來籌碼，博弈結束；如果 B 選擇背叛則 A 失去它拿出來的籌碼，B 自己獲得兩個籌碼。
如果一直合作，那么最終總體收益可達最大值 20 ，但根據理性人原則，B 會在最后一輪博弈中選擇背叛，以拿到 11 的收益，大于選擇合作的 10 收益。那么 A 亦會在 B 選擇背叛前先背叛，那么它就能拿到 9 收益，大于 B 背叛時的 8 收益……以此類推，得到的答案是 A 會在剛開始就選擇不合作，那么 A 和 B 所獲得的最終收益是 1 。
蜈蚣博弈的悖論
不難看出，在上面的推理過程中，運用的是逆推法。從邏輯推理來看，逆推法是嚴密的，但結論是不合理的。雖然 A 一開始采取合作性策略有可能獲得 0 ，但 1 或者 0 與 10 相比實在是很小。直覺告訴我們采取 合作 策略是好的。而從邏輯的角度看，A一開始應選擇 不合作 的策略。人們在博弈中的真實行動偏離了運用逆推法關于博弈的理論預測，造成二者間的矛盾和不一致。
酒吧博弈
假設有 100 個人都喜歡去酒吧消遣娛樂，若我們設定酒吧的座位數是 60，那么想要去酒吧的人便會有兩種決策：一種是不去，待在家中，另外一種是去。假設所有的人都去酒吧，那么去酒吧的人就會感到不舒服，而這時他們會覺得待在家中要比去酒吧更好。那么，這 100 個喜歡去酒吧的人最終將會做何選擇呢？
其實這些喜歡去酒吧的人，往往會受上一次酒吧人數的影響，進而產生一些人數上的浮動，久而久之便會形成一種持續性波動的情況。這是由切斯特·艾倫·阿瑟博士提出的，他的理論如下：
- 假設每個想要去酒吧的人都是理性的，那么酒吧每天接待的人數幾乎不會有過大的浮動。就會產生 神奇的 60% 客滿率定理 ，即當人們選擇去酒吧時，最初的觀察結果并未找到任何規律，但是通過長時間的觀察發現，每次去酒吧的人數和不去酒吧的人數之比接近
60:40。 - 但是人并不總能保持理性，當人們在第一次去酒吧時，若發現酒吧人數非常多，那么這種現象會成為他們下次選擇的一個參考，他們會認為酒吧人數太多、十分擁擠、喧鬧，大部分下次就不來了，但是少數人可能會選擇下次依然去酒吧，這時他們發現酒吧的人數并不多，然后便會在下一次叫上自己的朋友一起去酒吧，由此一來循環便正式開始了。
從心理學的角度來看，最初去酒吧的那些人可能互相不熟悉，但是由于經常去酒吧而且能夠遇見對方，久而久之便會由陌生人變成朋友，那么在這種情況下，便會由零散的個體變成一個大的群體，而這個整體中又會分支出小團體，而且這些小團體中的人，有一部分會占據主導地位，另一部分人會處在服從地位。這就意味著團體中的每個人的決策都會受到他人的影響。
槍手博弈
槍手博弈是指，槍手甲乙丙三人相互怨恨，以決斗的形式進行一場博弈。其中，甲的槍法最準，命中率 80%。乙的槍法在甲之下，命中率 60%。丙的槍法最差，命中率 40%。假設在三人都了解彼此實力并能理性判斷的情況下，會出現以下兩種情況：
- 三人同時開槍，誰活下來的可能最大？
- 若由丙開第一槍，隨后輪流開槍，他會如何選擇？
第一種情況：
- 第一輪：
- 甲：最佳的策略是先對準乙，因為乙的槍法比丙好。
- 乙：最佳的策略是先對準甲，因為三人中甲的槍法最準，這樣，在乙丙兩人中，乙活下來的概率更大。
- 丙：同樣也會先解決槍法最準的甲，干掉甲后再考慮如何應對乙。
現在我們可以分別計算三人活下來的概率：
- 甲活：即乙和丙都未命中。兩人都射偏的概率為：
40%×60%，所以甲活下來的概率為24%。 - 乙活：即甲射偏。甲有
20%的未命中率，就相當于乙的存活率為20%。 - 丙活：根據上面的分析，在這一種情況下，沒有任何人對準丙，因此丙的存活概率為
100%。
由此我們可以看到，在這一輪的決斗中，丙槍法最差但活下來的概率卻最大。而甲和乙的槍法都遠大于丙，存活率卻都比丙低。
- 第二輪：
第一輪過后，有三種情況：
- 若甲乙中有一方打偏，那么丙會面對甲或乙；
- 若都打偏，那丙將同時面對甲乙兩人；
- 甲乙都命中，甲乙皆死。
現在我們可以分別計算三人活下來的概率：
- 如果丙只面對甲或乙，那丙的存活率最低。
- 如果同時面對甲乙兩人，則返回第一輪的場景。
- 如果甲乙皆死，那么無疑丙最終存活。
第二種情況：
由丙先開第一槍，那么可能如下：
- 丙射中甲：乙與丙對決，且只能由乙先開槍，丙會處于不利位置。
- 丙射中乙：同上，甲的命中率最高，丙的處境會更糟。
- 丙都未射中的話：甲乙都不會選擇先射擊丙，而是會在甲乙雙方之間一決勝負，直至其中一人死亡，而這時就會又輪到丙。可以這樣說，只要丙誰都不打中，在接下來的對決中他就處于相對而言最有利的位置。
我們會發現，優勢最小的丙，反而可能是不是最先死掉的，因此，在多方非合作博弈中，優勢最小的往往可以在暫時安全的環境下，抓緊機會提升自己。當然，如果不能在暫時安全的環境下提升能力的話，當面對雙人非合作博弈時，難免處于失敗者的位置。簡言之，實力最差的并不一定是輸的最快的，但終究是需要提升自我的，否則即使能安全一時、但仍然難免落入敗局。
警匪博弈
在某個小鎮上只有一名警察，整個小鎮的治安全部由他負責。此時，我們假設這個小鎮上的一頭有一家銀行，存了 2 萬元；而小鎮的另一頭有一個酒館，存了 1 萬元。若這個小鎮上還有一名小偷，當這個小鎮上的警察在小鎮的一頭巡視時，小偷只能去小鎮的另一頭進行偷盜。
假想一下，當小鎮的警察正好在小偷采取行動的地方巡視，便能不費吹灰之力地抓住小偷；若是小鎮的警察的巡視方向恰好與小偷采取偷盜行為的方向相反，那么小偷便能在不被警察抓到的情況下成功偷盜。那么如何才能將小鎮的損失降到最低呢？
警察最好的做法是利用抽簽的方式決定去小鎮的銀行還是酒店。由于小鎮銀行中所需保護的財產是酒館的兩倍，因此用 1、2 號兩個簽表示小鎮的銀行，用 3 號簽表示酒館，這樣一來，警察去銀行巡視的機會將達到 2/3，而去酒館巡視的機會將是 1/3。
在小鎮警察的此種策略下，小偷的占優策略則要與警察相反，同樣采用抽簽的方式，與警察不同的是小偷用 1、2 號簽表示去酒館行動，而用 3 號簽表示去銀行，由此一來，小偷去酒館行動的概率是 2/3，而去銀行的概率僅有 1/3。
如果雙方都選擇最佳占優策略的話，警察和小偷的成功率是相等的（過程有些繁瑣，可選擇跳過），分析如下：
如果警察和小偷都是理性人的話，警察可以猜到小偷的概率，小偷也可以猜到警察的概率。
- 雙方如果單純都是第一層的話，警察成功概率
2/3*1/3+1/3*2/3=4/9，小偷成功概率1-4/9=5/9； - 但是如果警察在第二層（警察反概率行動），小偷在第一層，警察成功概率
1/3*1/3+2/3*2/3=5/9，小偷成功概率1-5/9=4/9； - 警察在第一層，小偷在第二層，那么和上一個情況一樣，警察成功概率
5/9，小偷成功概率4/9； - 雙方都是第二層（都以相反概率行動），警察成功概率
4/9，小偷5/9。
最后相加綜合期望，雙方成功概率都為 1/2。（這波啊，這波疊加就是千層餅~）
而如果警察和小偷扔硬幣去決定守、偷哪出地點。這樣就模糊了自己策略的傾向性，結果就具有偶然性。博弈取勝的要點在于運用其中的偶然性，針對對方是否發現你的某些策略性行為做出及時應對，進而保證自己成功的概率。總結來講還是說明信息在博弈中的重要性。
海盜分金
有五個海盜（記為1、2、3、4、5號）掠得 10 枚金幣，決定以抽簽的方式依次提出分金方案，并由五人共同表決。要想通過方案，必須有超半數的人同意才可以，否則這個人將會被扔進大海。
與其從前往后一個一個地想每個人會怎樣選擇，不如先把問題簡單化，若只剩下最后兩人的話，他們會怎么做呢？
- 倒推來看，若
1、2、3號都被投入海中，那么5號必定反對4號把一百枚金幣全部收入囊中。因此4號只有同意3號的方案才有可能保命。 - 3號猜到這一點，就會采取
（100、0、0）的分金方案，因為他清楚地知道即便4號一枚金幣也分不到，也仍然會同意他的方案。 2號猜到3號的策略，就會采取（98、0、1、1）的方案，因為2號只要稍微照顧到4、5號的利益，4、5號就會向他投贊成票，而不希望2號出局讓3號分配。1號同樣猜到2號的意圖，就會采取（97、0、1、2、0）或者（97、0、1、0、2）的方案。對于1號來說，只要放棄2號，再分給3號一枚金幣，給4號或5號兩枚金幣。
巴什博弈
巴什博弈： 一堆物品有 n 個，兩個人輪流從這堆物品中取物，規定每次至少取一個，最多取 m 個。最后取光者得勝。
巴什博弈是一種 動態、完全信息博弈 ，即局中人的行動有先后順序，且后做出選擇的人知道先做出選擇之人的行動。
如果一方拿取時，還剩 m+1 個，那便是 必敗局，因為此時不論你拿走多少個，下次對方一定可以全部拿完。
其他情況則是 必勝局 。因為如果還剩 m+1+k 個（0 < k <= m），我只要拿走 k 個，那么對方就面臨 m+1 個。可能有人在想 0 > k > -m 怎么辦？沒什么多說的，還是必勝局，我直接拿走剩下的全部。
擴展：如果 n = x(m+1) ，先拿的依然面對必敗局，先拿的拿 p 個，后拿的拿 m+1-p 個，先拿的第二輪拿的時候，還剩 x-1(m+1) ，重復 x-2 輪，先拿的又面對 m+1 了。
反之，如果 n=x(m+1)+k ，先拿的面對必勝局，先拿的拿走 k 個，則后拿的面對 x(m+1) ，重復上一段的過程。
因此，可以得到代碼：
#include<iostream>
using namespace std;
int main()
{int n, m;cin >> n >> m;if (n % (m + 1) == 0)cout << "second win" << endl;else cout << "first win" << endl;return 0;
}
