面對對手的決策
對某個假設反應最優的方案,遇上另一種反應可能失效。有限二人零和博弈把這種張力寫成矩陣: 是行玩家收到、列玩家支付的收益。行玩家要最大化收益,列玩家要最小化。矩陣固定且已知;混合策略表示各自獨立隨機選擇,選擇時看不到對手實際採取的行動。
本篇把博弈保證連接到已學的線性規劃對偶。
由保證收益建立線性規劃
行策略 滿足 、。面對純列 的期望收益為 。若每個值均至少為 ,對任意列混合策略 也成立,因為 是這些值的凸組合。故行玩家的最佳保證可由下式求出:
純量 的正負不受限制:所有矩陣元素均為負的博弈,其值也為負。未作其他改動便加上 會改變問題。同樣,若列策略 、 且 ,它保證行玩家的期望收益不超過 ;列玩家在這些約束下最小化 。
證明透視
為何只需檢查純反應
固定 。面對混合反應 的期望收益為 ,是各純列收益的加權平均,不會小於它們的最小值;選取達到最小值的純列便能取等。對固定列策略,行玩家的最大值也可同理由純行達到。這個單次期望界不需要不同回合互相獨立,也不要求對手一定隨機選擇。
證書與等值的存在
對任意可行的行保證 和列保證 ,分別用 乘 、用 乘 。由兩個策略的分量和均為一,得到
因此相同的可行保證 已證明兩個策略均最優,毋須枚舉全部混合策略。有限維線性規劃強對偶適用於以上兩個問題:它們可行,行目標有有限上界、列目標有有限下界,均可由矩陣元素取得,故存在保證相等的最優策略,其共同值稱為有限博弈的值。結論是所述同時行動零和模型的期望收益,不是每次實際收益均相同。
例子
令 ,。對兩個純列的期望收益為 和 ;最壞反應給出 。當 時最小值為 ,當 時為 ,所以交點 達最大值 。
列玩家取 時,對任何純行的期望收益都是 。行策略 對兩個純列保證至少 ;列策略對兩個純行保證至多 。上下界相等,證明博弈值。單用任何一個純行的保證只有零,可見混合可能改善最壞情況。
反例模式
混合策略不保證每次收益固定
採用上述策略時,四個可能的矩陣收益仍是 ;各結果概率是相應行、列概率之積,期望為 。一次觀察到零不違反保證:保證是對每個允許的對手反應,行玩家隨機選擇所得的期望。
安全的平移
所有矩陣元素加上同一常數 ,每對混合策略的收益都增加 ,因為兩個概率向量的分量和均為一。因此博弈值增加 ,最優策略不變。此法可使某種形式的收益為正,但報告原問題的值時必須減回平移量。對不同的行或列加不同常數一般會改變策略誘因,並不等同此變換。
練習
快速檢查
(對上述 ,若 ,最壞純列收益是多少?該策略最優嗎?)
解答 · 答案
兩個收益為 和 ,最壞為 ,故非最優。
快速檢查
(驗證 對兩個純行的收益,並給出上界證書。)
解答 · 答案
兩行各給 。任何行混合都是它們的加權平均,因此列策略給上界 。
快速檢查
(對 的每個元素加 ,新博弈值和一對最優策略是甚麼?)
解答 · 答案
新值為 ;兩個策略仍為 。
快速檢查
(對 ,用純策略證明博弈值。為何行問題須允許負的 ?)
解答 · 答案
第一行保證 ,第二列使兩行收益都不超過 ,故值為 。強加 會錯誤排除此可行保證。