动机
即使每个行动都有其价值,决策仍可能是可预测的。在零和博弈中,若对手知道你采取某个固定行动,就可以选择针对它的应对来加以利用。在若干行动之间随机化可以提高所能保证的收益。这里的数学问题不是哪种随机选择“感觉上”难以预测,而是哪个概率分布能针对对手的每一个行动给出最好的保证。
有限零和博弈把这个问题与线性规划联系起来。混合策略是一个概率向量,针对对手每个纯行动的保证是一个线性不等式。双方最佳保证相等这一事实来自线性规划的强对偶定理;该定理在此作为外部定理陈述,而不从头证明。
定义
定义 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
(一个值为负的博弈)
考虑一行两列的矩阵 。行玩家没有选择,其保证收益为 。列玩家选择第二列,保证支付至多为 。这两个策略证明博弈的值为 。列玩家在最小化行玩家的收益,所以在这一符号约定下,更负的元素对它更有利。
概念视角几何
把值看成下包络线的最高点
对两个行,记 。每一列 给出一条直线 ,而保证收益是这些直线的逐点最小值,是 上的凹分段线性函数。博弈的值就是它的最高点。对 ,两条直线为 与 ;其最小值在两线相交处 达到最高,高度为 。
支撑集与无差异条件
在均衡处,每个以正概率使用的纯行动,都必须是对手均衡混合策略的最优应对。就行玩家而言,设 最优,而 所用的某一行 给出的收益严格小于博弈的值。由列证书,针对 的每个行收益都至多为博弈的值。于是在 下它们的加权平均将严格低于博弈的值,这与鞍点收益相矛盾。类似的论证表明, 以正概率使用的每一列,针对 的收益恰好等于博弈的值。
常见错误
(只靠无差异不足以证明最优)
这一必要条件解释了不对称例子中的平衡计算。在所给的均衡处两列都被使用,所以它们针对行混合策略必须给出相同的收益;解 便得到候选解。但仅有无差异并不构成完整的证书。还必须检验概率非负、总概率为一,以及所有纯行动的不等式,包括被赋予概率零的行动。在较大的博弈中,只平衡所选的一对行动,可能会漏掉某个能改善玩家应对的其他行动。
例如,若在不对称矩阵中添加第三列,其收益为 ,则原来的行混合策略仍使前两列的收益平衡在 ,但第三列给出 。因此,在扩大后的博弈中它并不能保证 。决定所给混合策略是否最优的是最优应对不等式,而不仅仅是平衡方程。
一个有用的变换
给矩阵的每个元素加上常数 ,会使每个期望收益平移 ,因为概率权重之和为一。于是博弈的值增加 ,而最优策略集保持不变。把每个元素乘以一个正常数,会使博弈的值按该常数缩放,同样保持最优策略不变。乘以负常数会颠倒偏好顺序,需要改变由哪位玩家最大化或最小化;它不能当作普通的正缩放来处理。
这种平移可以使数值例子更易于考察,但在最终的值中不能被默默忽略。例如,给一行两列的例子加上 ,其值由 变为零。最优的列仍是第二列。该变换对每一对混合策略都成立,而不仅仅对均衡策略对成立,因为 。
纯策略与混合策略的保证
行最小值中的最大者,是行玩家限于纯行动时的最佳保证。列最大值中的最小者,是列玩家相应的纯策略上界。若二者在某个元素处重合,则该行与该列构成纯鞍点。若二者不同,则不存在纯鞍点,但有限极小极大定理仍然给出混合最优策略。猜硬币的例子中纯策略下界与上界分别为 与 ,而其混合策略的值为零。
纯鞍点证书特别容易检验:所选元素必须是其所在行的最小值,同时是其所在列的最大值。这样行玩家选择该行就保证至少得到该元素,列玩家选择该列就把收益限制在同一个元素。出现并列并无妨碍,还可能产生多个纯鞍点。这些行与列的比较遵循行玩家最大化、列玩家最小化的约定;若交换双方的目标,比较方向也随之颠倒。
博弈的值是针对任何独立于该玩家随机化而选取的混合应对的保证。它并不要求对手使用最优策略。若行玩家使用最优策略,则任何对手分布给出的期望收益都至少为博弈的值;针对最优的列策略则恰好等于博弈的值。这一区别有助于把证书理解为稳健的保证,而不是对双方实际都会以最优方式随机化的预测。
验证给定的解
实际计算的结果可以在不重新求解线性规划的情况下加以检验。首先验证每个概率向量的元素非负且和为一。其次计算 的每个分量与 的每个分量。若前者的最小值等于后者的最大值,则这个共同的数就是博弈的值,两个向量都是最优的。这一等式提供了双向的证据:没有任何行策略能针对所给列混合策略保证得更多,也没有任何列策略能针对所给行混合策略迫使收益更少。
近似计算需要相应的限定。若行策略保证至少 ,而列策略把收益限制在 ,则 ,且真实的值位于二者之间。当两个界不重合时,得到的是一个区间而非精确值。区间的宽度衡量证书中仍存在的差距;在断言两个数相等之前,必须考虑数值舍入。
混合鞍点也使量词变得明确。行不等式必须对所有可能的列分布成立,列不等式必须对所有可能的行分布成立。仅检验所给策略对的收益,并不能证明其中任何一个断言。纯应对不等式是验证这些全称条件的有限方法,因为每个混合应对都是纯应对的凸组合。
总结
混合策略是纯行动上的概率分布。针对所有纯应对的保证化为线性约束。强对偶使行的最佳保证与列的最佳上界相等,而相互匹配的可行界则给出可以直接检验的最优性证书。
练习
快速检查
(对猜硬币博弈,计算均匀行混合策略针对第一个纯列的收益。)
使用第一列的元素。
解答 · 答案
收益为 。
快速检查
(对 ,验证两个行针对列混合策略 的收益。)
用列混合策略分别乘以每一行。
解答 · 答案
第一行得 ,第二行也得 ,所以两行都不超过 。
快速检查
(对 ,验证第二行保证 ,且第二列把收益限制在 。)
取各行的最小值与各列的最大值。
解答 · 答案
第二行支付 或 ,所以其最小值为 。第二列支付 或 ,所以其最大值为 。证书适用。
快速检查
(为什么针对每个纯列的保证蕴含针对每个混合列的同样保证?)
把混合策略的收益写成加权平均。
解答 · 答案
针对混合列的收益是针对各纯列收益的凸组合。若每一项都至少为 ,则它们的加权平均也至少为 。