動機
即使每個行動都有其價值,決策仍可能是可預測的。在零和博弈中,若對手知道你採取某個固定行動,就可以選擇針對它的應對來加以利用。在若干行動之間隨機化可以提高所能保證的收益。這裏的數學問題不是哪種隨機選擇「感覺上」難以預測,而是哪個概率分佈能針對對手的每一個行動給出最好的保證。
有限零和博弈把這個問題與線性規劃聯繫起來。混合策略是一個概率向量,針對對手每個純行動的保證是一個線性不等式。雙方最佳保證相等這一事實來自線性規劃的強對偶定理;該定理在此作為外部定理陳述,而不從頭證明。
定義
定義 2.1.1
(混合策略與期望收益)
設 為實 收益矩陣,其中 。行玩家選擇某一行,當列玩家選擇第 列時,行玩家得到 ;列玩家支付該數額。混合行策略是滿足 且 的 ;類似地,混合列策略是滿足 且 的 。雙方的選擇分別獨立地從這兩個分佈中抽取。期望收益為 。
定義 2.1.2
(保證與鞍點)
對於 ,行玩家的保證收益為 ,這是因為各列收益的概率加權平均不小於它們的最小值,而取到最小值的純列可以達到該最小值。對於 ,列玩家的最壞支付為 ,理由類似。若對任意可行的 都有 ,則稱 為混合策略下的鞍點。
定理
定理 2.1.3
(有限零和博弈極小極大定理)
對每個有限實收益矩陣,
兩個極值均可取到。最優策略構成混合策略鞍點,其公共值稱為該博弈的值。
定理 2.1.4
(最優性證書)
若可行策略 與實數 滿足:對每一列 有 ,並且對每一行 有 ,則這兩個策略都是最優的,且博弈的值為 。
證明思路
證明
(先由弱不等式,再用線性規劃對偶)
對任意可行的 ,行保證至多為 ,而 至多為列的最壞支付。因此最大的行保證不會超過最小的列最壞支付。特別地,若證書中的不等式成立,則由行不等式知,針對 的期望收益至少為 ;由列不等式知,它至多為 。兩個界重合,從而證明了證書以及鞍點不等式。
為在一般情形下建立存在性,把行玩家的優化問題寫成線性規劃
其中 的符號不受限制。其對偶是列規劃
其中 不受符號限制。這兩個規劃都是可行的:任取一個純策略,並取足夠小的 或足夠大的 即可。由於矩陣只有有限個實數元素,它們的目標值是有界的。有限維線性規劃強對偶定理指出,這兩個可行且有界的規劃取得相等的最優值。最優解滿足的約束恰好就是證書不等式,由此得到極小極大等式與鞍點。該證明使用了強對偶定理,而並未證明該定理。
證明透視
為甚麼約束只需考慮純應對
對於固定的混合策略,針對混合應對的期望收益是針對各純應對的收益的加權平均。其最小值或最大值在這些純應對之一上取到。因此行玩家的規劃只需對每個純列寫一條約束,列玩家的規劃只需對每個純行寫一條約束。證明於是分為兩部分:由「行保證 列支付」這條不等式鏈,兩個最優值之間的不等式無需額外工具即可得到;只有反方向的不等式以及最優值能否取到,才需要借助線性規劃強對偶定理。
例題詳解
例題 2.1.5
(猜硬幣博弈)
設 。以概率 選擇任一行,則針對每個純列的收益均為零。類似的列混合策略針對每個純行的收益也均為零。證書證明博弈的值為零。固定選取某一純行的最壞收益為 ,所以隨機化改善了行玩家的保證。
例題 2.1.6
(一個不對稱的混合均衡)
設 。若行玩家以概率 選擇第一行,則其針對兩列的期望收益分別為 與 。令二者相等得 ,保證收益為 。以概率 選擇第一列,使每個純行的收益均為 。由證書得博弈的值為 。
例題 2.1.7
(一個純策略鞍點)
設 。該矩陣沒有純鞍點:行最小值中的最大者為 ,而列最大值中的最小者為 。相比之下,對於 ,第二行與第二列給出收益 。第二行保證至少得到 ,第二列把支付限制在至多 ,所以博弈的值為 ,無需隨機化。
常見錯誤
反例模式
分佈並不是對實際收益的承諾
在猜硬幣博弈中,均衡的期望收益為零,但每一次實際對局的收益是 或 。博弈的值描述的是期望,以及針對對手各種策略的最壞情形保證,而不是每一次具體對局的結果。
常見錯誤
(極小極大定理只適用於有限雙人零和博弈)
極小極大定理針對的是有限的二人零和博弈。它並不斷言任意多人博弈或非零和博弈具有同樣的值,也不斷言每個策略組合都是均衡。雙方隨機選擇相互獨立,是計算 所用乘積分佈模型的一部分。
解讀線性規劃
行變量 是針對每個純列的期望收益的下界。第 列對應的不等式為 。最大化 就是選取最好的保證下界。行玩家並不選擇對手的列;這些約束保證了針對所有列該保證都成立。同樣,列變量 是針對每個純行的收益的上界,列玩家最小化這個上界。
常見錯誤
(強迫值非負)
變量 與 允許取負值。當矩陣所有元素均為負時這一點很重要:對於一階矩陣 ,博弈的值為 。若要求 ,則行規劃將不可行,儘管該博弈本身定義完全良好。概率變量仍須非負且和為一;對收益符號的限制是另一回事。
對偶這一步也可以透過拉格朗日(Lagrange)函數來驗證。給每個行約束 配一個非負乘子 。要使對不受限制的 取上確界時結果有限,乘子之和必須為一。其餘對行概率向量取上確界的結果是 ,其上界由 表示。最小化該表達式便得到列規劃。強對偶保證最優值相等並且可以取到;僅憑弱對偶只能得到二者之間的不等式。
例題 2.1.8
(一個值為負的博弈)
考慮一行兩列的矩陣 。行玩家沒有選擇,其保證收益為 。列玩家選擇第二列,保證支付至多為 。這兩個策略證明博弈的值為 。列玩家在最小化行玩家的收益,所以在這一符號約定下,更負的元素對它更有利。
概念視角幾何
把值看成下包絡線的最高點
對兩個行,記 。每一列 給出一條直線 ,而保證收益是這些直線的逐點最小值,是 上的凹分段線性函數。博弈的值就是它的最高點。對 ,兩條直線為 與 ;其最小值在兩線相交處 達到最高,高度為 。
支撐集與無差異條件
在均衡處,每個以正概率使用的純行動,都必須是對手均衡混合策略的最優應對。就行玩家而言,設 最優,而 所用的某一行 給出的收益嚴格小於博弈的值。由列證書,針對 的每個行收益都至多為博弈的值。於是在 下它們的加權平均將嚴格低於博弈的值,這與鞍點收益相矛盾。類似的論證表明, 以正概率使用的每一列,針對 的收益恰好等於博弈的值。
常見錯誤
(只靠無差異不足以證明最優)
這一必要條件解釋了不對稱例子中的平衡計算。在所給的均衡處兩列都被使用,所以它們針對行混合策略必須給出相同的收益;解 便得到候選解。但僅有無差異並不構成完整的證書。還必須檢驗概率非負、總概率為一,以及所有純行動的不等式,包括被賦予概率零的行動。在較大的博弈中,只平衡所選的一對行動,可能會漏掉某個能改善玩家應對的其他行動。
例如,若在不對稱矩陣中添加第三列,其收益為 ,則原來的行混合策略仍使前兩列的收益平衡在 ,但第三列給出 。因此,在擴大後的博弈中它並不能保證 。決定所給混合策略是否最優的是最優應對不等式,而不僅僅是平衡方程。
一個有用的變換
給矩陣的每個元素加上常數 ,會使每個期望收益平移 ,因為概率權重之和為一。於是博弈的值增加 ,而最優策略集保持不變。把每個元素乘以一個正常數,會使博弈的值按該常數縮放,同樣保持最優策略不變。乘以負常數會顛倒偏好順序,需要改變由哪位玩家最大化或最小化;它不能當作普通的正縮放來處理。
這種平移可以使數值例子更易於考察,但在最終的值中不能被默默忽略。例如,給一行兩列的例子加上 ,其值由 變為零。最優的列仍是第二列。該變換對每一對混合策略都成立,而不僅僅對均衡策略對成立,因為 。
純策略與混合策略的保證
行最小值中的最大者,是行玩家限於純行動時的最佳保證。列最大值中的最小者,是列玩家相應的純策略上界。若二者在某個元素處重合,則該行與該列構成純鞍點。若二者不同,則不存在純鞍點,但有限極小極大定理仍然給出混合最優策略。猜硬幣的例子中純策略下界與上界分別為 與 ,而其混合策略的值為零。
純鞍點證書特別容易檢驗:所選元素必須是其所在行的最小值,同時是其所在列的最大值。這樣行玩家選擇該行就保證至少得到該元素,列玩家選擇該列就把收益限制在同一個元素。出現並列並無妨礙,還可能產生多個純鞍點。這些行與列的比較遵循行玩家最大化、列玩家最小化的約定;若交換雙方的目標,比較方向也隨之顛倒。
博弈的值是針對任何獨立於該玩家隨機化而選取的混合應對的保證。它並不要求對手使用最優策略。若行玩家使用最優策略,則任何對手分佈給出的期望收益都至少為博弈的值;針對最優的列策略則恰好等於博弈的值。這一區別有助於把證書理解為穩健的保證,而不是對雙方實際都會以最優方式隨機化的預測。
驗證給定的解
實際計算的結果可以在不重新求解線性規劃的情況下加以檢驗。首先驗證每個概率向量的元素非負且和為一。其次計算 的每個分量與 的每個分量。若前者的最小值等於後者的最大值,則這個共同的數就是博弈的值,兩個向量都是最優的。這一等式提供了雙向的證據:沒有任何行策略能針對所給列混合策略保證得更多,也沒有任何列策略能針對所給行混合策略迫使收益更少。
近似計算需要相應的限定。若行策略保證至少 ,而列策略把收益限制在 ,則 ,且真實的值位於二者之間。當兩個界不重合時,得到的是一個區間而非精確值。區間的闊度衡量證書中仍存在的差距;在斷言兩個數相等之前,必須考慮數值捨入。
混合鞍點也使量詞變得明確。行不等式必須對所有可能的列分佈成立,列不等式必須對所有可能的行分佈成立。僅檢驗所給策略對的收益,並不能證明其中任何一個斷言。純應對不等式是驗證這些全稱條件的有限方法,因為每個混合應對都是純應對的凸組合。
總結
混合策略是純行動上的概率分佈。針對所有純應對的保證化為線性約束。強對偶使行的最佳保證與列的最佳上界相等,而相互匹配的可行界則給出可以直接檢驗的最優性證書。
練習
快速檢查
(對猜硬幣博弈,計算均勻行混合策略針對第一個純列的收益。)
使用第一列的元素。
解答 · 答案
收益為 。
快速檢查
(對 ,驗證兩個行針對列混合策略 的收益。)
用列混合策略分別乘以每一行。
解答 · 答案
第一行得 ,第二行也得 ,所以兩行都不超過 。
快速檢查
(對 ,驗證第二行保證 ,且第二列把收益限制在 。)
取各行的最小值與各列的最大值。
解答 · 答案
第二行支付 或 ,所以其最小值為 。第二列支付 或 ,所以其最大值為 。證書適用。
快速檢查
(為甚麼針對每個純列的保證蘊含針對每個混合列的同樣保證?)
把混合策略的收益寫成加權平均。
解答 · 答案
針對混合列的收益是針對各純列收益的凸組合。若每一項都至少為 ,則它們的加權平均也至少為 。