25 · Condorcet 与锦标赛解

⏱ 40 分钟 ｜ ⭐⭐ 「多数人想要的」这件事，可能根本不存在

🎯 一句话

换一种数票方式：不看名次，只看每两个候选项单挑谁赢 —— 这给出上一章那份选票的第六个答案，也暴露出一个更深的麻烦：多数关系可能成环。

⚔️ 一、多数关系与多数图

对两个候选项 $x, y$，如果把 $x$ 排在 $y$ 前面的人更多，就说 $x$ 在多数意义下胜过 $y$：

$$x \succ^{maj} y \iff |\{i\in N: x\succ_i y\}| \;>\; |\{i\in N: y\succ_i x\}|$$

把每个候选项画成一个点，$x \succ^{maj} y$ 就从 $x$ 画一条箭头指向 $y$，得到的有向图叫多数图。记 $D(x)=\{y \mid x\to y\}$ 为 $x$ 直接打败的那些人。

⭐ 选民人数是奇数时不会有平局，多数图就是一个锦标赛（tournament） —— 完全（任意两点之间有一条边）且反对称（不会互指）的有向图。

Condorcet 赢家：打败所有其他候选项的那一个。它未必存在，但存在时一定唯一。

⭐ 一条规则如果「只要存在 Condorcet 赢家就一定选它」，就叫 Condorcet 一致（Condorcet extension）。这是评价投票规则最常用的一条标准。

🔨 二、回到那份 14 人选票

上一章那份选票原样搬过来：5 人 $a\succ c\succ b\succ d\succ e$、4 人 $e\succ b\succ c\succ d\succ a$、3 人 $d\succ c\succ b\succ e\succ a$、2 人 $b\succ d\succ e\succ c\succ a$。

手算套路：$m=5$ 就有 $\binom52=10$ 对，一对一对数。 例如 $b$ 对 $c$：把 $c$ 排在 $b$ 前面的是第 1 组（5 人）和第 3 组（3 人）共 8 人，另外 6 人相反 → $c$ 胜。

整理出来是一条完全传递的链：

$$c \;\to\; b \;\to\; d \;\to\; e \;\to\; a$$

⭐⭐ $c$ 打败了所有人 —— 它是 Condorcet 赢家，这就是这份选票的第六个答案。 而 $a$ 输给了所有人（0 胜 4 负），却是上一章的 plurality 赢家。

💀 值得停一下的一件事：$c$ 没有任何一个人把它排第一。在 plurality 下它得 0 分、连决选圈都进不去，却在一对一比较里打败了每一个对手。上一章说「plurality 看不见共同次选」，这就是那句话的完整证据。

⚠️ 三、Borda 选 b、Condorcet 是 c —— 这不是巧合

定理（Fishburn 1973）：候选项 ≥ 3 时，没有任何位置计分规则是 Condorcet 一致的。

一个 17 人的反例（6 人 $a\succ b\succ c$，3 人 $c\succ a\succ b$，4 人 $b\succ a\succ c$，4 人 $b\succ c\succ a$）：

• 三者得分：$a: 6s_1+7s_2+4s_3$，$b: 8s_1+6s_2+3s_3$，$c: 3s_1+4s_2+10s_3$
• 于是 $\text{score}(b)-\text{score}(a) = 2s_1-s_2-s_3 \ \ge\ 2s_1-s_1-s_3 = s_1-s_3 \;>\;0$

⭐ 不管打分向量怎么选，$b$ 永远压过 $a$。 但 $a$ 才是 Condorcet 赢家（$a$ 以 9:8 胜 $b$、10:7 胜 $c$）。

⭐ 所以「Borda 没选中 Condorcet 赢家」不是 Borda 的毛病，是整个计分规则家族的结构性限制。 看名次的规则和看对决的规则，本来就在测量不同的东西。

🔄 四、Condorcet 悖论：多数关系会成环

Condorcet 赢家可能根本不存在。最短的例子只要 3 人 3 候选：

逐对手算：

• $a$ 对 $b$：1 号和 3 号都把 $a$ 放前面 → $a$ 以 2:1 胜
• $b$ 对 $c$：1 号和 2 号 → $b$ 以 2:1 胜
• $c$ 对 $a$：2 号和 3 号 → $c$ 以 2:1 胜

$$a \to b \to c \to a$$

⭐⭐ 多数关系成了一个环，没有 Condorcet 赢家。

⚠️ 这里最容易误读的一点：环不是因为选民不理性。三个人的偏好都是完全传递的线性序，一点毛病没有。 是「多数」这个聚合操作本身把传递性弄丢了。「多数人偏好 $x$ 胜过 $y$」这个关系，不是一个序。

⭐ 这是整个社会选择理论的起点，也是第 26 章 Arrow 定理的直接前身 —— 既然多数关系自己就不传递，那么「要求输出一个传递的排序」这个看起来天经地义的要求，其实已经是一个很强的约束了。

🏆 五、没有 Condorcet 赢家时：锦标赛解

多数图成环时怎么选？锦标赛解是一族答案：输入一个锦标赛，输出一个「赢家集合」（所以它们是 SCC 不是 SCF）。

⚠️ 那份 14 人选票在这里帮不上忙 —— 它的多数图是一条传递的链，四个锦标赛解全都缩成 $\{c\}$，看不出任何区别。所以下面换一份 5 人 4 候选的选票（有环）：

六对全算完（5 人是奇数，不会平）：$a\to b$（3:2）、$a\to c$（4:1）、$b\to c$（3:2）、$b\to d$（3:2）、$c\to d$（3:2）、$d\to a$（3:2）。

① Copeland：数胜场

$x$ 的 Copeland 分就是它的出度（打败了几个人）。分数最高者当选，是 Condorcet 一致的。

出度：$a{:}2$（打 b、c），$b{:}2$（打 c、d），$c{:}1$（打 d），$d{:}1$（打 a）。⭐ $CO=\{a,b\}$。

② Top Cycle：能沿箭头走到所有人

$x$ 属于 Top Cycle，如果沿有向边能走到其他每一个候选项（步数不限）。也是 Condorcet 一致的。

本例四个点都能走到其余三个（例如 $c\to d\to a\to b$），⭐ $TC=\{a,b,c,d\}$ —— 全都进了。 这暴露了 Top Cycle 的毛病：它常常太宽，等于没筛。

③ Uncovered Set：两步之内能走到所有人

先定义覆盖：$x$ 覆盖 $y$，如果 $x\to y$ 并且 $D(y)\subseteq D(x)$ —— 人话是「$x$ 不但打赢了 $y$，而且 $y$ 打赢的人 $x$ 也全都打赢了，$y$ 在任何意义上都不比 $x$ 强」。

没有被任何人覆盖的候选项组成 Uncovered Set $UC(T)$，它的成员也叫 kings。等价刻画（更好用）：⭐ $x\in UC$ 当且仅当 $x$ 能在至多两步内走到其他每一个候选项。

逐个验：

⭐ $UC=\{a,b,d\}$。$c$ 被 $b$ 覆盖了：$b\to c$，而 $c$ 打败的 $\{d\}$ 也在 $b$ 打败的 $\{c,d\}$ 里。

④ Banks Set：最大无环子图的顶点

取一个顶点导出子图，要求它无环（也就是一个传递的小排名），并且极大（再加任何一个点就出环）。这个子图的第一名就是一个 Banks 赢家。

本例的极大无环子图有三个：$\{a,b,c\}$（$a\succ b\succ c$，顶点 $a$）、$\{b,c,d\}$（$b\succ c\succ d$，顶点 $b$）、$\{a,d\}$（$d\to a$，加 $b$ 或 $c$ 都会出环，顶点 $d$）。⭐ $BA=\{a,b,d\}$。

⚠️ Banks 的计算很割裂：找出一个 Banks 赢家很容易（贪心地往集合里加点，只要不成环就加，最后取顶点）；但判定某个给定候选项是不是 Banks 赢家是 NP-完全的（Woeginger 2003）。

📊 包含关系

$$BA(T)\subseteq UC(T),\qquad CO(T)\subseteq UC(T),\qquad UC(T)\subseteq TC(T)$$

本例：$CO=\{a,b\}\subsetneq UC=BA=\{a,b,d\}\subsetneq TC=\{a,b,c,d\}$ ✓

两条证明都很短：UC ⊆ TC 因为「两步内到达所有人」显然蕴含「能到达所有人」。CO ⊆ UC 用反证 —— 若 Copeland 赢家 $x$ 不在 $UC$ 里，就存在某个 $y$ 是 $x$ 两步也够不着的，于是 $D(y)\supseteq\{x\}\cup D(x)$，$y$ 的胜场比 $x$ 还多，矛盾。

🧰 六、另外三条 Condorcet 一致的规则

⚠️ 注意这里出现的模式和第 23 章一模一样：概念定义得很干净，计算复杂度却各不相同（Copeland 秒算、Banks 判定 NP-完全、Kemeny NP-难）。「哪条规则更合理」和「哪条规则算得动」是两个独立的问题。

🔗 这一章连到哪里

✅ 检查点

1. 多数关系怎么定义？什么时候多数图是一个锦标赛？
2. 那份 14 人选票的 Condorcet 赢家是谁？$a$ 的战绩是几胜几负？$c$ 有多少人把它排第一？
3. Fishburn 定理说了什么？那个 17 人反例里，为什么 $b$ 在任何打分向量下都压过 $a$？
4. 写出最短的 Condorcet 悖论例子并手算出环。为什么说「环不是因为选民不理性」？
5. Copeland 分是什么？例子里 $CO$ 是多少？
6. 「$x$ 覆盖 $y$」的定义是什么？等价的两步刻画是什么？例子里谁被谁覆盖了？
7. Banks 赢家怎么定义？例子里的三个极大无环子图分别是什么？Banks 在计算上割裂在哪？
8. 三个包含关系是什么？例子里的三个集合验证一遍。
9. Kemeny、Black、Nanson 各是怎么做的？

🛑 可以停在这里

⚡ 走神救援

⭐换一种数票方式：只看两两单挑。 $x\succ^{maj}y$ 当且仅当把 $x$ 排前面的人更多；画成有向图叫多数图，选民人数为奇数时它是一个锦标赛（完全 + 反对称）。Condorcet 赢家 = 打败所有人的那一个，未必存在但存在时唯一；「只要存在就一定选它」的规则叫 Condorcet 一致。🔨回到上一章那份 14 人选票：10 对全算完得到一条完全传递的链 $c\to b\to d\to e\to a$，⭐⭐Condorcet 赢家是 $c$ —— 这是同一份选票的第六个答案（前五个是 plurality 的 a、2-approval 的 c、3-approval 的 b、Borda 的 b、两轮决选的 e、IRV 的 d）。💀而 $a$ 是 0 胜 4 负却拿了 plurality 冠军；$c$ 一个第一名都没有，却赢了每一场单挑。 ⚠️Borda 选 b、Condorcet 是 c 不是巧合：Fishburn 1973 —— 候选项 ≥3 时没有任何位置计分规则是 Condorcet 一致的，17 人反例里 $\text{score}(b)-\text{score}(a)=2s_1-s_2-s_3\ge s_1-s_3>0$，与打分向量无关。⭐⭐Condorcet 悖论：3 人 3 候选（$a\succ b\succ c$ / $b\succ c\succ a$ / $c\succ a\succ b$），三场都是 2:1，得到环 $a\to b\to c\to a$，没有 Condorcet 赢家。⚠️环不是因为选民不理性 —— 三个人的偏好都是完全传递的线性序，是「多数」这个聚合操作把传递性弄丢了，这正是第 26 章 Arrow 定理的前身。成环时用锦标赛解（输出的是集合不是单个赢家）。在一个 5 人 4 候选的例子（$a\to b,\ a\to c,\ b\to c,\ b\to d,\ c\to d,\ d\to a$，环是 $a\to b\to d\to a$）上：Copeland 数出度 → $\{a,b\}$；Top Cycle 是「沿箭头能走到所有人」→ $\{a,b,c,d\}$ 全都进了，太宽等于没筛；Uncovered Set 要求两步之内到所有人（等价于「没被任何人覆盖」，$x$ 覆盖 $y$ 指 $x\to y$ 且 $D(y)\subseteq D(x)$）→ $\{a,b,d\}$，$c$ 被 $b$ 覆盖；Banks 取极大无环导出子图的第一名 → $\{a,b,c\}$给 a、$\{b,c,d\}$给 b、$\{a,d\}$给 d，即 $\{a,b,d\}$。⭐包含关系 $BA\subseteq UC$、$CO\subseteq UC$、$UC\subseteq TC$，本例 $\{a,b\}\subsetneq\{a,b,d\}\subsetneq\{a,b,c,d\}$。⚠️Banks 割裂得厉害：找一个赢家贪心就行，判定某个候选项是不是赢家却是 NP-完全（Woeginger 2003）；Kemeny 也是 NP-难，Black（没 Condorcet 赢家就用 Borda）和 Nanson（反复删 Borda 分低于平均的）则是两种缝合方案。⭐和第 23 章同一个模式：「哪条规则更合理」和「哪条规则算得动」是两个独立问题。

下一节 👉 26-不可能定理.md