算法与数据结构 / 博弈论 · 我的最优选择，取决于你怎么选 待审核 5 页

博弈论 · 我的最优选择，取决于你怎么选

博弈论研究两个 (或多个) 理性参与者之间的策略互动:每一方的最佳选择都依赖对手的选择。一切分析始于一张收益矩阵——行是一方的策略、列是另一方的策略,格子里写下双方的结局。本系列沿 Memorial University 的讲义从最纯粹的零和博弈讲起,逐步走到非零和的纳什均衡。

主线一条:读懂矩阵 → 纯策略的鞍点 → 划掉被支配的策略 → 无鞍点时改用混合策略 → 越过零和到纳什均衡。每页都可编辑收益、拖滑块或单步执行,实时看 maximin / minimax、支配消去、期望收益折线与最优反应如何变化。

两类对局先分清: 零和 (一方所得 = 另一方所失,如棋类 / 猜拳) 用 minimax 求解,核心是鞍点与混合策略;非零和 (可共赢可共输,如囚徒困境) 没有「博弈值」,核心换成纳什均衡与最优反应。纯策略是「固定出某一招」,混合策略是「按概率随机出招」。 basics · 收益矩阵 / 零和

收益矩阵：把一场对局摊成一张表

博弈的起点。两名参与者各选一个策略（行 / 列）落到某一格，格子里的数就是结局。认识零和博弈：一方收益恒为另一方的相反数，一个数即可描述整格。点选行列看落点，并理解「读表只是第一步，难在不知道对手会怎么选」。

 core · maximin / minimax

鞍点：保底线与压顶线相遇之处

零和博弈的纯策略解：行内最小的最大值(maximin)与列内最大的最小值(minimax)相等处即鞍点，不等则须改用混合策略。

 technique · 迭代消去

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

化简的捷径。若某行在每列都不优于另一行，它就被弱支配，可以删去；删后重新审视，即迭代消去。单步演示：被支配者标红、支配者标绿、随后退场。一个预设连环消到唯一解（即鞍点），一个开局即僵持（提示该上混合策略）。

 core · 混合策略 / minimax 定理

混合策略：无鞍点时，把出招交给骰子

2×2 无鞍点博弈的图解法：期望收益对 Red 的两种应对各成一条直线，取下包络的最高点即博弈值。一般情形须走线性规划。

 core · 纳什均衡 / 囚徒困境

纳什均衡：谁也不想单方面反悔的那一格

越过零和。非零和博弈每格记一对收益，两人各自最大化自己。用最优反应找出双方互不反悔的格子 = 纳什均衡。四个经典预设：囚徒困境（占优策略导致次优均衡）、协调博弈 / 性别战（多个均衡）、配对硬币（纯策略下无均衡，只有混合）。

 两条贯穿全系列的定理: von Neumann 的 minimax 定理——任何有限二人零和博弈在混合策略下都存在均衡,且混合策略下 maximin = minimax = 博弈值 (纯策略下二者常不相等);Nash 的存在性定理——任何有限博弈 (含非零和) 只要允许混合策略,就至少有一个纳什均衡。Nash 定理把存在性推广到非零和;零和情形下再加一步均衡可交换性的论证,才回到 minimax 定理 —— 且后者早了二十二年。

相关链接

取材与总览

  • Game Theory · Memorial University www.mun.ca 本系列的取材出处:用 2×2 收益矩阵讲零和博弈、鞍点、minimax 与混合策略的入门讲义 (minimax = 5 的例子即源于此)。
  • Game theory — Wikipedia en.wikipedia.org 博弈论总览:标准型 / 扩展型博弈、零和与非零和、合作与非合作博弈,以及它在经济学 / 生物学 / 计算机科学中的应用。

收益矩阵 · 零和

  • Normal-form game — Wikipedia en.wikipedia.org 标准型博弈的定义:参与者、策略集、收益函数,以及收益矩阵 / 双矩阵的表示法。
  • Zero-sum game — Wikipedia en.wikipedia.org 零和博弈:收益之和恒为零的对局(和为其他常数的常和博弈平移后等价),与 minimax 定理、混合策略均衡的关系。

鞍点 · minimax · 混合策略

  • Minimax — Wikipedia en.wikipedia.org minimax / maximin 准则、零和博弈中的鞍点,以及博弈树搜索里的 minimax 算法。
  • Saddle point — Wikipedia en.wikipedia.org 鞍点的定义:在一个方向上是极小、另一方向上是极大的点 —— 几何与博弈论两重含义。
  • Minimax theorem — Wikipedia en.wikipedia.org von Neumann 1928 年的定理:任何有限二人零和博弈在混合策略下都存在均衡,且此时 maximin = minimax —— 鞍点与混合策略两页的理论支柱。
  • Mixed strategy — Wikipedia en.wikipedia.org 混合策略的定义、无差异原则,以及 2×2 零和博弈的求解。

支配与机制设计

  • Strategic dominance — Wikipedia en.wikipedia.org 支配策略、严格 / 弱支配的区别,以及迭代消去中严格支配与弱支配的分野。
  • Vickrey auction — Wikipedia en.wikipedia.org 第二价格拍卖:「如实出价」是弱占优策略 —— 支配关系在机制设计里的经典应用。

纳什均衡 · 非零和