大家早安、午安脾拆、晚安馒索，今天我先從機器學習的學習中休息一下，來了解一些常見的博弈論模型名船，然后繼續(xù)學習機器學習等绰上。以下博弈論的介紹來自網(wǎng)絡。

1渠驼、博弈論概念

博弈論(Game Theory)蜈块，博弈論是指研究多個個體或團隊之間在特定條件制約下的對局中利用相關方的策略，而實施對應策略的學科迷扇。有時也稱為對策論百揭，或者賽局理論，是研究具有斗爭或競爭性質現(xiàn)象的理論和方法蜓席，它是應用數(shù)學的一個分支器一，既是現(xiàn)代數(shù)學的一個新分支，也是運籌學的一個重要學科厨内。目前在生物學祈秕、經(jīng)濟學、國際關系學雏胃、計算機科學请毛、政治學、軍事戰(zhàn)略和其他很多學科都有廣泛的應用丑掺。主要研究公式化了的激勵結構（游戲或者博弈（Game））間的相互作用获印。

2述雾、博弈論分類

圖1

3街州、部分博弈論術語解釋

1）合作博弈和非合作博弈

合作博弈和非合作博弈的區(qū)別在于相互發(fā)生作用的當事人之間有沒有一個具有約束力的協(xié)議，如果有玻孟，就是合作博弈唆缴，如果沒有，就是非合作博弈黍翎。

2）靜態(tài)博弈和動態(tài)博弈

從決策行為的時間序列來看面徽，博弈可以分為靜態(tài)博弈和動態(tài)博弈。靜態(tài)博弈是指在博弈中，參與人同時選擇或雖非同時選擇但后行動者并不知道先行動者采取了什么具體行動趟紊；動態(tài)博弈是指在博弈中氮双，參與人的行動有先后順序，且后行動者能夠觀察到先行動者所選擇的行動霎匈。通俗的理解："囚徒困境"就是同時決策的戴差，屬于靜態(tài)博弈；而棋牌類游戲等決策或行動有先后次序的铛嘱，屬于動態(tài)博弈暖释。

3）完全信息博弈和不完全信息博弈

按照參與人對其他參與人的了解程度分為完全信息博弈和不完全信息博弈。完全信息博弈是指在博弈過程中墨吓，每一位參與人對其他參與人的特征球匕、策略空間及收益函數(shù)(也叫支付)有準確的信息。不完全信息博弈是指如果參與人對其他參與人的特征帖烘、策略空間及收益函數(shù)信息了解的不夠準確亮曹、或者不是對所有參與人的特征、策略空間及收益函數(shù)都有準確的信息秘症，在這種情況下進行的博弈就是不完全信息博弈乾忱。

此外，非合作博弈又分為：完全信息靜態(tài)博弈历极，完全信息動態(tài)博弈窄瘟，不完全信息靜態(tài)博弈，不完全信息動態(tài)博弈趟卸。與上述四種博弈相對應的均衡概念為：納什均衡(Nash equilibrium)蹄葱，子博弈精煉納什均衡（subgame perfect Nash equilibrium），貝葉斯納什均衡(Bayesian Nash equilibrium)锄列，精煉貝葉斯納什均衡(perfect Bayesian Nash equilibrium)图云。其中，博弈中涉及的‘均衡’的概念邻邮，指的是一種相關量處于穩(wěn)定值竣况。

4）納什均衡(Nash Equilibrium)

在一策略組合中，所有的參與者面臨這樣一種情況筒严，當其他人不改變策略時丹泉，他此時的策略是最好的。也就是說鸭蛙，此時如果他改變策略他的支付將會降低摹恨。在納什均衡點上，每一個理性的參與者都不會有單獨改變策略的沖動娶视。納什均衡點存在性證明的前提是“博弈均衡偶”概念的提出晒哄。所謂“均衡偶”是在二人零和博弈中睁宰，當局中人A采取其最優(yōu)策略a*,局中人B也采取其最優(yōu)策略b*,如果局中人B仍采取b*,而局中人A卻采取另一種策略a，那么局中人A的支付不會超過他采取原來的策略a*的支付寝凌。這一結果對局中人B亦是如此柒傻。

5）均衡偶

一對策略a*(屬于策略集A)和策略b*（屬于策略集B）稱之為均衡偶，對任一策略a(屬于策略集A)和策略b（屬于策略集B）较木，總有：偶對（a, b*）≤偶對(a*,b*)≥偶對（a*诅愚，b）

6）納什定理

任何具有有限純策略的二人博弈至少有一個均衡偶。這一均衡偶就稱為納什均衡點劫映。但納什均衡點定義只局限于任何局中人不想單方面變換策略违孝，而忽視了其他局中人改變策略的可能性，因此泳赋，在很多情況下雌桑，納什均衡點的結論缺乏說服力，研究者們形象地稱之為“天真可愛的納什均衡點”祖今。

4校坑、部分具有代表性的博弈模型

1）智豬博弈/完全信息靜態(tài)博弈(Boxed pigs Game)

智豬博弈是納什提出的，假設豬圈里有一頭大豬千诬、一頭小豬耍目。豬圈的一頭有豬食槽，另一頭安裝著控制豬食供應的按鈕徐绑，按一下按鈕會有10個單位的豬食進槽邪驮，但是誰按按鈕就會首先付出2個單位的成本，若大豬先到槽邊傲茄，大小豬吃到食物的收益比是9∶1毅访；同時到槽邊，收益比是7∶3盘榨；小豬先到槽邊喻粹，收益比是6∶4。

圖2 智豬博弈

在這個過程中草巡，小豬有占優(yōu)策略守呜，大豬木有，小豬等待對它自己是最優(yōu)的山憨。

2）囚徒困境/非合作博弈（完全信息的靜態(tài)博弈查乒、納什均衡）

1950年，由就職于蘭德公司的梅里爾·弗勒德（Merrill Flood）和梅爾文·德雷希爾（Melvin Dresher）擬定出相關困境的理論萍歉，后來由顧問艾伯特·塔克（AlbertTucker）以囚徒方式闡述侣颂，并命名為“囚徒困境”。經(jīng)典的囚徒困境如下：警方逮捕甲枪孩、乙兩名嫌疑犯，但沒有足夠證據(jù)指控二人入罪。于是警方分開囚禁嫌疑犯蔑舞，分別和二人見面拒担，并向雙方提供以下相同的選擇：若一人認罪并作證檢控對方（相關術語稱“背叛”對方），而對方保持沉默攻询，此人將即時獲釋从撼，沉默者將判監(jiān)10年。若二人都保持沉默（相關術語稱互相“合作”）钧栖，則二人同樣判監(jiān)1年低零。若二人都互相檢舉（相關術語稱互相“背叛”），則二人同樣判監(jiān)8年拯杠。

圖3 囚徒困境

囚徒到底應該選擇哪一項策略掏婶，才能將自己個人的刑期縮至最短？兩名囚徒由于隔絕監(jiān)禁潭陪，并不知道對方選擇雄妥；而即使他們能交談，還是未必能夠盡信對方不會反口依溯。就個人的理性選擇而言老厌，檢舉背叛對方所得刑期，總比沉默要來得低黎炉。試設想困境中兩名理性囚徒會如何作出選擇：若對方沉默時枝秤，背叛會讓我獲釋，所以會選擇背叛慷嗜；若對方背叛指控我宿百，我也要指控對方才能得到較低的刑期，所以也是會選擇背叛洪添。二人面對的情況一樣垦页，所以二人的理性思考都會得出相同的結論——選擇背叛。背叛是兩種策略之中的支配性策略干奢。因此痊焊，這場博弈中唯一可能達到的納什均衡，就是雙方參與者都背叛對方忿峻，結果二人同樣服刑8年薄啥。

3）海薩尼轉換(the Harsanyi transformation，將不完全信息靜態(tài)博弈轉換為完全但不完美的靜態(tài)博弈逛尚、貝葉斯納什均衡)

人的支付函數(shù)類型是不清楚的掸犬。如果一些局中人不知道另一些局中人的支付函數(shù)，或支付函數(shù)不是共同知識顽爹，局中人就不知道他在與誰博弈，博弈的規(guī)則是沒有定義的铣口。因而在1967年以前，博弈論專家認為此時博弈的結構特征是不確定的觉壶，無法進行分析脑题。海薩尼提出了一種處理不完全信息博弈的方法，即引入一個虛擬的局中人——“自然”铜靶。自然首先行動叔遂，它決定每個局中人的特征。每個局中人知道自己的特征争剿，但不知道別的局中人特征已艰。這種方法將不完全信息靜態(tài)博弈變成一個兩階段動態(tài)博弈，第一個階段是自然N的行動選擇蚕苇，第二階段是除N外的局中人的靜態(tài)博弈哩掺。這種轉換被稱為“海薩尼轉換”，這個轉換把“不完全信息”轉變成為完全但不完美信息捆蜀，從而可以用分析完全信息博弈的方法進行分析疮丛。“不完美信息”指的是辆它，“自然”作出了它的選擇誊薄，但其他參與人并不知道它的具體選擇是什么，僅知道各種選擇的概率分布锰茉。

在上述轉換的基礎上呢蔫，海薩尼提出了貝葉斯納什均衡(Bayesian Nash equilibrium)。對此飒筑，可以作如下解釋：在不完全信息靜態(tài)博弈中片吊，參與人同時行動，沒有機會觀察到別人的選擇协屡。給定其他參與人的戰(zhàn)略選擇俏脊，每個參與人的最優(yōu)戰(zhàn)略依賴于自己的類型。由于每個參與人僅知道其他參與人有關類型的分布概率肤晓，而不知道其真實類型爷贫，因而，他不可能知道其他參與人實際上會選擇什么戰(zhàn)略补憾。但是漫萄，他能夠正確地預測到其他參與人的選擇與其各自的有關類型之間的關系。因此盈匾，該參與人的決策目標就是：在給定自己的類型腾务，以及給定其他參與人的類型與戰(zhàn)略選擇之間關系的條件下，使得自己的期望效用最大化削饵。貝葉斯納什均衡是一種類型依賴型戰(zhàn)略組合岩瘦。在給定自己的類型和其他參與人類型的分布概率的條件下未巫，這種戰(zhàn)略組合使得每個參與人的期望效用達到了最大化。

4）Stackelberg競爭(雙寡頭模型担钮，完全且完美動態(tài)信息博弈)

Stackelberg leadership model是經(jīng)濟學中雙寡頭模型之一橱赠。它以德國經(jīng)濟學家Heinrich von Stackelberg的名字命名尤仍，在1934年出版的 "Marktform und Gleichgewicht" 中被闡述箫津。用博弈論的語言說，這個博弈的兩個參與者分別是leader和follower宰啦，它們進行的是數(shù)量競爭苏遥。leader先行選擇產(chǎn)量，follower觀察到leader的選擇后再作選擇赡模。舉栗子：某個地域田炭，A本來處于壟斷地位，利潤是10億漓柑，然后B是創(chuàng)業(yè)公司教硫，想進入該市場，這期間可能的雙方的利潤變化如下：

圖4 博弈樹-利潤分布

圖5?

在圖5中辆布，B采用的是倒推法（逆推法）瞬矩，不難發(fā)現(xiàn)，在圖4中存在兩個納什均衡點：B不進入(A為10锋玲，B為0)景用、B進入且A不阻攔(AB均為4)。但是依據(jù)圖5的分析惭蹂，A最理智的行為是不阻撓伞插，辣么，因為A的威脅是不可置信的盾碗，針對這一的現(xiàn)象媚污，澤爾騰引入了子博弈完美納什均衡的概念，目的就是將這些不可置信威脅戰(zhàn)略的納什均衡從均衡中剔除廷雅，比如去掉‘B不進入(A為10耗美，B為0)’這樣的均衡點。子博弈完美納什均衡要求均衡戰(zhàn)略的行為規(guī)則在每一個信息集上是最優(yōu)的榜轿，也就是要去掉那些不可置信的威脅幽歼。

5）信號博弈(不完全信息的動態(tài)博弈、子精煉納什均衡)

信號博弈是一種由一個發(fā)送者（S）和另一個接收者（R）所組成的非完全信息的動態(tài)博弈谬盐。一開始這個發(fā)送者有一個給定的類型（t）甸私，接著發(fā)送者會觀察這個沒有其他人（好比說接收者）知道的類型，去從訊息堆 M = {m1, m2, m3,..., mj} 中選擇送出一個訊息（m）飞傀，接著接收者會觀察這個訊息后從他可行的動作中 A = {a1, a2, a3,...., ak} 選一個作為反應動作（a）皇型，這里要注意的是接收者除了訊息之外其他都無法得知（如發(fā)送者的類型t）诬烹，接著根據(jù)（t, m, a）的組合來決定雙方會獲得的報酬或回報。這類型的博弈比如公交車上的小偷與乘客之間的博弈弃鸦。小偷向乘客釋放了誰反抗就毆打誰的信號绞吁，而乘客覺得小偷的信號是可信的，可能會議如下的幾種情況：

圖6

根據(jù)圖6中的情況發(fā)現(xiàn)唬格，對于乘客來說家破，小偷的威脅是可信的，因此购岗，不反抗是最優(yōu)的策略汰聋；對于小偷來說，乘客的不反抗下的不毆打策略最優(yōu)喊积。這一博弈的結果直接導致出現(xiàn)了不良的社會風氣烹困，縱容了小偷的違法行為。這就是一種信號博弈乾吻。

其實髓梅，在這個栗子中，如果我們能夠提高乘客反抗時可能獲取的利益绎签，比如反抗會讓乘客獲得道德滿足枯饿，辣么，這個不好的事情就會變得有轉機辜御，比如可能會獲得如圖7所示的博弈樹：

圖7?

在圖7中鸭你，因為出現(xiàn)了道德這樣的信念，那么乘客結合自己的道德觀擒权，再次進行不一樣的取舍袱巨，‘乘客反抗、小偷被打’出現(xiàn)的可能性更大碳抄。此時愉老，這樣的決策稱為精煉貝葉斯均衡（也叫精煉貝葉斯納什均衡）。沒懂剖效，那我借用知乎以為大牛的科普版解釋：

圖8 精煉貝葉斯均衡

舉栗子說明一下：

圖9 精煉貝葉斯均衡

6）重復博弈（Repeated Games）

其實嫉入，通俗來說，如果是一錘子買賣璧尸，辣么咒林，大家都無所顧忌了，肯定是盡可能的謀求自己利益最大化爷光，不惜欺騙等垫竞；但是，如果是來日方長的這種交易，辣么欢瞪，大家在博弈中活烙，就會有所顧忌，可能是薄利多銷這種方式了遣鼓，保證讓大家繼續(xù)合作下去啸盏。

重復博弈是指同樣結構的博弈重復許多次，其中的每次博弈稱為“階段博弈”（stage games）骑祟。重復博弈是動態(tài)博弈中的重要內容回懦，它可以是完全信息的重復博弈，也可以是不完全信息的重復博弈曾我。在重復博弈中粉怕，每次博弈的條件健民、規(guī)則和內容都是相同的, 但由于有一個長期利益的存在, 因此各博弈方在當前階段的博弈中要考慮到不能引起其它博弈方在后面階段的對抗抒巢、報復或惡性競爭, 即不能象在一次性靜態(tài)博弈中那樣毫不顧及其它博弈方的利益。有時, 一方做出一種合作的姿態(tài), 可能使其它博弈方在今后階段采取合作的態(tài)度, 從而實現(xiàn)共同的長期利益秉犹。

以下我們用一個產(chǎn)品定價的例子討論重復博弈蛉谜，給出了一次性完全信息靜態(tài)博弈的收益矩陣。

A崇堵、B兩個參與人都有兩種定價待選擇：定高價或定低價型诚。如果兩個參與人都定低價，則每個參與人的收益均為20個單位鸳劳；如果兩人都定高價狰贯，則每人的收益均為30個單位；如果其中某一參與人定低價赏廓，而另一參與人定高價涵紊，則定低價的參與人有占有更多的市場份額獲得40個單位的收益，定高價的參與人由于失去一部分市場份額而只獲得10個單位的收益幔摸。顯然摸柄，在這個一次性完全信息靜態(tài)博弈中，兩個參與人均有占優(yōu)策略既忆，占優(yōu)策略均衡為A驱负、B雙方都定低價。

如果A患雇、B之間的定價博弈是多次進行的跃脊，那么，問題就不是如此簡單了苛吱。我們先來分析博弈重復次數(shù)為無限時的情況酪术。

如果A、B雙方都選擇合作又谋，都保持定高價拼缝，則雙方在每個階段的收益均為30個單位娱局，記為(30，30咧七，30衰齐，…)；如果A继阻、B中有一方(如A)采取投機行為耻涛，在實際定價中選擇不與對方合作，在第一階段就通過選擇定價策略使得選擇高價策略的對手B受損瘟檩，則受損的一方B一定會在第二階段及其以后的定價中也選擇低價策略抹缕，加以報復，這樣一來墨辛，首先選擇不合作的一方A在個階段的收益為(40卓研，20，20睹簇，…)奏赘，顯然，其總收益遠遠小于合作太惠、維持高價情況下的總收益磨淌。因為，首選選擇不合作的一方A凿渊，只是在第一階段獲得了“額外”收益梁只，但在以后個階段的收益將因為對手B的報復性選擇而減少，并且埃脏，重復若干此后搪锣，首先選擇不合作的一方A將得不償失。

在這里剂癌，B選擇的策略稱為“冷酷策略”(grim strategies)淤翔。冷酷策略是指重復博弈中的任何參與人的一次性不合作將引起其他參與人的永遠不合作，從而導致所有參與人的收益減少佩谷。因此旁壮，所有參與人具有維持合作的積極性。我們再來討論博弈重復次數(shù)為有限時的情況谐檀。

重復次數(shù)有限博弈與重復次數(shù)無限博弈之間的惟一區(qū)別抡谐，是所有參與人都可以明確無誤地了解重復的次數(shù)，即可以準確地預測到最后一個階段博弈桐猬。而在最后階段的博弈中麦撵，任何一個參與人選擇不合作，不會導致其他參與人的報復。因此免胃，所有參與人都會在最后階段的博弈中選擇自己的占優(yōu)策略音五，那就是不合作。上例中羔沙，在最后階段博弈中選擇低價是所有參與人的占優(yōu)策略躺涝。

既然所有參與人都會在最后階段選擇不合作，那么扼雏，在倒數(shù)第二階段博弈中任何參與人也就沒有必要擔心由于自己選擇不合作坚嗜，導致其他參與人在最后階段博弈中的報復。因此所有參與人在倒數(shù)第二階段博弈中诗充，也都會選擇不合作苍蔬。即在倒數(shù)第二階段博弈中，所有參與人都會選擇占優(yōu)策略蝴蜓。

由此類推碟绑，可以得出以下結論：在階段性博弈存在惟一的納什均衡時，階段博弈的納什均衡解就是重復次數(shù)有限博弈的唯一子博弈精煉納什均衡解励翼。即重復次數(shù)有限博弈的每個階段的均衡解都是一次性博弈的納什均衡解蜈敢。注意，上述推論成立的前提條件是階段性博弈納什均衡的惟一性汽抚。

7)合作博弈（財產(chǎn)分配、Shapley值）

合作博弈與非合作博弈想對稱伯病，是一種參與者能夠聯(lián)合達成一個具有約束力且可強制執(zhí)行的協(xié)議的博弈類型造烁。合作博弈強調的是集體理性，其最重要的兩個概念是‘聯(lián)盟’和‘分配’午笛。每個參與者從聯(lián)盟中分配的收益正好是各種聯(lián)盟形式的最大總收益惭蟋，每個參與者從聯(lián)盟中分配到的收益不小于單獨經(jīng)營所得收益。具體關于合作博弈的內容药磺，請參考合作博弈

Shapley值（夏普里值）告组？據(jù)說，如果說納什均衡是非合作博弈的核心的話癌佩，Shapley值就是合作博弈的核心木缝，這么重要？Ｎд蕖我碟！

考慮這樣一個聯(lián)盟博弈：有一個三人財產(chǎn)分配問題：假定財產(chǎn)為100萬元，這100萬在三人之間進行分配姚建。a擁有50%的決定權矫俺，b擁有40%的決定權，c擁有10%的決定權。規(guī)定厘托，當超過50%的同意時友雳，才能獲得整個財產(chǎn)，否則三人將一無所獲铅匹。辣么沥阱，咋辦哩

圖10 Shapley值

那么，如何計算邊際貢獻呢伊群，夏普里給出了這樣的計算形式：

圖11 夏普里值的計算

根據(jù)夏普里值定義考杉，所有排列的順序是等可能的。而在每一個排列下舰始，每個參與者對這個排列的聯(lián)盟有一個邊際貢獻崇棠。在投票博弈中，這個值反映的是參與者與其他參與者結成聯(lián)盟的可能性丸卷，因此夏普里值反映的是參與者的權利枕稀。

博弈論初步知識先到這里，本次只是簡單講網(wǎng)絡知識收集匯總谜嫉，希望能幫點小忙哈~~