博弈論（Game Theory）入門學習筆記

課程介紹

• 博弈論,又稱對策論,是使用嚴謹的數學模型研究沖突對抗條件下最優決策問題的理論,是研究競爭的邏輯和規律的數學分支，

1-1 Taste-Backoff

• 以一個經典案例引出博弈論
• TCP Backoff Game
  兩臺電腦之間想要實作通信，兩種方式可供選擇，建立回退機制以及不建立回退機制，如果AB雙方均建立回退機制，則雙方延遲都是1，如果A、B一方建立回退機制，另一方不建立，那么建立的一方延遲是4，不建立的一方延遲是0，如果雙方都不建立回退機制，則雙方延遲都是3，
  
• 該問題的結果有一特點，即自己做出決策的收益不僅跟自己的決策有關，還跟對方的決策有關，因此存在一種“博弈”競爭關系，

1-2 Self-Interested Agents and Utility Theory

• Self-Interested Agents：利己代理
  并不是說決策者只考慮自己或者傷害他人，而是指決策者對于世界狀態有自己的獨特看法，并且根據自己的判斷理解做出決策，
• Utility Theory ：效用理論
  每個決策者都有自己的效用函式，表達了決策者對于決策的偏好，決策者做出決策都是為了最大化效用期望，

1-3 Define

• Key Ingredients 關鍵組成
  Players：決策者，執行決策的人，
  Actions：動作，決策者可以做的事情，
  Payoffs：回報，激勵決策者的東西，決策帶來的回報，

• Two Standard Representations 兩種標準表達方式
  Normal Form：分別定義Players、Actions、Payoffs，
  Extensive Form：擴展定義Timing、Information，

• 簡單的博弈論問題可以使用矩陣表達，如1-1所示，

• 復雜問題無法用矩陣表達，如經典的造反問題，共有10000000個人，每個人可以選擇造反或者不造反，只有達到2000000個人才算造反成功，如果造反達到人數要求，無論決策者選擇什么收益都是1；如果造反沒有達到人數要求，則決策者選擇造反的收益是-1；如果造反沒有達到人數要求，則決策者選擇不造反的收益是0，
  Players： N = { 1 , . . . , 10 , 000 , 000 } N=\{1,...,10,000,000\} N={1,...,10,000,000}
  Actions Set for player i i i： A i = { R e v o l t , N o t } A_i=\{Revolt,Not\} Ai?={Revolt,Not}
  Utility Function for player i i i：
  （1） u i ( a i ) = 1 i f { j : a j = R e v o l t } > = 2 , 000 , 000 u_i(a_i)=1 \space if \{j:a_j=Revolt\}>=2,000,000 ui?(ai?)=1 if{j:aj?=Revolt}>=2,000,000
  （2） u i ( a i ) = ? 1 i f { j : a j = R e v o l t } < 2 , 000 , 000 a n d a i = R e v o l t u_i(a_i)=-1 \space if \{j:a_j=Revolt\}<2,000,000 \space and \space a_i=Revolt ui?(ai?)=?1 if{j:aj?=Revolt}<2,000,000 and ai?=Revolt
  （3） u i ( a i ) = ? 0 i f { j : a j = R e v o l t } < 2 , 000 , 000 a n d a i = N o t u_i(a_i)=-0 \space if \{j:a_j=Revolt\}<2,000,000 \space and \space a_i=Not ui?(ai?)=?0 if{j:aj?=Revolt}<2,000,000 and ai?=Not

1-4 Examples

• 囚徒困境 Prisoner’s dilemma，故事背景：兩個共謀犯罪的人被關入監獄，不能互相溝通情況，如果兩個人都不揭發對方，則由于證據不確定，每個人都坐牢一年；若一人揭發，而另一人沉默，則揭發者因為立功而立即獲釋，沉默者因不合作而入獄十年；若互相揭發，則因證據確鑿，二者都判刑八年，由于囚徒無法信任對方，因此傾向于互相揭發，而不是同守沉默，
  結果的優劣程度按照A>B>C>D排序，
  

• Game of Pure Competition 純競爭博弈
  博弈的雙方具有完全對立的利益，
  對于雙方任意動作組合，其效用之和永遠為一個常數， ? a ∈ A , u 1 ( a ) + u 2 ( a ) = c \forall \space a \in A,u_1(a)+u_2(a)=c ? a∈A,u1?(a)+u2?(a)=c
  特殊型別：零和博弈，雙方效用之和永遠為0，
  舉例說明：石頭剪刀布游戲，
  

• Games of Cooperation 合作博弈
  博弈的多方具有相同的利益，利益之間不存在沖突， ? a ∈ A , ? i , j , u i ( a ) = u j ( a ) \forall a\in A,\forall i,j,u_i(a)=u_j(a) ?a∈A,?i,j,ui?(a)=uj?(a)
  舉例說明：過馬路問題，馬路兩頭兩個人想同時通行，每個人可以選擇靠左或者靠右行駛，
  

1-5 Nash Equilibrium Intro

• Keynes Beauty Contest Game：凱恩斯選美博弈
  舉辦選美大賽，從1-100號候選者中選擇自己認為最美的一位，獲得票數最多的人獲得選美冠軍，投票給選美冠軍的人也會得到一定的獎勵，這個問題是老千層餅了，第一層的人只是自己覺得誰漂亮就選誰，比如A覺得10號最美投票給了10號；第二層的人考慮其他人的投票分布從而產生自己的決策，比如B覺得可能有很多人投票給30號，雖然自己喜歡10號也投票給30號；第三層的人覺得其他人可能也會因為考慮到第二層的因素，從而放棄自己最喜歡的轉投自己認為最火爆的…這是一個無休止的猜想游戲，
• 猜數字游戲
  每個人從1-100中選擇一個整數，最后最接近平均值三分之二的人獲得獎勵，假設參加這項游戲的人數足夠多，這個問題同樣是一個千層餅問題，
  第一層的人：參賽人數足夠多，我假設大家所選擇的數字均勻分布，那么最后的平均值應該接近于50，那么我為了獲勝應該選擇的數字是 50 ? 2 3 = 33 50*\frac{2}{3}=33 50?32?=33，
  第二層的人：我想大部分人都在第一層，因此他們都選擇33，那么最后的平均值應該接近于33，那么我為了獲勝應該選擇的數字是 33 ? 2 3 = 22 33*\frac{2}{3}=22 33?32?=22，
  第三層的人： 22 ? 2 3 = 11 22*\frac{2}{3}=11 22?32?=11，
  …
  第n層的人：應該選擇的數是0，這就得到了納什均衡，
  美國進行過一項調查，其中2%選擇了66（沒讀懂題的笨蛋）、5%的選擇了50（第一層）、10%的選擇了33（第二層）、6%選擇了22（第三層）、12%的選擇了0或者1（思考到了最后），但最后的結果平均值為19，第三層左右的人獲得了最終的勝利，
• 以上兩個故事告訴我們，在投資問題或者博弈問題中，我們的層數不可太高也不可太低，太低是傻子，太高聰明反被聰明誤，

1-6 Strategic Reasoning

• 在其他人的決策確定的情況下，每一個決策者都是為了最大化個人的識訓效用來做出決策，
• 一旦納什均衡建立，沒有人可以通過改變決策跳出均衡而獲利受益，
• 如果某些決策者通過改變決策跳出均衡可以獲利受益，那么說明納什均衡還沒有真正建立，
• 納什均衡是一個穩定的狀態，但并不是一個最優的獲利狀態，

1-7 Best Response and Nash Equilibrium

• Best Response 最優回應
  如果知道其他所有人的動作，那么挑選對于自己最有利的動作就變得十分簡單，
  a i 表 示 第 i 個 決 策 者 所 做 出 的 決 策 a_i表示第i個決策者所做出的決策 ai?表示第i個決策者所做出的決策
  a ? i = { a 1 , . . . , a i ? 1 , a i + 1 , . . . , a n } 表 示 除 去 a i 以 外 其 他 人 的 決 策 a_{-i}=\{a_1,...,a_{i-1},a_{i+1},...,a_n\}表示除去a_i以外其他人的決策 a?i?={a1?,...,ai?1?,ai+1?,...,an?}表示除去ai?以外其他人的決策
  a = ( a i , a ? i ) a=(a_i,a_{-i}) a=(ai?,a?i?)
  a i ? ∈ B R ( a ? i ) i f f ? a i ∈ A i , u i ( a i ? , a ? i ) > = u i ( a i , a ? i ) a_i^*\in BR(a_{-i})\space iff \forall a_i\in A_i,u_i(a_i^*,a_{-i})>=u_i(a_i,a_{-i}) ai??∈BR(a?i?) iff?ai?∈Ai?,ui?(ai??,a?i?)>=ui?(ai?,a?i?)
  其中 B R ( a ? i ) BR(a_{-i}) BR(a?i?)表示已知其他決策資訊后第i個決策者做出的最優回應，最優回應不一定只有一個，并且最優相應集合中的所有元素 a i ? a_i^* ai??都滿足下列要求，當且僅當選擇 a i ? a_i^* ai??的效用大于等于選擇其他所有回應的效用，
• Pure Strategy Nash Equilibrium 純策略納什均衡
  實際上我們并不知道其他人會做出何種決策，因此根據他人決策制定自己的最優回應是不現實的，
  a = { a 1 , . . . , a n } i s a p u r e s t r a t e g y N a s h e q u i l i b r i u m i f f ? i , a i ∈ B R ( a ? i ) a=\{a_1,...,a_n\}is \space a \space pure \space strategy \space Nash \space equilibrium \space iff \space \forall i,a_i\in BR(a_{-i}) a={a1?,...,an?}is a pure strategy Nash equilibrium iff ?i,ai?∈BR(a?i?)

1-8 Nash Equilibrium of Example Games

• 納什均衡的定義
  給定其他決策者的決策，每個決策者都沒有單獨改變決策的動機，（也就是當前決策是最優決策）
  假設一共有A、B、C三個決策者，已知A、B決策下C做出最優決策 c ? c^* c?，已知A、C決策下B做出最優決策 b ? b^* b?，已知B、C決策下A做出最優決策 a ? a^* a?，那么 ( a ? , b ? , c ? ) (a^*,b^*,c^*) (a?,b?,c?)就是一個納什均衡點，
• 如何從決策矩陣中挑選納什均衡點？
  看該單元格，是否左側的值是該列左側值的最大值，右側的值是否是該行右側值的最大值，
• 納什均衡不一定是對于全域來說最優的結果，比如囚徒困境，
• 納什均衡也不是自發實作的，需要有一定的溝通協商規定，總之就是直接間接獲取他人的決策資訊，
  

1-9 Dominant Strategies

• Strictly\Very Weakly Dominates 決策優勢、劣勢關系
  s i s t r i c t l y d o m i n t a t e s s i ′ i f ? s ? i ∈ S ? i , u i ( s i , s ? i ) > u i ( s i ′ , s ? i ) s_i \space strictly \space domintates \space s_i^{'} \space if \forall s_{-i}\in S_{-i},u_i(s_i,s_{-i})>u_i(s_i^{'},s_{-i}) si? strictly domintates si′? if?s?i?∈S?i?,ui?(si?,s?i?)>ui?(si′?,s?i?)
  s i v e r y w e a k l y d o m i n t a t e s s i ′ i f ? s ? i ∈ S ? i , u i ( s i , s ? i ) > = u i ( s i ′ , s ? i ) s_i \space very \space weakly \space domintates \space s_i^{'} \space if \forall s_{-i}\in S_{-i},u_i(s_i,s_{-i})>=u_i(s_i^{'},s_{-i}) si? very weakly domintates si′? if?s?i?∈S?i?,ui?(si?,s?i?)>=ui?(si′?,s?i?)
  嚴格壓制關系與輕微壓制關系的區別就在于取不取等號，以 s i s_i si?嚴格壓制決策 s i ′ s_i^{'} si′?為例，是指無論其他決策者制定什么決策，當前決策者選擇 s i s_i si?的效用一定嚴格優于選擇 s i ′ s_i^{'} si′?，
• 如果一個決策壓制其他所有決策，那么稱之為占優策略，如果該決策嚴格壓制每一個其他決策，那么稱之為嚴格占優策略，并且該策略唯一，由占優策略組成的策略組合一定是納什均衡點，全部由嚴格占優策略組成的策略組合一定是唯一的納什均衡點，

1-10 Pareto Optimality

• 之前對于決策的選擇以及評估都是站在每個決策者的角度，現在我們跳出決策者的身份，以一個外界觀察者的角度來評估決策，我們只考慮最直接的一種評估方式，如果決策組合 O O O對于所有決策者的效用都優于決策 O ′ O^{'} O′，那么我們稱 O P a r e t o ? d o m i n a t e s O ′ O \space Pareto-dominates \space O^{'} O Pareto?dominates O′，
  比如說 O ( 7 , 8 ) 、 O ′ ( 4 , 5 ) ， 那 么 我 們 可 得 O P a r e t o ? d o m i n a t e s O ′ O(7,8)、O^{'}(4,5)，那么我們可得O \space Pareto-dominates \space O^{'} O(7,8)、O′(4,5)，那么我們可得O Pareto?dominates O′，
• Pareto-Optimal 帕累托最優
  一個決策組合 O ? O^* O?，如果沒有其他任何一個決策組合帕累托壓制 O ? O^* O?,那么稱該決策組合是帕累托最優，
  帕累托最優定義的并不是壓制別人的能力，而是不被其他人壓制，
  一場游戲中可能有多個帕累托最優決策組合，
  一場游戲中最少含有一個帕累托最優決策組合，
• 實體分析
  
  注意對于零和博弈問題來說，所有決策組合都是帕累托最優，

2-1 Mixed Strategies and Nash Equilibrium Taste

• 以安保設定檢查關卡、攻擊者制定策略攻擊關卡的博弈問題來引出混合策略，

2-2 Mixed Strategies and Nash Equilibrium

• 純策略每次決策選擇的是具體的動作，而混合策略每次決策選擇的是概率分布，純策略納什均衡是混合策略納什均衡的一種，
• 純策略均衡：每個決策者都是根據已知其他決策者的選擇從而做出決策，并且在已知其他決策者選擇的前提下沒有改變自己決策的動機，混合策略均衡：每個決策者只可以調整自己的決策分布，而自己的效用則由其他決策者的決策分布決定，
• 在博弈游戲中，決策者每次選擇固定的決策方式是最愚蠢的結果，因為競爭者會根據你的固定選擇從而制定策略獲利，因此決策者應該隨機決策來迷惑對手，讓對手猜不透你的選擇，
• 區分定義：在純策略中每個決策者每一步決定的是一個動作 a i a_i ai?；在混合策略中每個決策者每一步決定的是一個策略 s i s_i si?，策略包含多個動作及對應概率，針對第 i i i個決策者所有策略的組合為 S i = { s 1 , . . . , s n } S_i=\{s_1,...,s_n\} Si?={s1?,...,sn?}，針對所有決策者的策略組合為各個決策者的策略笛卡爾積 S = S 1 × . . . × S n S=S_1\times ...\times S_n S=S1?×...×Sn?，
• 在純策略中我們針對每個決策者的不同動作衡量效用，在混合策略中我們針對每個決策者的不同策略概率分布來衡量效用，換句話說計算效用期望，
  u i ( s ) = ∑ a ∈ A u i ( a ) P r ( a ∣ s ) , P r ( a ∣ s ) = ∏ j ∈ N s j ( a j ) u_i(s)=\sum_{a\in A}u_i(a)Pr(a|s),Pr(a|s)=\prod_{j\in N}s_j(a_j) ui?(s)=∑a∈A?ui?(a)Pr(a∣s),Pr(a∣s)=∏j∈N?sj?(aj?)
• 混合策略中的最優回應以及納什均衡
  只需要將之前的 a i a_i ai?全部替換成 s i s_i si?即可，
  s i ? ∈ B R ( s ? i ) i f f ? s i ∈ S i , u i ( s i ? , s ? i ) > = u i ( s i , s ? i ) s_i^*\in BR(s_{-i})\space iff \forall s_i\in S_i,u_i(s_i^*,s_{-i})>=u_i(s_i,s_{-i}) si??∈BR(s?i?) iff?si?∈Si?,ui?(si??,s?i?)>=ui?(si?,s?i?)
  s = { s 1 , . . . , s n } i s a N a s h e q u i l i b r i u m i f f ? i , s i ∈ B R ( s ? i ) s=\{s_1,...,s_n\}is \space a \space Nash \space equilibrium \space iff \space \forall i,s_i\in BR(s_{-i}) s={s1?,...,sn?}is a Nash equilibrium iff ?i,si?∈BR(s?i?)
• 納什理論
  每個有限游戲都有一個納什均衡，（有限游戲是指有限的players、actions、utilities），

2-3 Computing Mixed Nash Equilibrium

• 以行人問題作為示例，展示兩種納什均衡的求解方法，
  
  

2-4 Hardness Beyond 2x2 Games

• 本章節介紹演算法求解納什均衡問題的困難行與復雜度，
• 尋找NE（納什均衡）的兩個經典演算法：
  LCP（Linear Complementarity）formulation 線性互補問題，
  Support Enumeration Method 子集列舉演算法，
• NE求解是一個困難的問題，現在還沒有一般的NE求解方法（不僅限于雙矩陣博弈），目前還沒有求解NE的多項式時間演算法，并且與NE有關的幾個問題已經被證明是np-hard的（比如判斷當前問題是否有多于一個NE），
• 在4 人及以上的博弈中，納什均衡的計算是屬于PPAD-Complete 的，總結來說，PPAD介于NP與P之間，最外層的NPC問題是指在多項式時間內可以判斷是否存在解，NP問題是指已知存在解但無法在多項式時間內求解，P問題是指可以在多項式時間內求解，

2-5 Example: Mixed Strategy Nash

• 本節我們以足球中點球大戰的例子來體會混合策略納什均衡在實際當中的應用，

• 點球大戰說的是這么一種博弈游戲，點球者可選擇向左向右踢，守門員可選擇向左向右撲救，最簡單的情況，我們默認守門員撲空的情況，點球者收益是1，守門員收益是0；守門員選對方向的情況，點球者收益是0，守門員收益是1，但是實際情況中，收到點球者球技的影響，守門員撲空時也不一定進球，比如說該球員右腳技術很差，即便撲空，也只有75%的概率進球，

• 最基礎的點球大戰收益矩陣：
  

• 調整后的點球大戰收益矩陣：
  

• 守門員的決策分布使得點球者對自己的決策漠不關心（收益相等）：
  設守門員向左撲的概率為 q q q，向右撲的概率為 1 ? q 1-q 1?q
  達到納什均衡時，點球者向左向右踢得收益相同：
  q × 0 + ( 1 ? q ) × 1 = q × 0.75 + ( 1 ? q ) × 0 , q = 4 7 q\times 0+(1-q)\times 1=q\times 0.75+(1-q)\times 0,q=\frac{4}{7} q×0+(1?q)×1=q×0.75+(1?q)×0,q=74?

• 點球者的決策分布使得守門員對自己的決策漠不關心（收益相等）：
  設點球者向左踢的概率為 p p p，向右踢的概率為 1 ? p 1-p 1?p
  達到納什均衡時，守門員向左向右撲得收益相同：
  p × 1 + ( 1 ? p ) × 0.25 = p × 0 + ( 1 ? p ) × 1 , p = 4 7 p\times 1+(1-p)\times 0.25=p\times 0+(1-p)\times 1,p=\frac{4}{7} p×1+(1?p)×0.25=p×0+(1?p)×1,p=74?

• 分析以上結果，點球者知道自己的左腳更具有優勢，因此增大向左踢的概率，最終達到納什均衡有 4 7 \frac{4}{7} 74?的概率向左踢，守門員知道點球者左腳有優勢會更多向左踢，因此增大向左撲的概率，最終達到納什均衡有 4 7 \frac{4}{7} 74?的概率向左撲，

2-7 Data：Professional Sports and Mixed Strategies

• 上一節中我們利用收益矩陣理論分析了點球大戰中的博弈情況，這一節我們通過真實實驗資料去驗證理論的正確性，

• 147場點球統計出的收益矩陣資訊：
  

• 設點球者向左踢的概率為 P K P_K PK?，守門員向左撲的概率為 P G P_G PG?，計算納什均衡點，
  
  

• 將計算出的概率與實際統計的概率相比，兩者結果非常接近，證明納什均衡理論的確是實際存在的、正確的理論，可以表征事物發展的內在規律，
  

3-1 Beyond the Nash Equilibrium

• 本章節用三張圖片，三個故事分別引出Dominated Strategies、Zero-Sum Games、Coordination，

3-2 Strictly Dominated Strategies & Iterative Removal

• 本章節帶來的是嚴格占優策略以及迭代消除法，
• Strictly Dominated Strategies 嚴格占優策略
  A strategy a i ∈ A i a_i\in A_i ai?∈Ai?is strictly dominated by a i ′ ∈ A i a_i^{'}\in A_i ai′?∈Ai?if u i ( a i , a ? i ) < u i ( a i ′ , a ? i ) ? a ? i ∈ A ? i u_i(a_i,a_{-i})<u_i(a_i^{'},a_{-i})\forall a_{-i}\in A_{-i} ui?(ai?,a?i?)<ui?(ai′?,a?i?)?a?i?∈A?i?.
  簡單來說，無論其他決策者作何決策，第 i i i個決策者選擇 a i a_i ai?的收益都要大于選擇 a i ′ a_i^{'} ai′?，
• 迭代消除法程序圖示
  每次迭代消去針對的都是某一特定決策者，因此只需看對應的左側收益或者是右側收益，不用考慮雖然在左側收益完全占優，但是右側收益被消除的有更優的情況，因為博弈的程序是最大化個人收益，不會去考慮到其他決策者的收益，
  
  注意：迭代消除的程序同樣也可以使用混合策略，比如說第二張圖中，如果U行與D行以相同概率混合，混合結果同樣嚴格占優M行，同樣可以消除掉M行，雖然這里M行可以使用純策略消除，因此給與我們提示，如果純策略消除不掉的話或許可以嘗試混合策略消除，
• 借助迭代消除的思想也可以找到純策略納什均衡點，
  具體方法是：找到每一行左側收益的最大值標出，找到每一列右側收益的最大值標出，如果某一個單元下標重合，那么就是純策略納什均衡點，
  
• 依據嚴格占優策略的迭代消除法會保持納什均衡的性質（即不影響納什均衡），并且迭代消除的順序無關緊要（最終結果相同），
• 弱占優策略
  相較于嚴格占優策略，弱占優策略的條件相對寬松了一些，嚴格占優策略要求針對所有的其他決策者決策，第 i i i個決策者選擇 a i a_i ai?的收益都要優于 a i ′ a_i^{'} ai′?的收益，弱占優決策是指，針對所有的其他決策者決策，第 i i i個決策者選擇 a i a_i ai?的收益都要大于等于 a i ′ a_i^{'} ai′?的收益，并且對于部分其他決策者的決策情況，第 i i i個決策者選擇 a i a_i ai?的收益都要優于 a i ′ a_i^{'} ai′?的收益，總結來說弱占優策略部分滿足嚴格占優策略的要求，
  弱占優策略同樣可以用于迭代消除，但是迭代消除的順序對結果有影響，至少一個納什均衡點被保留，

3-3 Dominated Strategies & Iterative Removal:An Application

• 本章節介紹了一個十分有趣的實驗來佐證，豬都不會去選擇被嚴格壓制的策略，更何況是人類，
• 實驗內容是這樣的，在一個大籠子里關著一頭大豬和一頭小豬，兩頭豬都在籠子的A側，籠子的B側有一個機關，觸發該機關在籠子的A側就會掉落下10份食物，無論大豬小豬從A側跑到B側觸發機關再回到A側都需要消耗2份食物，大豬會欺負小豬，不同情況下大豬小豬獲得事物配比如下：
  如果大豬先得到食物，最終小豬獲得1份，大豬獲得9份，
  如果小豬先得到食物，最終小豬獲得4份，大豬獲得6份，
  如果大豬小豬同時獲得，最終小豬獲得3份，大豬獲得7份，
• 該問題的收益矩陣如下圖所示：
  
• 雖然無論誰先得到食物，都是大豬獲益更多，但是對于小豬來說，正確的決策能增加自己的收益，選擇花費2份食物代價去觸發機關，也就以為著會較晚獲得食物，因此看起來大豬小豬都選擇等待是最好的選擇，但同時也存在問題如果都不觸發機關就都無法獲得食物，
• 該問題中存在著嚴格占優策略，對于小豬來說，選擇等待的收益永遠大于選擇觸發的收益，因此小豬很大概率會選擇等待，而大豬雖然也想“坐享其成”，但小豬的決策讓大豬不得不更多時候選擇去觸發機關，最終實驗的統計結果如下：