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

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

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

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

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

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

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

若迭代消去最后只剩一行一列,那个格子就是博弈的解,且必为鞍点——支配关系是发现纯策略解最省力的捷径。即使消不到唯一,每删掉一个被支配策略,都让后续分析的矩阵更小,因此它常作为求解前的预处理。注意这里用的是严格支配(留有「至少一处更优」),删除严格被支配策略不会丢掉任何均衡,是安全的化简。

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

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

1.3 · 它真实跑在哪里

迭代消去严格被支配策略是求解博弈的标准预处理,也是机制设计 / 拍卖理论里论证「说真话是占优策略」(如第二价格拍卖)的核心论证方式。在多智能体 / 算法博弈论中,它把巨大的策略空间先裁剪到可处理的规模,再交给均衡求解。