博弈論

博弈論（game theory）是一門單獨的學科，和RL并無統屬關系。然而由于RL，特別是MARL大量應用到了相關的知識，所以這里也把它寫在RL系列里了。

歷史

博弈論最早可追溯到“齊威王田忌賽馬”，但它真正的發展是在20世紀下半葉。

RL的歷史相對比較晚，因此從淵源來看，RL=博弈論+控制論+ML。

參考：

https://blog.csdn.net/sobermineded/article/details/79601986

博弈論歷史、發展與應用

教程

《Game Theory An Introduction》，Steven Tadelis著。

Steven Tadelis，經濟學家。Harvard博士（1997），UCB教授。

概述

要理解博弈論，可以通過博弈論和決策論的區別開始。

決策論是研究局中人在給定其他環境參數條件下的最優選擇問題。

博弈論研究的是當局中人充分考慮到其他局中人對其戰略選擇的反應后（即局中人都具有同樣充分的理性時）進行最優戰略的選擇。

博弈論的直接目標不是找到一個玩家的最佳策略，而是找到所有玩家的最理性策略組合。我們稱最理性策略組合為均衡（equilibrium）。

從宏觀上可以將博弈論研究的問題分為：合作博弈和非合作博弈。現代狹義的博弈論一般是指非合作博弈。

非合作博弈根據參與博弈的參與人做決策的先后順序可以分為：靜態博弈和動態博弈。

靜態博弈：參與人同時做決策，常用標準型（normal form）表述其策略。如兩人零和博弈等。

動態博弈：參與人有先后順序做決策，且后者能觀察到前者所做的決策，如圍棋等。常用擴展型（extensive form）來表述其策略，常用的擴展型表述為博弈樹。

非合作博弈根據參與人是否已知對方的信息，可以分為：完美信息博弈和不完美信息博弈。

完美信息博弈：參與人對相關信息完全已知，如棋類游戲。玩家知道對方棋子所在的位置。

不完美信息博弈：參與人對相關信息并不完全已知。如牌類游戲，玩家并不知道對手的牌是什么。

當局中人的個數n為有限數且每個局中人的戰略空間中的元素只有限個時，稱博弈為有限博弈（finite game）。

決策問題的三要素：

• 行動(action): 玩家可能的選擇
• 結果(outcome): 每個行動的可能后果
• 傾向(preference): 對所有可能后果，按照從最渴望到最不渴望的排列。

理智選擇假設：

一個玩家完全明白決策問題：

• 所有可能的行動
• 所有可能的結果
• 了解行動如何影響結果
• 玩家的理性傾向（收益）是基于結果的

經濟人(Homo economicus)：一個經濟人是理智的，了解決策問題的各個因素，并且總是選擇可以獲得最高收益的行動。

風險態度：

• 中立風險（risk neutral）：認為同樣期望回報的價值相同。
• 厭惡風險（risk averse）：傾向于一個確定性的回報，不愿意采用一個擁有同樣期望回報的不確定性方案。
• 喜愛風險（risk loving）：更嚴格地傾向于采用擁有同樣期望回報的賭注。

博弈論旨在了解游戲的動態，以優化其玩家可能獲得的結果。相反的，**逆博弈論（Inverse Game Theory）**旨在根據玩家的策略和目標來設計游戲。逆博弈論在多智能體AI以及人機交互AI中都很有用處。

囚徒困境

上圖是囚徒困境（prisoner’s dilemma）的策略矩陣。

參與者為：囚徒A和囚徒B。動作空間為：{坦白、抵賴}，回報函數由矩陣給出。即：

• 當囚徒A和囚徒B都坦白時，囚徒A被判處3年有期徒刑、囚徒B也被判處3年有期徒刑。
• 當囚徒A坦白、囚徒B抵賴時，囚徒A被當場釋放、囚徒B被判處5年有期徒刑。
• 當囚徒A抵賴、囚徒B坦白時，囚徒A被判處5年有期徒刑、囚徒B當場釋放。
• 當囚徒A抵賴、囚徒B抵賴時，囚徒A和B都被判處1年有期徒刑。

很明顯，如果兩個囚徒都選擇抵賴，那么它們總的懲罰最低。然而，選擇抵賴對于囚徒個人來說是理性的嗎？

答案是：選擇抵賴對于個人來說并不理性。因為，就個人而言，囚徒并不知道另外一個囚徒選擇的策略是什么。在這種情況下，選擇坦白對于個人來說是理性的，而且是最優的。

即，不管其他囚徒選擇什么動作，選擇坦白總比選擇抵賴要優。

比如，對于囚徒A來說：

當囚徒B選擇坦白時，如果囚徒A選擇坦白被判處3年有期徒刑；而這時如果A選擇抵賴則被判處5年有期徒刑，所以這時囚徒A選擇坦白要好。

當囚徒B選擇抵賴時，如果囚徒A選擇坦白，則當場釋放；而這時如果A選擇抵賴，則被判處1年有期徒刑，所以這時囚徒A選擇坦白要好。

綜合這兩種情況，對于囚徒A不管囚徒B如何選擇，選擇坦白都是最好的。

在該例中（坦白，坦白）是占優策略（dominated strategy）。所謂占優策略是指如果一方在任何情況下從某種策略中得到的回報均大于從另外一種策略得到的回報，那么我們稱為這種策略為占優策略。

囚徒困境同樣適于分析寡頭壟斷廠商合作的不穩定性。對于寡頭整體而言最理性的做法是（合作，合作）。于是，諸如OPEC等組織會聯手以期達到利潤最大化。但同時，另外有種激勵，若自己悄悄毀約、不遵守協議自己的獲利會高于合作下的獲利。于是（不合作，不合作）的策略組合排擠掉了（合作，合作）的策略組合，并且由于（不合作，不合作）組合還是一個占優策略均衡，所以，卡特爾經常以失敗告終，也就屬情理之中了。

帕累托最優

帕累托最優(Pareto Optimality)，也稱為帕累托效率(Pareto efficiency)，是指資源分配的一種理想狀態，假定固有的一群人和可分配的資源，從一種分配狀態到另一種狀態的變化中，在沒有使任何人境況變壞的前提下，使得至少一個人變得更好。帕累托最優狀態就是不可能再有更多的帕累托改進的余地;換句話說，帕累托改進是達到帕累托最優的路徑和方法。 帕累托最優是公平與效率的"理想王國"。

Vilfredo Pareto，1848~1923，意大利經濟學家、社會學家。

納什均衡

Nash equilibrium的定義：

在博弈中，如果聯結策略$({\pi }_1^{?},\dots ,{\pi }_n^{?})$滿足：

$$V_i({\pi }_1^{?},\dots ,{\pi }_i^{?},\dots ,{\pi }_n^{?})\ge V_i({\pi }_1^{?},\dots ,{\pi }_i,\dots ,{\pi }_n^{?}),?{\pi }_i\in {\Pi }_i,i=1,\dots ,n$$

則為一個納什均衡。若上式嚴格大于，則為嚴格納什均衡。

若智能體的策略對一個動作的概率分布為1，對其余的動作的概率分布為0，則這個策略為一個純策略。

若一個策略對于智能體動作集中的所有動作的概率都大于0，則這個策略為一個完全混合策略。

介于上述兩者之間的叫做混合策略。

納什存在定理(Nash’s existence Theorem)：

任何普通形式、具有限策略集合的博弈存在一個納什均衡的混合策略。

零和博弈中，兩個智能體是完全競爭對抗關系，它只有一個納什均衡值，即使可能有很多納什均衡策略，但是期望的獎勵是相同的。

一般和博弈是指任何類型的矩陣博弈，包括完全對抗博弈、完全合作博弈以及二者的混合博弈。在一般和博弈中可能存在多個納什均衡點。

下圖是納什均衡的幾何解釋：

John Nash，1928～2015，數學家、經濟學家。Princeton博士（1950），Princeton教授。主要研究博弈論、微分幾何學和偏微分方程。諾貝爾經濟學獎獲得者（1994）。奧斯卡金像獎電影《美麗心靈》男主角原型。

高風險下的納什均衡

在一些特殊情況下，即使犯錯誤的可能性很小也可能導致大的災難（比如核電站，出問題就非常嚴重），納什均衡就可能不會產生有說服力的解釋。考慮如下博弈：

		乙
		左	右
甲	上	8,10	-1000,9
	下	7,6	6,5

在這個博弈中，參與人甲會選擇“下”，因為如果乙不小心（低概率）犯錯誤，要避免產生右上的災難性情況。

這個例子說明，個體可能不想我們所假設的那樣完全理性，在遇到高風險的情況下，人們會考慮風險，從而使得最終結果可能偏離納什均衡戰略。

總結

以上是生活随笔為你收集整理的机器学习（三十八）——博弈论（1）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。