面对对手的决策
对某个假设反应最优的方案,遇到另一种反应可能失效。有限二人零和博弈把这种张力写成矩阵: 是行玩家收到、列玩家支付的收益。行玩家要最大化收益,列玩家要最小化。矩阵固定且已知;混合策略表示各自独立随机选择,选择时看不到对手实际采取的行动。
本篇把博弈保证连接到已学的线性规划对偶。
由保证收益建立线性规划
行策略 满足 、。面对纯列 的期望收益为 。若每个值均至少为 ,对任意列混合策略 也成立,因为 是这些值的凸组合。因此行玩家的最佳保证可由下式求出:
标量 的正负不受限制:所有矩阵元素均为负的博弈,其值也为负。未作其他改变便加上 会改变问题。同样,若列策略 、 且 ,它保证行玩家的期望收益不超过 ;列玩家在这些约束下最小化 。
证明透视
为什么只需检查纯反应
固定 。面对混合反应 的期望收益为 ,是各纯列收益的加权平均,不会小于它们的最小值;选择达到最小值的纯列便能取等。对固定列策略,行玩家的最大值也可同理由纯行达到。这个单次期望界不需要不同回合相互独立,也不要求对手一定随机选择。
证书与等值的存在
对任意可行的行保证 和列保证 ,分别用 乘 、用 乘 。由两个策略的分量和均为一,得到
因此相同的可行保证 已证明两个策略均最优,无须枚举全部混合策略。有限维线性规划强对偶适用于以上两个问题:它们可行,行目标有有限上界、列目标有有限下界,均可由矩阵元素取得,故存在保证相等的最优策略,其共同值称为有限博弈的值。结论是所述同时行动零和模型的期望收益,不是每次实际收益均相同。
例子
令 ,。对两个纯列的期望收益为 和 ;最坏反应给出 。当 时最小值为 ,当 时为 ,所以交点 达最大值 。
列玩家取 时,对任何纯行的期望收益都是 。行策略 对两个纯列保证至少 ;列策略对两个纯行保证至多 。上下界相等,证明博弈值。单用任何一个纯行的保证只有零,可见混合可能改善最坏情况。
反例模式
混合策略不保证每次收益固定
采用上述策略时,四个可能的矩阵收益仍是 ;各结果概率是相应行、列概率之积,期望为 。一次观察到零不违反保证:保证是对每个允许的对手反应,行玩家随机选择所得的期望。
安全的平移
所有矩阵元素加上同一常数 ,每对混合策略的收益都增加 ,因为两个概率向量的分量和均为一。因此博弈值增加 ,最优策略不变。此法可使某种形式的收益为正,但报告原问题的值时必须减回平移量。对不同的行或列加不同常数一般会改变策略激励,并不等同此变换。
练习
快速检查
(对上述 ,若 ,最坏纯列收益是多少?该策略最优吗?)
解答 · 答案
两个收益为 和 ,最坏为 ,故非最优。
快速检查
(验证 对两个纯行的收益,并给出上界证书。)
解答 · 答案
两行各给 。任何行混合都是它们的加权平均,因此列策略给上界 。
快速检查
(对 的每个元素加 ,新博弈值和一对最优策略是什么?)
解答 · 答案
新值为 ;两个策略仍为 。
快速检查
(对 ,用纯策略证明博弈值。为什么行问题须允许负的 ?)
解答 · 答案
第一行保证 ,第二列使两行收益都不超过 ,故值为 。强加 会错误排除此可行保证。