算法与数据结构 / 博弈论 · 我的最优选择,取决于你怎么选 / 支配策略:把永远不该选的策略划掉 待审核 3 / 5
technique · 迭代消去

支配策略:把永远不该选的策略划掉

并非每一行 / 每一列都值得保留。若 Blue 的某一行无论 Red 怎么应对都不优于另一行,Blue 就没有严格更好的理由选它——这行被另一行弱支配 (weakly dominated),可以划掉。(若那一行在每一列都严格更差,则是严格支配,此时理性的一方永远不会选它。)划掉后矩阵变小,可能又冒出新的被支配行 / 列,于是迭代消去 (iterated elimination)。它常能把一局对局化简,甚至直接逼出鞍点那个唯一解。

1 · 谁支配谁:行看 Blue(越大越好),列看 Red(越小越好)

Blue 要最大化收益:若存在另一行在每一列都 ≥ 本行(且至少一处更大),本行被支配,删去。Red 要最小化 Blue 的收益:若存在另一列在每一行都 ≤ 本列(且至少一处更小),本列被支配,删去。每删一个就重新审视剩下的子矩阵——这就是迭代。

下一步 ▸ 逐次消去:被支配的行 / 列标,把它压下去的「支配者」标绿,随后该行 / 列变暗退场。两个预设:一个能一路消到唯一解,一个开局即僵持。

图 1-1 · 迭代消去的单步演示。被支配的行或列标红、支配者标绿,随后该行列变暗退场。一个预设能一路消到唯一解,另一个开局即僵持。

1.1 · 消到唯一格 ⇒ 这就是解;消不动 ⇒ 还得靠混合

若迭代消去最后只剩一行一列,那个格子就是博弈的解,且必为鞍点——支配关系是发现纯策略解最省力的捷径。即使消不到唯一,每删掉一个被支配策略,都让后续分析的矩阵更小,因此它常作为求解前的预处理。注意本页判据是弱支配:另一行每列都不差、至少一处更好。弱支配的消去只保证博弈值不变,并不保留全部均衡,且结果依赖消去顺序——取值 0 到 3 的全部 3×33 \times 3 矩阵里,有鞍点的 136744 例中 34866 例会被消掉部分鞍点(实测本仓实现),但没有一例消光全部鞍点、也没有一例改变博弈值。若把判据换成严格支配(每列都严格更优),才有「不丢任何均衡」这条保证。

1.2 · 消不动时,僵持本身就是信号

第二个预设里没有任何行 / 列被支配:每一行都在某些列占优、又在另一些列吃亏,谁也淘汰不了谁。这正是无鞍点的局面——纯策略互相牵制。出路是按概率随机混用,即混合策略。所以「支配法卡住」往往是「该上混合策略了」的提示。

1.3 · 它真实跑在哪里

迭代消去被支配策略是求解博弈的标准预处理机制设计 / 拍卖理论里论证「说真话是占优策略」用的正是弱支配一侧——第二价格拍卖里如实出价只是弱占优:出价不改变胜负与成交价时收益相同,不存在严格改进。在多智能体 / 算法博弈论中,它把巨大的策略空间先裁剪到可处理的规模,再交给均衡求解。