27 · 实战与挑战项目

⏱ 项目 3 小时 – 2 天 ｜ 挑战 2 – 4 天 ｜ ⭐⭐ 这个板块最大的便宜：所有算法都能用几十行纯 Python 写出来

🎯 一句话

别的板块要动手得先有 GPU、数据集和一堆库；这一套从头到尾只需要 Python 自带的 itertools 和 fractions —— 而且每个算法都有一份「书上的标准答案」可以对账。

前面 25 章每一章都留了完整的手算例子。这一章就是把那些例子变成 assert。

🧰 开工前：三条这个板块特有的规矩

⚠️ 第三条之外还有一条：算法都是确定性的，没有随机种子 —— 唯一的不确定性来自 ⭐ 「并列怎么打破」，而它偏偏能改结果（项目一、项目四都会撞上）。

🥉 项目一：投票规则对比器（3 – 5 小时）

目标：亲手跑出第 24 章那句话 —— 同一份选票，六条规则，五个不同的赢家； 再补上第 25 章的 Copeland 凑成第七条。 依赖：24 · 25 · 26

• [ ] T1 位置计分规则写成通用函数（打分向量当参数传进去，一个函数覆盖一整族）
• [ ] T2 两轮决选 + IRV。⚠️ 顺延时要跳过所有已被淘汰的候选项，这是最容易写错的一行
• [ ] T3 两两对决表 → 多数图 → Condorcet 赢家（写成「可能返回 None」）
• [ ] T4 Copeland（数出度）· Top Cycle（可达）· Uncovered Set（两步内到达所有人）
• [ ] T5 ⭐ 把 3 人 3 候选的 Condorcet 悖论喂进去：condorcet() 返回 None，而三个锦标赛解仍有输出
• [ ] T6 ⭐⭐ IIA 复现：用第 26 章那个 5 人 3 候选的 Borda 例子，只改 c 的位置，看社会对 a、b 的排序翻转

from collections import Counter

# 第 24 章那份 14 人选票：每个元素是一位选民「从最爱到最恨」的排序
PROFILE = ([list("acbde")] * 5 + [list("ebcda")] * 4
           + [list("dcbea")] * 3 + [list("bdeca")] * 2)
CANDS = sorted(set(PROFILE[0]))

def positional(profile, cands, weights):        # ⭐ 一个函数覆盖一整族计分规则
    s = {c: 0 for c in cands}
    for ballot in profile:
        for j, c in enumerate(ballot):
            s[c] += weights[j]
    return s

def pairwise(profile, x, y):                    # 把 x 排在 y 前面的人数
    return sum(1 for b in profile if b.index(x) < b.index(y))

def condorcet(profile, cands):                  # ⭐ 可能返回 None —— 那才是重点
    for x in cands:
        if all(pairwise(profile, x, y) > pairwise(profile, y, x)
               for y in cands if y != x):
            return x
    return None

m = len(CANDS)
print("Plurality ", positional(PROFILE, CANDS, [1] + [0] * (m - 1)))
print("Borda     ", positional(PROFILE, CANDS, list(range(m - 1, -1, -1))))
print("Condorcet ", condorcet(PROFILE, CANDS))

🎯 该跑出来的数字

⭐⭐ 五个候选人，每一个都当选过。 而最后一行更刺眼：赢家 a 的出度是 0 —— 它输给了所有人。

✅ 通关：七行数字逐格对上（Borda 总分 140 是最好用的自查）；悖论上 condorcet() 返回 None； T6 的 IIA 翻转跑出来了（(a 6, b 7, c 2) → (a 6, b 4, c 5)，没有任何人改过对 a、b 的看法）。

🥉 项目二：纳什均衡求解器（1 天）

目标：把第 10 – 13 章的四套手算法变成代码，并让它们互相验证。 依赖：10 · 11 · 12 · 13

• [ ] T1 圈法找全部纯 NE。⚠️ 并列最大值必须全圈，这是漏掉均衡的头号原因
• [ ] T2 IESDS：反复删严格劣势的行/列。⭐ 在随机 3×3 上跑 1000 次，验证它从不误删 NE
• [ ] T3 ⭐⭐ 2×2 混合 NE：用 Fraction 解无差异方程。⚠️ 解 p 用列玩家的收益、解 q 用行玩家的收益，写反了是这一章唯一的错法
• [ ] T4 支撑枚举解 3×3（石头剪刀布），并用第 12 章那三条清单验证
• [ ] T5 maximin（每行取最小、再取最大）+ 鞍点判定（行最小的最大 == 列最大的最小）
• [ ] T6 ⭐ 验证第 13 章的推论：零和里两人各自的 maximin 策略凑一起恰好是 NE；换成性别之争就不成立

def pure_ne(U1, U2):
    """U1[i][j]、U2[i][j] 是行/列玩家在第 i 行第 j 列的收益。返回全部纯策略 NE。"""
    nR, nC = len(U1), len(U1[0])
    out = []
    for j in range(nC):
        colmax = max(U1[i][j] for i in range(nR))       # 逐列圈行玩家
        for i in range(nR):
            if U1[i][j] != colmax:                      # ⚠️ 并列最大值必须全圈
                continue
            rowmax = max(U2[i][k] for k in range(nC))   # 逐行圈列玩家
            if U2[i][j] == rowmax:                      # ⭐ 双圈 = 纯策略 NE
                out.append((i, j))
    return out

print("囚徒困境", pure_ne([[2, 0], [3, 1]], [[2, 3], [0, 1]]))   # [(1, 1)]
print("性别之争", pure_ne([[2, 0], [0, 1]], [[1, 0], [0, 2]]))   # [(0,0), (1,1)]
print("罚球    ", pure_ne([[-1, 1], [1, -1]], [[1, -1], [-1, 1]]))  # [] 没有纯 NE

🎯 该跑出来的数字

✅ 通关：上表全对；T2 的 1000 次随机测试零反例；⭐ T6 的对比做出来了 —— 零和里 maximin 组合就是 NE，而性别之争里行玩家 maximin 是 1/3、混合 NE 却是 2/3。

🥈 项目三：稳定匹配求解器（1 天）

目标：把「谁提案，谁受益」和「没有稳定机制能对双方同时防伪」从结论变成你自己搜出来的证据。 依赖：17 · 18（TTC 是加分项）

• [ ] T1 实现 DA。⭐ 写成「谁提案」是参数，同一个函数直接得到 SPDA 和 CPDA
• [ ] T2 阻挡对检查器：给定匹配，列出所有互相都更想要的 $(s,c)$
• [ ] T3 ⭐ 穷举全部稳定匹配（$n\le5$ 时枚举 $n!$ 个匹配逐个查），验证 SPDA 的结果确实是学生最优
• [ ] T4 复现第 17 章那次成功的谎报：$c_1$ 把 $s_1\succ s_2\succ s_3$ 报成 $s_1\succ s_3\succ s_2$
• [ ] T5 ⭐⭐ 暴力搜索验证 Roth 1982：枚举 $n=3$ 的全部实例，对每个人、每种谎报查有没有人能变好
• [ ] T6 加分：TTC（人指房、房指主人、找环、删环）；多对一（把一所招 $b_c$ 人的学校拆成 $b_c$ 个座位）

def da(proposers, receivers):
    """一对一延迟接受。两个参数都是 dict：名字 -> 偏好列表（从最想要开始）。"""
    held, free, nxt = {}, list(proposers), {s: 0 for s in proposers}
    while free:
        s = free.pop(0)
        c = proposers[s][nxt[s]]; nxt[s] += 1          # 向还没拒过自己的最高一位提案
        cur = held.get(c)
        if cur is None:
            held[c] = s                                # 空着，暂收
        elif receivers[c].index(s) < receivers[c].index(cur):
            held[c] = s; free.append(cur)              # ⭐ 来了更好的，把手里的踢掉
        else:
            free.append(s)                             # 被拒，回去继续提案
    return {v: k for k, v in held.items()}

S = {"s1": ["c1", "c2", "c3"], "s2": ["c2", "c3", "c1"], "s3": ["c3", "c1", "c2"]}
C = {"c1": ["s2", "s3", "s1"], "c2": ["s3", "s1", "s2"], "c3": ["s1", "s2", "s3"]}
print("SPDA", da(S, C))                                # 学生全拿第 1 志愿
cpda = da(C, S)                                        # ⭐ 换一边提案，同一个函数
print("CPDA", {v: k for k, v in cpda.items()})         # 学校全拿第 1 志愿

🎯 该跑出来的数字

⭐⭐ T5 那两个数字是这个项目的灵魂：书上的两句话在这里变成 0 和 864 —— 你亲手把 Roth 1982 的不可能性搜了出来。

✅ 通关：SPDA / CPDA 分别给出 $\mu_S$ 和 $\mu_C$；T3 的穷举结果和它们对得上；T5 跑出 0 / 864。

🥈 项目四：公平分配实验室（1 – 2 天）

目标：三个算法跑同一组估值，看 EF1 和 PO 是怎么分家的。 依赖：19 · 20 · 21（加分）

• [ ] T1 Round-Robin（轮流从剩下的挑自己估值最高的一件）
• [ ] T2 ⭐ 判据四件套 is_ef / is_ef1 / is_prop1 / is_po。 ⚠️ EF1 最容易写错的是那一步：从对方那堆里拿掉「对我最值钱」的那件（max(v[i][g] for g in A[j])），不是拿掉对他最值钱的
• [ ] T3 嫉妒图算法：找 source → 发一件 → 成环就沿环轮换整堆。⭐ 打印每步的边数，验证「破环只会让边变少」
• [ ] T4 MNW 暴力版（枚举 $n^m$ 种分配，先比正效用人数、再比乘积）
• [ ] T5 ⭐⭐ 统计实验：随机生成 500 个实例（$n=3$、$m=6$、估值 1–10），统计两个算法的 EF1 命中率和 PO 命中率
• [ ] T6 加分：$\mathrm{MMS}_i$ 计算器 + $\frac12$-MMS 贪心；第 21 章的带权嫉妒图（Bellman–Ford 查正权环，最长路给出恰好补平的支付）

🎯 该跑出来的数字

⭐ T5 是最值钱的一步：EF1 那一列两个都是 100%，PO 那一列裂开了。 ⚠️ 百分比取决于估值分布和平局规则 —— 要看的是那道裂缝，不是那个数。

✅ 通关：四个判据在书上的正反例上都判对；嫉妒图破环后边数严格下降；T5 的表做出来、能指出 PO 那一列的裂缝。

🥈 项目五：Shapley 值计算器（1 天）

目标：把第 23 章算出来，然后 ⭐⭐ 和你工作里在用的 shap 库对一次账。 依赖：22 · 23

• [ ] T1 排列枚举版（$n\le10$，$10!=362$ 万，秒级）
• [ ] T2 ⭐⭐ 行和自查写成 assert：每个排列的边际贡献加起来必须等于 $v(N)$（望远镜求和）。算错一个数当场炸
• [ ] T3 联盟版公式（带 $|S|!(n-|S|-1)!$ 那个），和 T1 比对 —— 两条路必须给出同一个数
• [ ] T4 图博弈：验证闭式解 $\phi_i=\frac12\sum_{j\ne i}w(\{i,j\})$ 和枚举完全一致
• [ ] T5 Core 判定：$n=3$ 用第 22 章的「三个下限 + 三个上限」，一般 $n$ 用 $2^n$ 条约束的线性规划
• [ ] T6 ⭐ 在手套博弈上同时算 Shapley 和 Core，确认 Shapley 落在 Core 外面；顺手算 Banzhaf 对比
• [ ] T7 加分：pip install shap scikit-learn，训一个 3–4 个特征的小模型，把 shap 的输出和你的排列枚举对账

🎯 该跑出来的数字

⭐⭐ T7 做完你会明白：shap 里 base_value + sum(shap_values) == prediction 就是效率公理； TreeSHAP 能取代你那段 $n!$ 循环靠的正是「表示法决定复杂度」。工程上会踩什么坑， 见《模型上线之后》10 · SHAP 能做什么不能做什么。

✅ 通关：煎饼博弈 $(6,4,6)$、行和 assert 全程不炸；T3 两条路给出同一个数； ⭐ T6 把「公平」和「稳定」的分歧打印了出来。

🥇 挑战 A：拥塞博弈实验室（2 – 3 天）

难度 ★★★☆☆ ｜ 目标：让第 15 章那个三行论证在你屏幕上一行一行地发生。

• [ ] T1 建模：资源集 + 每人的资源子集 + 成本函数 $c(x,k)$
• [ ] T2 最佳响应动态：反复找一个能改进的人让他换。⚠️ 判断时要用 $c(x, n_x+1)$ —— 你换过去之后自己也算进拥堵里
• [ ] T3 ⭐⭐ 每步同时打印三个数：那个人省下的成本 $\Delta_{\text{cost}}$、$\Phi$ 的降幅 $\Delta_\Phi$、当前 $\Phi$。验证前两个逐步相等
• [ ] T4 复现一万人三条路：确认收敛到 $(0, 5000, 5000)$、每人 50 分钟
• [ ] T5 ⭐ Braess：算改造前后的均衡耗时和 Price of Anarchy
• [ ] T6 ⭐⭐ 打破前提看它塌：改成加权拥塞博弈（成本依赖总权重而不是人数），最佳响应动态会绕圈不收敛

def phi(cost, counts):
    """Rosenthal 势函数。⚠️ 它不是总成本，是「每加一个人记一次当时的价」。"""
    return sum(sum(cost(x, k) for k in range(1, counts[x] + 1)) for x in counts)

total = lambda cost, cnt: sum(cnt[x] * cost(x, cnt[x]) for x in cnt)
cost = lambda x, k: {"a": 50 + k / 1000, "b": 40 + k / 500, "c": k / 100}[x]
for name, s in [("开局", {"a": 10000, "b": 0, "c": 0}),      # 一万人全走高速路
                ("均衡", {"a": 0, "b": 5000, "c": 5000})]:   # 第 15 章算出的均衡
    print(name, "Φ =", round(phi(cost, s), 2), " 总成本 =", round(total(cost, s), 2))

🎯 该看到的现象

✅ 通关：T3 的三列数字打印出来、$\Delta_\Phi=\Delta_{\text{cost}}$ 逐步成立；T4、T5 的数字和书上一致； ⭐ T6 找到一个不收敛的加权实例，并能说清被打破的是哪条前提（成本对使用者不再匿名）。

🥇 挑战 B：操纵率实验室（2 – 4 天）

难度 ★★★★☆ ｜ 目标：⭐⭐ 把 Gibbard–Satterthwaite 定理从一句话变成一张表。

第 26 章说「任何非独裁的满射 SCF 都存在可被谎报操纵的情形」。这个挑战让你把那些情形全部枚举出来、数一遍。

• [ ] T1 枚举 3 候选 3 选民的全部 $6^3=216$ 个偏好轮廓
• [ ] T2 对每条规则、每个选民、每种谎报，判断新赢家在他真实偏好里是否更靠前
• [ ] T3 ⭐ 出表。⚠️ 必须固定一个打破平局规则并写进报告 —— 它会明显影响结果
• [ ] T4 ⭐⭐ 把独裁规则也放进表里（「永远选 1 号选民的第一名」），确认它是 0%
• [ ] T5 扩到 4 候选 4 选民（$24^4$ 太大，随机抽 4000 个轮廓），看趋势
• [ ] T6 ⭐⭐ 域限制：只保留单峰偏好（候选轴 $a<b<c$ 时 6 种排序里只有 4 种单峰），跑中位选民规则
• [ ] T7 加分：统计 Borda 的成功操纵里有多少是 burying（把最强对手压到最后一名）；实现随机独裁并验证它防伪

🎯 该跑出来的数字（3 候选 · 3 选民 · 全部 216 个轮廓 · 字母序打破平局）

T5（4 候选 4 选民，抽 4000 个轮廓）：Plurality ≈33%、Borda ≈51%、IRV ≈18%、Copeland ≈55%，独裁仍是 0%。 ⭐ 候选项一多，所有非独裁规则的可操纵率都明显上升。

T6 单峰域（4 种单峰偏好 → $4^3=64$ 个轮廓）：⭐⭐ 中位选民规则 0 / 64 = 0%；IRV、Copeland 也是 0； Borda 6 / 64；⚠️ Plurality 反而是 12 / 64 = 18.8%，比全域的 16.7% 还高。

⭐⭐ 这是第 26 章第六节「两条能绕开的路」的实验版：你没有推翻 G–S，你换了一个更小的输入域。 ⚠️ 但 Plurality 那一行提醒你：域限制救的是「某一条特定规则」，不是「所有规则」。

✅ 通关：216 行的表做出来，四条常见规则非零、独裁恰好为 0；写清了打破平局规则并试过第二种； ⭐⭐ T6 的单峰实验做出来了，能解释「为什么这不叫推翻定理」。

📝 报告模板

# 实验：____
## 设定（玩家/候选项/物品的规模，偏好或估值从哪来）
## ⚠️ 打破平局的规则            ← 这个板块特有的一节，必须写 ⭐
## 和书上例子的对账表            ← 每个数字都要有出处（第几章第几节）
## 我搜出来的反例 / 边界案例
## 我原本以为 ___，实际上 ___

⚠️ 第二节是这个板块独有的：Round-Robin 的 135 还是 140、IRV 先淘汰谁，全看这一行。 不写清楚，别人复现不出你的数字。

🔗 这一章连到哪里

✅ 检查点

1. 这个板块动手的门槛和别的板块比差在哪？三条规矩分别是什么？
2. 为什么说「这边没有种子，但有一件事同样会改结果」？举一个带数字的例子。
3. 同一份 14 人选票在七条规则下的赢家分别是谁？哪个数字最适合做自查？
4. 圈法里最容易漏掉均衡的是哪一步？2×2 混合 NE 里唯一的错法是什么？
5. 项目三 T5 的两个数字是多少？它们分别对应哪条结论？
6. 项目四 T5 的统计实验，EF1 那一列和 PO 那一列分别长什么样？说明了什么？
7. 怎么用一行 assert 抓出算错的 Shapley 值？挑战 A 的 T3 要同时打印哪三个数？
8. 挑战 B 里独裁规则的可操纵率是多少？单峰域上得到 0% 为什么不叫推翻 G–S 定理？

🛑 完成了？

去附录 A · 速查把定义、手算套路卡和陷阱清单过一遍，然后回总目录。

⚡ 走神救援

⭐⭐ 这个板块动手的门槛低到不像话：不需要 GPU、数据集或 pip install，因为玩家 3 个、物品 5 件、选民 14 人 —— 规模全在纸笔量级。三条规矩：① 零依赖零数据 ② 先复现书上的手算例子（跑不出书上的数字就是写错了，这是别的板块给不了的调试条件）③ 用 Fraction 不要用 float。⚠️ 和 RL 那边对照：那边第一铁律是「跑多个种子」，这边根本没有种子，唯一的不确定性来自 ⭐ 并列怎么打破 —— Round-Robin 的并列取 $g_4$ 得 135/45、取 $g_3$ 得 140/45（两个都是 EF1），所以报告模板里专门有「打破平局的规则」一节。七个项目：项目一 投票规则对比器跑出「同一份 14 人选票、七条规则、五个赢家」（Plurality a、2-approval c、3-approval b、Borda b、两轮决选 e、IRV d、Copeland c，自查 Borda 总分 140），⭐⭐ 而赢家 a 的 Copeland 出度是 0 —— 它输给了所有人。项目二 纳什均衡求解器：圈法（⚠️ 并列最大值必须全圈）、IESDS（第 10 章那个 3×3 四步剩 (M,C)=(3,3)）、2×2 混合（⭐ 解 p 用列玩家的收益、解 q 用行玩家的收益）、鞍点（maximin 2 = minimax 2）；T6 对比出零和里 maximin 组合就是 NE，性别之争里 maximin 是 1/3 而混合 NE 是 2/3。项目三 稳定匹配：同一个 DA 函数换个方向就得到 $\mu_S$ 和 $\mu_C$；⭐⭐ T5 是灵魂 —— 46656 个 $n=3$ 实例里学生端成功谎报 0 个、学校端 864 个（1.9%），你亲手把 Roth 1982 搜了出来。项目四 公平分配实验室：Round-Robin、嫉妒图（破环后两人从 5、5 变 10、40，两条边同时消失）、MNW（乘积 40 且完全 EF）；⭐⭐ T5 统计 500 个随机实例：EF1 那一列两个都 100%，PO 那一列裂开 —— RR 约 81%、MNW 100%。项目五 Shapley：煎饼博弈 (6,4,6)、手套博弈 (4/6,1/6,1/6)，⭐ 行和 assert 是最好的检错手段；手套博弈的 Core 只有 (1,0,0)，Shapley 落在 Core 外面 —— 公平和稳定在这里分家。⭐ 挑战 A 拥塞博弈：核心是 T3 —— 每步打印那个人省下的成本、$\Phi$ 的降幅和当前 $\Phi$，验证前两者一分不差地相等；⚠️ 开局 Φ=550005 而总成本=600000（Φ 不是总成本），149 步收敛到 (0,5000,5000)；Braess 65 → 80、PoA ≈ 1.231；⭐⭐ T6 改成加权拥塞博弈，最佳响应动态当场绕圈，存在性保证塌掉。⭐⭐ 挑战 B 操纵率实验室把 G–S 变成一张表：216 个轮廓上 Borda 23.6%、Plurality 16.7%、IRV 与 Copeland 各 11.1%，独裁恰好 0% —— 那个唯一出口，你在自己的表里看到它是唯一一个 0；换成单峰域后中位选民规则 0/64，⚠️ 但这叫换了更小的输入域，救的是特定规则不是所有规则（同一个域上 Plurality 反而涨到 18.8%）。

下一节 👉 附录A-速查.md