附录 A · 速查

📌 Ctrl+F 搜。不要通读。 这一页是做题、面试、写代码时翻的那一页，不重讲任何东西 —— 每条都标了出处，看不懂就点回去。

🗺️ 一、哪个概念在哪一章

📖 二、定义速查（一行一条）

单人决策（07–08）

非合作博弈（09–15）

机制设计 · 匹配 · 分配（16–21）

合作博弈（22–23）

社会选择（24–26）

✏️ 三、⭐⭐ 手算套路卡

这一节是这份附录最值钱的部分。每张卡都是「拿起笔就能照做」的清单。

🃏 vNM 效用标定

📍 出处：08

1. 把每条无差异关系写成期望效用相等的方程
2. 整理出一条把三个 $u$ 串起来的等式
3. 做差判断排序（例：$u(c)-u(a)=3(u(a)-u(b))>0$）
4. ⭐ 最好的定 1、最差的定 0（正仿射变换恰好 2 个自由度），代回解出中间那个
5. 验：把数字代回原式两边算一遍，且排序要和第 3 步一致

🃏 圈最佳响应，找纯策略 NE

📍 出处：11

1. 每格写「行玩家收益, 列玩家收益」，顺序固定
2. 逐列看：圈出这一列里第一个数最大的那格
3. 逐行看：圈出这一行里第二个数最大的那格
4. 两个数都被圈的格子 = 纯策略 NE
5. 一个双圈都没有 → 没有纯 NE，去混合

⚠️ 并列最大要全圈 —— 漏圈并列值 = 漏掉整个均衡，手算最常见的错。

🃏 2×2 混合 NE（无差异法）

📍 出处：12

1. 先用圈法找纯 NE，顺手删掉严格劣势的动作
2. ⭐ 令列玩家对两个动作无差异，解出 $p$（行玩家的概率）—— 用每格第二个数
3. ⭐ 令行玩家无差异，解出 $q$（列玩家的概率）—— 用每格第一个数
4. 回代算两人的期望收益

⭐⭐ 口诀：求谁的概率，就翻到对面的收益去列方程。 ⚠️ 拿自己的收益解自己的概率，是这一章唯一的、也是最普遍的错法。

🃏 支撑枚举（动作 ≥ 3）

📍 出处：12

1. 猜一个支撑组合
2. 列方程：对手的 $n-1$ 个无差异等式 + 1 个归一化
3. 解出概率
4. 验三条：① 支撑内期望全相等（记为 $v_i$）② 支撑外期望 $\le v_i$ ③ 概率非负且和为 1

⚠️ 概率跑出 $[0,1]$ → 换支撑；解出 0 或 1 → 它其实是纯策略。最容易漏第 ② 条。

🃏 IESDS（迭代删除严格劣势）

📍 出处：10

1. 行玩家看每格第一个数、按列比较；列玩家看第二个数、按行比较
2. 找到一个严格劣势的行/列，整行整列划掉
3. 在更小的表里重复，直到删不动
4. 删到只剩一格 → 那格是唯一的 NE

⭐ 严格支配下删除顺序无关、不会误删 NE。⚠️ 换成弱支配，两条性质全部失效。

🃏 maximin 与鞍点

📍 出处：13

1. 只看自己的收益，每行取最小值，再在这些最小值里取最大 → 纯策略安全水平
2. 列玩家同理：每列取最小、再取最大（用他自己的收益）
3. 零和矩阵的捷径：算「行最小的最大」和「列最大的最小」—— 相等 → 鞍点，纯策略解完；不相等 → 老实混合
4. 2×2 求混合 maximin：写出对着对手每个纯动作的期望收益，画成随 $p$ 变化的两条直线，取下包络的最高点（也就是两线交点）

🃏 逆向归纳

📍 出处：14

1. 找一个所有子节点都已标好收益向量的节点
2. 看这个节点轮到谁
3. 挑他自己那一维最大的那条边
4. ⭐ 把选中那条边的整个收益向量搬到这个节点上
5. 回到第 1 步，直到根

⚠️ 第 4 步是唯一会错的地方：搬整个向量，不是只搬那个人的数字。

🃏 拥塞博弈求纯均衡

📍 出处：15

1. 先假设所有资源都有人用，令各条的耗时相等并联立（加上人数守恒）
2. 解出来若有负数，说明该资源在均衡里没人用，去掉它重解
3. ⚠️ 验均衡用 $t_x(n_x+1)\ \ge\ t_y(n_y)$ —— 你换过去之后自己也算进新路的拥堵里
4. 势函数 $\Phi(a)=\sum_x\sum_{k=1}^{n_x}c(x,k)$；⚠️ 它不是总成本

🃏 SPDA / CPDA

📍 出处：17

1. 每个没被暂收的提案方，向自己列表里还没拒过自己的最高一位提案
2. 接受方把「手里的 + 新来的」排序，只暂时握住最好的 $b_c$ 个
3. 被挤下来的回到第 1 步（此后不再提这一家）
4. 没人能再提案时停

验：逐对 $(s,c)$ 查阻挡对；⭐ 提案方拿到的一定是全场对它最好的稳定匹配。 多对一：把一所招 $b_c$ 人的学校拆成 $b_c$ 个座位，结论照搬。

🃏 TTC

📍 出处：18

1. 每个人指向当前图里他最想要的那套房；每套房指向它的主人
2. 从任意一点沿边走，一定会走出一个环（每点出度都是 1）
3. 环上成交：每人拿走他指着的那套；把环上的人和房整个删掉
4. 剩下的人重新指向剩余房里最想要的，回到第 2 步

验 IR：每个人拿到的都不比自己原来那套差（换不成的人拿回自己的房，也没亏）。

🃏 Round-Robin

📍 出处：20

1. 定一个人的顺序
2. 轮流叫号，轮到谁就从剩下的物品里挑自己估值最高的一件
3. 一圈叫完从头再来，直到分完

⚠️ 并列时怎么取会改结果（第 20 章那张表取 $g_4$ 得 135/45、取 $g_3$ 得 140/45，两个都是 EF1）。 ⭐ 结果一定 EF1 + PROP1 + 均衡（每人 $\lfloor m/n\rfloor$ 或 $\lceil m/n\rceil$ 件），⚠️ 但不保证 PO。

🃏 嫉妒图算法

📍 出处：20

1. 所有人空手开始
2. 找一个 source（没有入边、谁都不眼红他），把任意一件物品发给他
3. 发完检查是否成环；成环就沿环轮换整堆，重复到无环
4. 回到第 2 步直到发完

⭐ 轮换只增不减每个人的值 ⟹ 不会冒出新边 ⟹ 边数严格下降，所以破环必然终止。 ⭐ 只要求估值单调（不必可加），⚠️ 但做不了均衡分配。

🃏 EF1 / PROP1 / MMS 怎么验

📍 出处：19

• EF1：$i$ 嫉妒 $j$ 时，从 $A_j$ 里拿掉对 $i$ 最值钱的那一件，再比一次
• PROP1：往 $A_i$ 里添一件（挑对 $i$ 最值钱的），看够不够 $\frac1n v_i(M)$
• MMS：枚举把 $M$ 分成 $n$ 堆的所有方式，取「最小那堆」的最大值；⭐ 总有 $\mathrm{MMS}_i \le \frac1n v_i(M)$

🃏 带权嫉妒图 → 算出该补多少钱

📍 出处：21

1. 边权 $w(i,j)=v_i(X_j)-v_i(X_i)$
2. 查有没有正权环（边权取反跑 Bellman–Ford）。有 → 这个分法救不回来
3. 无正权环时，令 $p_i=\ell(i)=$ 从 $i$ 出发的最大权路径的权重
4. 验：逐条查 $v_i(X_i)+p_i \ge v_i(X_j)+p_j$；⭐ 最长路给出的是恰好补平的最小支付（会出现「持平」）

🃏 PS「吃蛋糕」与 SD 比较

📍 出处：21

1. 每件物品是一块重量 1 的蛋糕；所有人同时、同速吃自己当前最想要且没吃完的那件
2. 一件被吃光，正在吃它的人立刻转向列表里下一件还没吃完的
3. 全部吃光时停，每人吃掉的份额就是概率
4. 比两张概率表用 SD：⭐ 从最爱往下累计概率，每一层都不少才叫支配；⚠️ 常常互不可比

🃏 Core 验证（n = 3）

📍 出处：22

1. 空集恒成立；大联盟由效率取等号；3 个单点给下限
2. ⭐ 3 个两人联盟翻成上限：因为 $x(N)=v(N)$，有 $x(S)\ge v(S) \iff x(N\setminus S)\le v(N)-v(S)$
3. 三个下限 + 三个上限，一眼看得出有没有解
4. 想证明核心是空的：把三条不等式直接相加（例：$2\times100 \ge 50+70+X \Rightarrow X\le80$）

⭐ 简单博弈的捷径：核心非空 ⟺ 存在否决者；且核心里非否决者一律拿 0。

🃏 Least Core / Nucleolus

📍 出处：22

1. Least Core：把所有约束放松成 $x(S)\ge v(S)-\varepsilon$，最小化 $\varepsilon$（永远非空）
2. Nucleolus：算出每个候选分配的超额向量（所有 $e(x,S)$ 升序排），取字典序最大的那个
3. 验：核心非空时 nucleolus 必在核心里

🃏 Shapley 值（n = 3 的六排列法）

📍 出处：23

1. 列出 6 个排列，每行从左到右依次结算增量 $v(S\cup\{i\})-v(S)$
2. 每人的 6 个增量求和 ÷ 6
3. ⭐ 两个自查：① 三人总和 $=v(N)$ ② 每一行也加起来 $=v(N)$（望远镜求和）

⭐ 简单博弈捷径：$\phi_i = \dfrac{i\ \text{把局面从输变赢的排列数}}{n!}$。 ⭐ 图博弈闭式解：$\phi_i=\frac12\sum_{j\ne i}w(\{i,j\})$ ——「每条边的价值两个端点一人一半」。 ⭐ Banzhaf：数「$i$ 是关键成员」的联盟个数 $\eta_i$，再 $\beta_i=\eta_i/\sum_j\eta_j$。

🃏 位置计分规则

📍 出处：24

1. 写下打分向量：Plurality $(1,0,\dots,0)$、k-approval 前 $k$ 个 1、Borda $(m-1,\dots,1,0)$
2. 逐格填表，按候选项求和
3. ⭐ Borda 自查：总分必等于 $n\times\frac{m(m-1)}{2}$（14 人 5 候选 = 140）

🃏 IRV 与两轮决选

📍 出处：24

• 两轮决选：按第一名票数取前两名，直接一对一比
• IRV：反复删掉第一名票数最少的候选项，选票顺延
• ⚠️ 顺延时必须跳过所有已被删掉的候选项（这是 IRV 最容易算错的一步）

🃏 多数图与 Condorcet

📍 出处：25

1. $\binom m2$ 对逐对数票：把 $x$ 排在 $y$ 前面的人多，就画 $x\to y$
2. 出度 = Copeland 分
3. 打败所有人的那个 = Condorcet 赢家（可能不存在 —— 成环就是没有）

🃏 锦标赛解

📍 出处：25

⭐ 包含关系：$BA\subseteq UC$、$CO\subseteq UC$、$UC\subseteq TC$。

🃏 中位选民规则（单峰域）

📍 出处：26

1. 先把候选项排成一条轴，验证每个人的偏好是单峰的（从峰出发两侧各自递减）
2. 只问每个人的峰在哪
3. 选出中位数那个峰
4. ⭐ 奇数选民 + 单峰 ⟹ Condorcet 赢家一定存在，而且中位选民规则会选中它，还是策略防伪的

🃏 逻辑那五章

📍 出处：03–06

• 真值表：⭐ 每个子公式各占一列，从最内层往外填；$n$ 个符号 $2^n$ 行
• 转 CNF：消去蕴含（$\varphi\to\psi \equiv \neg\varphi\vee\psi$）→ 德摩根把 ¬ 赶到字母前（NNF）→ 分配律把 ∨ 赶到里面；⭐ 同时含 $L$ 和 $\neg L$ 的子句恒真，直接扔
• 分辨率反证四步：⭐ ① 否定结论 ② 全转 CNF ③ 反复分辨 ④ 推出空子句 □；⚠️ 终点必须是 □，中途推出了结论也不算完
• 一阶推理：照搬上面，多两个零件 —— Skolem 化（$\forall x\exists y$ 要用函数 $f(x)$，⚠️ 不等价、只保可满足性）和 合一 MGU（⚠️ 必须最一般，多余限制会丢完备性）

📐 四、核心公式

帕累托 / 支配

$$o \text{ 帕累托支配 } o' \iff \forall i,\ u_i(o)\ge u_i(o')\ \ \text{且}\ \ \exists j,\ u_j(o)>u_j(o')$$

纳什均衡与无差异原理

$$u_i(s_i,s_{-i}) \ \ge\ u_i(t_i,s_{-i})\qquad \forall i\in N,\ \forall t_i\in S_i$$

$$u_i(a_i,s_{-i}) \;=\; u_i(b_i,s_{-i}) \;\ge\; u_i(c_i,s_{-i}),\qquad s_i(a_i),s_i(b_i)>0,\ s_i(c_i)=0$$

💡 上式左半边解出对手的概率，右半边是验证时最容易漏的那一条。

极大极小定理（von Neumann 1928）

$$\max_{s_1}\min_{s_2}u_1 \;=\; \min_{s_2}\max_{s_1}u_1 \;=\; v$$

Rosenthal 势函数

$$\Phi(a)=\sum_{x\in R}\ \sum_{k=1}^{n_x(a)} c(x,k) \qquad\text{⚠️ 不是总成本 } \textstyle\sum_x n_x\,c(x,n_x)$$

💡 一条路、$c(x,k)=k$、3 人在用：总成本 $3\times3=9$，而 $\Phi$ 这一项 $=1+2+3=6$。

公平判据

$$\text{EF}:\ v_i(A_i)\ge v_i(A_j) \qquad \text{EF1}:\ \exists g\in A_j,\ v_i(A_i)\ge v_i(A_j\setminus\{g\})$$

$$\text{PROP}:\ v_i(A_i)\ge \tfrac1n v_i(M) \qquad \text{MMS}_i=\max_{A}\ \min_{j\in N}\ v_i(A_j)$$

蕴含（都是单向）：$\text{EF}\Rightarrow\text{EF1}\Rightarrow\text{PROP1}$、$\text{EF}\Rightarrow\text{PROP}$。 ⚠️ EF1 和 MMS 互不蕴含（一个是相对判据、一个是绝对判据）。

核心与 Shapley

$$x\in \text{Core} \iff x(N)=v(N)\ \text{且}\ \forall S\subseteq N:\ x(S)\ge v(S)$$

$$\phi_i=\frac{1}{n!}\sum_{\pi\in\Pi_N}\Delta_\pi(i) =\frac{1}{n!}\sum_{S\subseteq N\setminus\{i\}}|S|!\,(n-|S|-1)!\,\bigl(v(S\cup\{i\})-v(S)\bigr)$$

💡 手算用排列版，写程序用联盟版。 那两个阶乘 = 「有多少种排列让 $i$ 恰好接在 $S$ 后面」。

一阶随机支配

$$p \succeq^{SD}_i q \iff \sum_{o'\succeq_i o} p_i(o') \ \ge\ \sum_{o'\succeq_i o} q_i(o')\quad \text{对每一件 } o$$

💡 等价于「对每一个与该排序相容的效用函数，期望都不低」。

⚠️ 五、常见陷阱清单

🧮 六、存在性 / 唯一性 / 复杂度一览

🚫 七、不可能定理一览（谁和谁不能同时要）

两条能真正绕开的路（各破坏一个前提）：

⭐⭐ 不可能定理的正确用法：它是一张地图，标出每条路要付的过路费。 技术能告诉你每个选项的代价，但「我们最不能忍受哪种失败」是价值判断，得由人来做。

📖 八、术语对照

🔗 九、跨教程速查

👉 回到首页　｜　动手练：27 · 实战与挑战项目