🏠 总目录📚 本教程 27 · 实战与挑战项目 ← →

博弈论与集体决策 · 27 · 原章导读

先验证哪一种规则:投票、均衡、匹配还是分配?

各项目检验的对象不同。先固定实验口径,再选一个项目,按原起步任务、继续任务和通关数字逐步运行。

读后可检查:能选出一个可执行项目,并区分算法输出与性质检验。

📑 本页目录(点开跳转)

27 · 实战与挑战项目

⏱ 项目 3 小时 – 2 天 | 挑战 2 – 4 天 | 原预计,仅供参考;可以分次完成。

🎯 先选一个项目,不必一次做完

这一页把前面各章的小例子变成可以运行、可以核对的实验。 每个项目独立选做,不是从 T1 一口气做到全页最后。

刚开始写 Python,建议先选项目一:投票或项目二:纯策略均衡。先运行已有代码、核对一张表,再补功能。

每张任务卡都有动作与完成标志。勾选只是记录你的核对进度,不代表网站替你运行了测试。

🧰 开工前:先固定实验口径

① 小例子先行,但不是所有项目都零依赖。

投票、匹配和小规模枚举可以只用 Python 标准库。一般线性规划、SHAP 对账等扩展可能需要额外库;不要求 GPU,也不要求下载大型数据集。

② 先对输入、规则和计算,再对书上的数字。

出现差异时,先检查数据是否相同、平局如何处理、代码和教材是否有误。不能因为“书上这么写”就认定一定是读者写错。

③ 有理数能精确算就精确算;近似计算注明容差。

Fraction(2, 3) 能精确表示 $2/3$。浮点求解器仍可使用,但应把误差容限写进报告,不要把近似相等误判为不同。

还有两类复现设置不能漏:

  • 平局规则:候选项、物品、源节点、更新玩家如何排序,都可能影响具体路径或结果。
  • 随机性:随机估值、随机博弈、抽样轮廓、随机独裁都涉及随机过程;保存种子与生成方法,最好同时保存实际输入。

🥉 项目一:投票规则对比器(3 – 5 小时)

要回答的问题:同一份偏好,换规则为什么会换赢家?

输入是下面的 14 张严格排序票。输出包括计分、淘汰记录、两两对决和赢家集合。

前置:24 · 投票规则、25 · Condorcet 与锦标赛解;IIA 对照读第 26 章。

起步任务:先跑通常见规则

  • 把打分向量作为参数,实现 Plurality、2-approval、3-approval、Borda。

    完成标志: 下方四行计分一致;Borda 所有人分数之和是 140。

  • 两轮决选保留首轮前两名;IRV 每轮只淘汰一个最低票者,再把票转给尚未淘汰的最高偏好。

    完成标志: 保存每轮所有候选人的票数,包括零票者,核对下方淘汰顺序。

  • 数出每一对候选人的支持人数。只有严格击败其他所有人,才返回 Condorcet 赢家;否则返回 None。

    完成标志: 本例返回 c;能从对决表检查 c 的每一场胜利。

继续任务:加入集合解与性质测试

  • 实现 Copeland、Top Cycle、Uncovered Set。先限定为每对都有严格多数胜者的锦标赛。

    完成标志: Copeland 取最大出度集合;Top Cycle 用可达关系;Uncovered Set 用“最多两步到达所有其他点”。出现平票时提示超出此版本,而不是随意补一条边。

  • 用三张票:$a\succ b\succ c$、$b\succ c\succ a$、$c\succ a\succ b$。

    完成标志: condorcet() 返回 None,T4 的三个集合都为 $\{a,b,c\}$;不要误报程序没有结果。

  • 用第 26 章的五人 Borda 例子,只移动 c,不改变任何人对 a、b 的相对顺序。

    完成标志: 得分从 (a 6, b 7, c 2) 变为 (a 6, b 4, c 5),集体对 a、b 的顺序翻转。这里检验的是社会排序版 IIA。

先运行:三项基础输出

这段独立代码只实现位置计分与 Condorcet 检查;它不是 T1–T6 的完整答案。

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、b、c、d、e:同分选优先者获胜或晋级;IRV 最低票并列时,淘汰优先级最低者。第 25 章的三个集合解先返回集合,不强制选一个人。

规则 中间结果 赢家
Plurality a 5;b 2;c 0;d 3;e 4 a
2-approval a 5;b 6;c 8;d 5;e 4 c
3-approval a 5;b 14;c 12;d 5;e 6 b
Borda a 20;b 36;c 34;d 27;e 23 b
两轮决选 a 与 e 决选,5 : 9 e
IRV c → b → e;最后 d 9 : a 5 d
Copeland a 0;b 3;c 4;d 2;e 1 c

IRV 首先淘汰的是零票的 c。 旧表跳过了这一点,把 c 放到后面,虽然最终赢家碰巧没变,过程仍然是错的。

同一候选项可以在一种规则下获胜、在另一种规则下输掉所有两两对决:本例 Plurality 赢家 a 的出度就是 0。

验收标准 · 七条规则对上结果,并能解释“无 Condorcet 赢家”不是报错。T6 用来进一步区分规则结果与规则性质。

🥉 项目二:纳什均衡求解器(1 天)

要回答的问题:哪些策略组合没有单人偏离的收益?

前置:10 · 支配策略、11 · 纳什均衡、12 · 混合策略、13 · 零和。

输入是同样大小的两张收益矩阵 U1、U2;行列索引对应同一组行动。先处理小矩阵,输出策略而不只是收益。

起步任务:纯策略与严格劣势

  • 每列找行玩家的最大收益,每行找列玩家的最大收益,交集是纯 NE;并列最大值全部保留。

    完成标志: 下面三个独立测试分别得到一个、两个、零个纯 NE。

  • 先实现“被另一条纯策略严格支配”的版本,保留原始行列索引。随机生成 1,000 个 3×3 整数收益博弈,固定种子并保存输入。

    完成标志: 比较删前、删后的纯 NE 集合,确认原纯 NE 未被误删;同时复现第 10 章四步删除。这是实现测试,不是靠 1,000 次测试证明一般定理。

  • 令 p 是行玩家选第一行的概率,q 是列玩家选第一列的概率。用列玩家无差异解 p,用行玩家无差异解 q。

    完成标志: 检查概率在 [0,1] 内,再核对最佳响应。分母为 0、边界解和退化情况单独报告;不能只套一个除法公式。

继续任务:混合策略与零和对照

  • 先在石头剪刀布上,枚举双方使用哪些行动、求无差异方程。

    完成标志: 支撑内概率为正且和为 1;支撑内收益相等;支撑外没有更高收益。奇异方程不能直接视作“无均衡”,通用退化处理是扩展项。

  • 对零和行收益矩阵,比较“各行最小值中的最大值”与“各列最大值中的最小值”。

    完成标志: 相等时给出鞍点;不相等时说明纯策略保底不足,需要混合策略,而不是宣称没有 NE。

  • 在零和博弈中配对双方的最优混合保底策略,再与性别之争比较。

    完成标志: 零和组合满足 NE;性别之争中行玩家保底 p=1/3,而其内点混合 NE 为 p=2/3。T5 的纯策略行最小法不能直接当作混合求解器。

先运行:只检查纯策略

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

🎯 该跑出来的数字

输入 核对结果
第 11 章 3×3 唯一纯 NE 是行动 (c,y),对应收益 (3,5);(a,x)、(b,z) 只有单边最佳响应
性别之争 两个纯 NE;内点混合 p=2/3、q=1/3,两人期望收益均为 2/3
罚球 / 石头剪刀布 无纯 NE;混合策略分别是 (1/2,1/2) 与 (1/3,1/3,1/3)
第 10 章 3×3 C 支配 R;M 支配 D;C 支配 L;M 支配 U,剩 (M,C),收益 (3,3)
第 13 章零和 3×3 行最小 (1,2,0),列最大 (3,2,6),鞍点 (b,y),值为 2

验收标准 · 能区分“行动组合”“对应收益”和“混合概率”;不把无纯 NE 当作没有均衡。

🥈 项目三:稳定匹配求解器(1 天)

要回答的问题:谁提案会影响稳定匹配,谁又能从谎报中受益?

本项目基础版限定:两侧各 n 人、一对一、完整严格排序、所有配对都可接受。前置:17 · 稳定匹配;18 · TTC是扩展。

起步任务:得到匹配并检查稳定

  • 将两侧的偏好字典传给同一个延迟接受函数。学生提案叫 SPDA,学校提案叫 CPDA。

    完成标志: 两个方向都得到一对一完整匹配;输出统一转换成“学生 → 学校”,避免反向字典读错。

  • 对每个未配在一起的 (学生,学校),检查双方是否都更喜欢对方而非当前搭档。

    完成标志: DA 的结果没有阻挡对;故意构造不稳定匹配后,检查器能列出具体阻挡对。

  • 在 n≤5 的小实例上枚举 n! 个双射,调用 T2 筛选;先做下方三人循环例。

    完成标志: 找到三个稳定匹配,分别让学生取得第 1、第 2、第 3 志愿;逐个学生比较,SPDA 不差于其他稳定结果。

继续任务:检查这个机制的谎报空间

  • 使用第 17 章例一,而不是下面的循环例。让 c₁ 把真实顺序 s₁、s₂、s₃ 报成 s₁、s₃、s₂。

    完成标志: c₁ 从真实第 2 名 s₂ 改配到真实第 1 名 s₁;其余人的报告保持不变。

  • 三名学生加三所学校,各有 6 种完整排序,共 $6^6=46,656$ 个真实偏好实例。固定 SPDA,逐人替换一份报告,用该人的真实偏好评价新搭档。

    完成标志: 分别统计“至少一名学生能改善”和“至少一所学校能改善”的实例数。每个实例在每一侧最多记一次;并保存一个成功谎报作为证据。

  • TTC 保留房屋的初始所有权,按“人指最喜欢的剩余房、房指主人”找环成交。多对一先使用固定配额与学校对学生的严格优先序。

    完成标志: TTC 复现第 18 章五人结果;若拆学校为座位,明确座位共享优先序、学生对同校座位的固定排序,以及学校采用响应式偏好。不能把任意学校组偏好直接拆成座位。

先运行:三人循环例

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 志愿

🎯 该跑出来的数字

数据与任务 核对结果
第 17 章例一 SPDA (s₁,c₂)、(s₂,c₁)、(s₃,c₃);s₃ 被拒 2 次,总计 5 次提案
上方循环例 SPDA 学生全拿第 1 志愿,学校全拿第 3 志愿
上方循环例 CPDA 学校全拿第 1 志愿,学生全拿第 3 志愿
循环例穷举 3 个稳定匹配,学生名次分别为 (1,1,1)、(2,2,2)、(3,3,3)
T4 谎报 c₁ 从 s₂ 换成 s₁,即真实第 2 名升为第 1 名
T5:SPDA,46,656 个实例 学生端可操纵实例 0;学校端 864,约 1.85%
T6:第 18 章 TTC 三轮成交,房屋结果 (o₂,o₁,o₃,o₅,o₄)

0 / 864 只是在这个有限输入域上测试 SPDA。 找到 864 个实例说明 SPDA 的接收方可能获益,并不等于穷举了所有稳定匹配机制。

Roth 的不可能性结论量化的是所有满足稳定性的机制,范围比这份程序大得多。Roth 原论文摘要

验收标准 · 匹配无阻挡对,两个提案方向能对上;能说明枚举结果支持什么、没有证明什么。

🥈 项目四:公平分配实验室(1 – 2 天)

要回答的问题:EF1 与帕累托最优 PO,是不是同一回事?

基础版采用非负、可加估值的不可分好物品,无额外配额,每件只给一个人。前置:19 · 公平判据、20 · 分配算法;支付扩展读第 21 章。

起步任务:算法与判据分开写

  • 固定人物顺序,轮流拿剩余物品中自己最看重的一件;同分按固定物品优先序选择。

    完成标志: 每件恰好分一次,复现下表的两种平局分支。

  • 实现 is_ef、is_ef1、is_prop1、is_po。检查 EF1 时,从对方那堆里去掉在我眼里最值钱的一件;空堆不嫉妒。

    完成标志: 四个函数分别返回结论与见证。PO 的反例是一份让所有人不变差且至少一人变好的可行重分配;不能只比较总效用。

  • 找无入边节点 source 发一件物品;出现有向环时沿环轮换整堆,直到无环,再发下一件。

    完成标志: 每次消环后嫉妒边总数严格下降,EF1 保持。发新物品可能增加边数;个别箭头也可能因换主人而改向。

继续任务:精确最优与随机实验

  • 枚举 n^m 份完整分配。非负估值下先最大化正效用人数,再最大化正效用者的效用乘积;不要让乘积为 0 抹掉所有差别。

    完成标志: 两人四物例得到全局最大乘积 40;调用独立判据验证 EF1 与 PO。近似候选解不能直接继承精确 MNW 定理。

  • 比较 Round-Robin 与精确 MNW。设 n=3、m=6,各物品估值独立均匀取整数 1–10;先用 random.Random(0),按“实例、人物、物品”顺序调用 randint(1,10)。

    完成标志: 两算法使用同一批输入;给出 EF1、PO 的通过数和分母。保存输入后,再换种子测试,不要求凑出某个预设百分比。

  • 先对小例子枚举分区计算 MMS,再做第 20 章“先处理大件、再轮流拿”的 1/2-MMS 方法。

    完成标志: 验证个人价值不低于自身 MMS 的一半。支付另按第 21 章定义带权嫉妒图:Bellman–Ford 检查的是取负边权后的负环;无正权环时才用最长路补贴,并逐条核对支付不等式。

🎯 该跑出来的数字

输入 核对结果
第 20 章 RR,人物顺序 1、2 2 号第二轮在 g₃、g₄ 上并列,各值 5
并列选 g₄ 最终自身价值 (135,45),EF1
并列选 g₃ 最终自身价值 (140,45),也 EF1
RR 不保 PO 的两物反例 v₁=(1,1)、v₂=(1,0),若 1 号先取第一件,效用 (1,0);交换后 (1,1)
第 20 章两人消环 自身价值从 (5,5) 到 (10,40),边数从 2 到 0
第 20 章 MNW X₁={o₁,o₂}、X₂={o₃,o₄};8×5=40,且完全 EF

PROP1 另有口径: 看自己是否已达到总价值的 1/n;否则,能否从外部加上一件物品达到。不要把“从别人堆里去掉一件”的 EF1 实现直接复制过去。

T5 参考运行还需固定:人物按 1、2、3,物品同分取编号最小;MNW 按完整分配的字典序枚举并保留首个最优。PO 穷举全部 $3^6=729$ 份分配核对。

500 例,种子 0 EF1 PO
Round-Robin 500 / 500 381 / 500(76.2%)
精确 MNW 500 / 500 500 / 500

这是上述生成器的一次可复现结果,不是普遍的 76.2% 定律。旧文“约 81%”未给出完整设置,不能作为通关硬指标。

验收标准 · 在反例上区分 EF1 与 PO,说明统计结果受输入分布与规则影响。理论保证来自前提与证明,不来自样本里刚好 100%。

🥈 项目五:Shapley 值计算器(1 天)

要回答的问题:按边际贡献分,是否一定不会被小联盟反对?

前置:22 · 联盟与核心、23 · Shapley 值。先用三人合作博弈的完整价值表,取 $v(\varnothing)=0$。

起步任务:两种计算路径互相核对

  • 从 n=3 开始,按每个加入顺序计算新增价值并平均。小规模可扩到 n≤10,但 $10!=3,628,800$,不承诺“秒级”。

    完成标志: 输出每个排列的边际贡献;记录规模、价值函数计算次数和耗时。

  • 每个排列的增量之和应为 $v(N)-v(\varnothing)$;本项目空联盟为 0,才简写为 $v(N)$。

    完成标志: 对精确分数用相等断言;浮点版声明容差。行和正确是必要自查,不代表每个人的归因都算对。

  • 实现权重 $|S|!(n-|S|-1)!/n!$,与排列版比较;不是把每个联盟等权平均。

    完成标志: 所有成员的结果逐项相同,并说明两个阶乘分别计数什么。

  • 取联盟价值为内部边权之和的图博弈,比较枚举与 $\phi_i=\frac12\sum_{j\ne i}w(\{i,j\})$。

    完成标志: 每条边权各有一半给两端;换图重算仍与枚举一致。

继续任务:贡献、稳定与模型解释

  • 三人时用第 22 章三个下限、三个上限和总额约束;一般 n 枚举联盟约束,检查候选分配是否满足。寻找可行点可另用线性规划库。

    完成标志: 返回可行分配,或具体违反的联盟约束;不能只检查每个人非负。

  • 在同一价值表上同时算 Shapley、Core、Banzhaf 关键次数。Banzhaf 要分别输出绝对指数和归一化指数。

    完成标志: 对上下面的数值,指出哪个联盟能阻挡 Shapley;不要把“归一化后和为 1”说成不满足总额。

  • 安装 shap、scikit-learn,训练一个 3–4 特征的小回归树。固定待解释样本、背景样本和输出为预测值;枚举同一“缺失特征用背景替换并平均”的联盟价值。

    完成标志: 与显式设置 interventional、相同背景及输出空间的 TreeExplainer 逐项比较。检查基线加归因和等于该输出;先对齐解释问题,不能拿不同缺失定义硬比。

🎯 该跑出来的数字

输入 核对结果
第 23 章煎饼博弈 Shapley (6,4,6),总和 16
手套博弈 Shapley (2/3,1/6,1/6);Core 只有 (1,0,0)
阻挡证据 1、3 合计只拿 5/6,小于合作价值 1,因此可重新分配让两人都更好
第 22 章 X 扫描 单点全 0,v(12)=50、v(13)=70、v(23)=X、v(N)=100;Core 非空条件为 X≤80

手套例的 Banzhaf 结果,分开看:

口径 三人结果 总和
关键次数 η (3,1,1) 5
绝对 Banzhaf:除以 $2^{3-1}$ (3/4,1/4,1/4) 5/4
归一化 Banzhaf:除以关键次数总和 (3/5,1/5,1/5) 1

绝对指数不保证总和为 1;归一化指数本来就是缩放到 1。两者与 Shapley 的区别在于平均权重,不只是表中数字不同。

T7 中,base_value + sum(shap_values) 对应的是选定输出空间下的预测。背景数据、特征依赖假设或模型输出变了,就可能不再是同一个归因问题。TreeExplainer 官方说明

验收标准 · T1 与 T3 对上,T6 能用具体联盟说明“贡献公理”不等于“联盟稳定”。工程解释边界见模型上线之后 10。

🥇 挑战 A:拥塞博弈实验室(2 – 3 天)

难度 ★★★☆☆。要回答的问题:个人在改善,哪个总量一定跟着下降?

前置:15 · 拥塞博弈与势函数。基础实验使用有限、无权、每次一人移动的拥塞博弈,不允许同成本下不断换路。

起步任务:把一次单人移动记清楚

  • 记录资源、每人的可选资源子集、每种资源的成本函数 c(x,k)。先用三条互斥路线,再扩到共享路段。

    完成标志: 能从一份完整策略组合重算每个资源的人数与每个玩家的成本。

  • 一次选一个玩家,暂时从旧资源移除,再加入候选资源,重算新成本。原、新方案共有的资源人数不变。

    完成标志: 只在新成本严格更低时移动;新加入资源用“其他使用者 + 1”。不要给共有资源重复加 1。

  • 统一定义为“新值减旧值”:记录个人成本变化、势函数变化、移动后的势函数。

    完成标志: 每次严格改善满足 $\Delta_{\rm cost}=\Delta_\Phi<0$;若改记“节省量”,两者都取相反数。不能与第 15 章的符号约定混用。

继续任务:均衡、效率与边界

  • 从 (10,000,0,0) 出发,一次只移动一个人。记录更新次序,最后检查所有可行的单人偏离。

    完成标志: 验证 (0,5,000,5,000) 是纯 NE,每人 50 分钟。一次移动 100 人不再是本实验的单人动态,不能套用 T3 的同一等式或要求“149 步”。

  • 分别求旧网络、新网络的均衡;然后在新网络本身中最小化总耗时,不能直接拿旧网络均衡当分母。

    完成标志: 对上“65 → 80”的改造前后比较,并与下方 PoA 计算区分开。

  • 把人数改成玩家权重之和,先明确每人的成本定义,再检查原来的 Rosenthal 记账公式是否仍适用。

    完成标志: 写出哪一步等式不再能直接套用。若找循环,给出具体成本函数、权重、完整状态循环,并逐步验证严格改善;没找到不能判定一定收敛,找到循环也不能单凭它断言没有纯 NE。

先运行:势函数与总耗时是两回事

这段只计算两个状态的数值,不是在模拟动态。成本用精确分数表示,显示时转换为小数。

from fractions import Fraction

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 + Fraction(k, 1000), "b": 40 + Fraction(k, 500), "c": Fraction(k, 100)}[x]
for name, s in [("开局", {"a": 10000, "b": 0, "c": 0}),      # 一万人全走高速路
                ("均衡", {"a": 0, "b": 5000, "c": 5000})]:   # 第 15 章算出的均衡
    print(name, "Φ =", round(float(phi(cost, s)), 2), " 总成本 =", round(float(total(cost, s)), 2))

🎯 该看到的现象

状态 势函数 Φ 总耗时
全在 a:(10,000,0,0) 550,005 600,000
均衡:(0,5,000,5,000) 350,030 500,000

均衡时移去空 a 路会耗时 50.001,移到另一个已有 5,000 人的 b/c 路也会更慢。稳定性由偏离检查确认,不由“看起来负载均匀”确认。

若按 a、b、c 选首个有改善空间的来源,每次换到移动后成本最低的路,同分按 a、b、c 优先,本例从全 a 到该均衡需 10,000 次单人移动。换调度规则后不要把步数当作通用答案。

加权不等于一定绕圈。 一般加权模型不再继承无权模型的通用保证,但例如仿射成本的标准加权拥塞博弈仍有纯 NE 保证。加权拥塞博弈原论文摘要

Braess:比较对象必须相同

第 15 章网络:4,000 辆车,两个可变路段耗时为各自流量 / 100,两个外侧固定路段耗时 45,新通道耗时 0。

比较对象 每人平均耗时
旧网络均衡:上下各 2,000 65
新网络均衡:全走新通道 80
新网络集中最优:上下各 1,750,新通道 500 64.6875

因此 $80/65\approx1.231$ 是改造前后的均衡耗时比;新网络的 PoA 为 $80/64.6875=256/207\approx1.237$。

64.6875 是怎样算出来的?

令 u、l、z 分别是上、下、新通道路线的车数,总数为 4,000。共享可变路段的负载分别是 u+z、l+z:

$$C=\frac{(u+z)^2+(l+z)^2}{100}+45(u+l)$$

固定 z 后,平方和在 u=l=(4,000−z)/2 时最小。代入:

$$C(z)=\frac{(4000+z)^2}{200}+45(4000-z)$$

对 z 求导,最小点为 z=500,因此 u=l=1,750;此时总耗时 258,750,除以 4,000 得 64.6875。

这里所有最优路线车数都是整数,所以这份分配对逐车分配也可行。

验收标准 · T3 的变化量逐步相等;能区分个人成本、势函数、系统总成本,以及“改造前后比”与 PoA。

🥇 挑战 B:操纵率实验室(2 – 4 天)

难度 ★★★★☆。要回答的问题:指定规则在指定输入域里,有多少实例能被单人谎报改变得更有利?

这不是用一张表证明 Gibbard–Satterthwaite。定理覆盖不受限严格偏好域、至少三个候选项、确定的单赢家、满射及非独裁等条件,结论是不存在通用策略防伪;程序只检查你实现的规则和有限规模。先读第 26 章。

起步任务:定义一次成功操纵

  • 三候选、三选民,每人 6 种严格排序,共 $6^3=216$ 个有标号选民的偏好轮廓。

    完成标志: 无遗漏、无重复。每个轮廓权重相同是实验设定,不是真实选民分布的事实。

  • 固定别人报告,让该选民尝试全部合法谎报。按其真实排序比较谎报前后赢家。

    完成标志: 只有严格更喜欢新赢家才算成功;同一轮廓即使有多人、多种成功报告,也只记 1 次。

  • 赢家同分选字母最小者。IRV 每轮淘汰一人,最低票并列时淘汰字母最大者;Copeland 对决赢 1 分、平 1/2 分、输 0 分。

    完成标志: 输出每条规则的可操纵轮廓数 / 216,保存至少一个成功见证。改规则再测,而不是只改报告标题。

  • 永远选第 1 名选民报告的第一项。

    完成标志: 结果为 0 / 216;能分别解释决定者和非决定者为何无法靠谎报获得更好结果。

继续任务:扩大规模与改变允许域

  • 全域共有 $24^4=331,776$ 个轮廓,仍可枚举,但每个还要搜索单人谎报;先随机抽 4,000 个有放回样本,保存种子与样本。

    完成标志: 五条规则共用同一批样本,报告样本操纵率及不确定性。不可预设“候选一多,各规则必然单调上升”。

  • 固定候选轴 a<b<c,合法排序为 abc、bac、bca、cba,共 $4^3=64$ 个轮廓;真实偏好与可报偏好都限于这四种。

    完成标志: 中位峰规则在此域是 0 / 64,其他规则按下表核对。只限制真实偏好、却允许任意域外谎报,是另一个实验。

  • 先明确 burying 的识别口径,例如“将真诚结果的赢家下调至最后”,再统计,不把所有成功操纵都叫 burying。

    完成标志: 随机独裁使用与报告无关的固定选人概率;比较真实排序下每个前缀的累计获胜概率,而非只模拟几次抽签就宣称防伪。

🎯 三候选、三选民的枚举结果

按 T3 的完整规则、每个真实轮廓最多计一次:

规则 可被单人操纵的轮廓 占比
Borda 51 / 216 23.6%
Plurality 36 / 216 16.7%
IRV 24 / 216 11.1%
Copeland 24 / 216 11.1%
独裁 0 / 216 0%

Borda 在这张表中最高,不意味着它在所有候选数、选民数和偏好分布下都最容易操纵。

把所有字母优先次序完全反过来时,本次均匀全枚举的总计数仍相同:重新命名候选项建立了对应关系。平局规则能改变具体赢家,但不保证一定改变总比例。

T6 真实偏好与报告均限制为单峰:

规则 可操纵轮廓数 / 64
中位峰规则 0
IRV / Copeland / 独裁 0
Borda 6
Plurality 12(18.75%)

域限制不是让所有规则都自动防伪。 Plurality 在这个缩小的域上仍可操纵;不同分母下的比例也不能当作同一分布中的增减。

旧文给四候选四选民的 Plurality≈33%、Borda≈51%、IRV≈18%、Copeland≈55%,但未提供完整样本与种子。这些旧参考值不再作为应得答案;T5 保留,结果由你的已记录实验产生。

随机独裁的检查口径见第 26 章:概率输出。它改变的是输出类型,不能沿用确定赢家版的判断而不加说明。

验收标准 · 完成一份 216 轮廓的精确表,并留一个成功谎报。扩展结果要说清输入域、报告域、计数单位与随机过程。

📝 报告模板:用正常段落填写

不需要把整份报告塞进代码框。按下面六项填写即可:

  1. 问题与规模:项目名称、想核对的性质、玩家/候选项/物品数量。
  2. 输入与规则:具体数据、偏好或估值来源、平局优先序、更新顺序;随机实验再写种子与生成器。
  3. 与正文对账:章节位置、预期值、实际值;不同之处先查口径。
  4. 反例或边界:保存完整输入、旧结果、新结果及性质检查。
  5. 证据范围:手算复现、有限全枚举、抽样统计还是一般证明,不混写。
  6. 发现与下一步:原以为是什么、观察到什么、还没验证什么。

🔗 这一章连到哪里

✅ 检查点

  1. 哪些基础例子只要标准库?哪些扩展可能需要依赖?
  2. 哪些设置要固定:平局、更新顺序、随机种子分别在哪出现?
  3. 14 人例里七条规则选谁?IRV 为什么先淘汰 c?
  4. 纯 NE 圈法和混合 NE 检查各有什么边界?
  5. 匹配的 0 / 864 在数什么,为什么不是证明 Roth 的全部结论?
  6. EF1 与 PO 有什么不同?随机实验里 100% 能证明一般性质吗?
  7. Shapley 行和要减去什么基线?Banzhaf 哪种口径总和为 1?
  8. 势函数变化的正负号如何约定?PoA 的分子分母属于哪个网络?
  9. 单峰域与随机独裁分别改变哪个前提?
核对答案:不必背百分比
  1. 投票、匹配与小规模精确枚举可只用标准库;通用 LP、SHAP 等扩展可能需要额外库。

  2. RR 和 IRV 等需要平局规则;改进动态需要更新顺序;随机估值、抽样轮廓和随机机制还要说明随机过程。

  3. Plurality a、2-approval c、3-approval b、Borda b、两轮决选 e、IRV d、Copeland c。c 首轮零票,必须最先淘汰;Borda 总分为 140。

  4. 并列最大值全圈。混合策略还要检查概率、归一化、支撑外偏离与退化情况;不能只解一个无差异方程。

  5. 在 46,656 个三对三实例中,至少有一名单人能改善的实例数,按 SPDA 的学生侧与学校侧分别计数;没有枚举所有稳定机制。

  6. EF1 允许去掉别人一件后不嫉妒;PO 排除所有人不变差且一人更好的重分配。样本里 100% 是测试结果,不代替定理。

  7. 一般行和是 $v(N)-v(\varnothing)$。绝对 Banzhaf 不保证和为 1,归一化 Banzhaf 在分母非零时和为 1。

  8. 记新减旧,则严格改善时个人成本与势函数变化都负且相等。PoA 比较同一网络的最坏均衡总成本和集中最优总成本。

  9. 单峰缩小真实偏好与报告域,并固定共同轴;随机独裁输出概率,需按真实前缀概率等随机性质检验。

项目记录与回顾

完成一个项目,就可以把输入、结果表和反例保存下来。未做的扩展保持未勾选,不影响已经完成的部分。

去附录 A核对定义,再回总目录选择下一站。

先记住这四点

  • 先选一个项目,复现一个小例子,再扩展。
  • 固定数据、平局与更新规则;随机实验保存种子和实际输入。
  • 把“运行成功”“小域枚举”“统计结果”和“一般证明”分开。
  • 报告写清性质检查与反例,不只写谁赢了。

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

打卡记录保存在你的浏览器里,首页能看到总进度