多数两两比较若出现循环,怎样选出候选集合?
读后可检查:从多数关系和原选票出发,区分 Condorcet 赢家与不同锦标赛解。
📑 本页目录(点开跳转)
25 · Condorcet 与锦标赛解
⏱ 30 分钟 | 原预计,仅供参考;可以分次读 | ⭐ 两两比较,不一定能排出一条顺序
🎯 一句话
Condorcet 赢家是能在两两多数比较中打败所有对手的候选项。 它存在时很明确,但不保证存在。
这一章先复算上一章的 14 人选票,再看一个三人循环,最后比较“没有全胜者时怎么选”。第一遍可以先读到三人循环,集合定义留到下一次。
⚔️ 一、多数关系:一对一地数票
本章默认每位选民对所有候选项给出无并列的完整排序,每人权重相同,并参与每一对比较。
先问一个具体问题:把 $x$ 排在 $y$ 前面的人,比反过来的人多吗?
记 $N(x,y)$ 为“把 $x$ 排在 $y$ 前面的人数”。多数关系就是:
$$x\succ^{maj}y \iff N(x,y)>N(y,x)$$
这里的 $N(x,y)$ 是票数,不是候选项的得分。若两边人数相等,这一对没有严格多数胜者。
把候选项画成点,画一条从胜者指向败者的箭头,就得到多数图。$D(x)$ 表示 $x$ 直接打败的候选项集合;顺着多条箭头走到,不等于直接打败。
什么时候叫锦标赛?
当任意两个不同点之间恰好有一个方向的边,这个有向图叫锦标赛(tournament)。这里没有自环,也没有两点互指。
在本章的完整严格排序、等权投票条件下,奇数选民足以避免平票;偶数选民也可能恰好没有平票。若允许弃权、并列或不同权重,不能只凭总人数是奇数作保证。
Condorcet 赢家直接打败其余所有候选项,所以至多有一个。
一条规则若在这种赢家存在时只选它,就称为 Condorcet 一致。这个条件本身还没有规定“没有全胜者时怎么办”,因此不是一套完整的选人算法。
🔨 二、回到那份 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$ |
先只算 $b$ 和 $c$:第一组的 5 人、第三组的 3 人把 $c$ 放在 $b$ 前面,总共 8 人。另外 6 人相反,所以 $c$ 以 8:6 胜出。
5 个候选项共有 10 对,完整结果如下。票数按左栏候选项的书写顺序排列。
| 对决 | 票数 | 胜者 |
|---|---|---|
| a : b | 5 : 9 | b |
| a : c | 5 : 9 | c |
| a : d | 5 : 9 | d |
| a : e | 5 : 9 | e |
| b : c | 6 : 8 | c |
| b : d | 11 : 3 | b |
| b : e | 10 : 4 | b |
| c : d | 9 : 5 | c |
| c : e | 8 : 6 | c |
| d : e | 10 : 4 | d |
结果:c 是 Condorcet 赢家,4 胜 0 负。 这张多数图还是传递的:按 c、b、d、e、a 排列,任意靠前者都打败任意靠后者,不只是相邻者之间有边。
反过来,$a$ 是 0 胜 4 负,却因为第一名票数最多,成为上一章的 plurality 赢家。
| 上一章的计票规则或本章的条件 | 这份选票的结果 |
|---|---|
| Plurality | a |
| 2-approval | c |
| 3-approval | b |
| Borda | b |
| 两轮决选 | e |
| IRV | d |
| Condorcet 赢家 | c |
这里不是出现了“第六个不同赢家”。 六种计票规则已经给出 a、b、c、d、e 五个不同答案;Condorcet 检查再次指向 c,与 2-approval 的结果重合。
值得留意的是:没有一个人把 $c$ 排第一,但它能赢得每场一对一比较。第一名票数与“逐对多数胜出”衡量的要求不同。
⚠️ 三、为什么换一套名次分数也不能总找到它?
位置计分规则不保证 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 是全胜者。
- a 对 b:前两组支持 a,共 9 人;另外 8 人支持 b。
- a 对 c:第一组和第三组支持 a,共 10 人;另外 7 人支持 c。
再数每个候选项出现在各名次的次数:
| 候选项 | 第一名次数 | 第二名次数 | 第三名次数 |
|---|---|---|---|
| a | 6 | 7 | 4 |
| b | 8 | 6 | 3 |
| c | 3 | 4 | 10 |
例如使用 Borda 的 2、1、0 分,a 得 19 分,b 得 22 分,c 得 10 分,计分选 b,而不是全胜的 a。
为什么任意合法的三名次分数,都让 b 独自领先?
设三个名次的分数为 $s_1,s_2,s_3$,满足:
$$s_1\ge s_2\ge s_3,\qquad s_1>s_3$$
每个总分就是上表次数与对应名次分数相乘后相加:
$$S_a=6s_1+7s_2+4s_3$$
$$S_b=8s_1+6s_2+3s_3$$
$$S_c=3s_1+4s_2+10s_3$$
先比较 b 与 a。把分差拆成两个非负项:
$$S_b-S_a=(s_1-s_2)+(s_1-s_3)>0$$
再比较 b 与 c:
$$S_b-S_c=5(s_1-s_3)+2(s_2-s_3)>0$$
因为 $s_1>s_3$,两次比较都严格为正。所以 b 是唯一计分赢家;这不是某个分数向量选得不巧。
超过三个候选项时怎么延伸? 可以让所有选民都把新增候选项排在 a、b、c 后面,且新增项之间使用同一顺序。a 仍打败所有人。
若前三名分数不全相同,以上分差仍让 b 胜过 a;若前三名分数相同,a、b、c 都并列最高,结果仍不是只选 a。在本章“所有最高分者都当选”的约定下,这也违反 Condorcet 一致。
这个反例的历史出处不能直接写成“Fishburn 1973 的 17 人例子”。原始文献的不同构造见 Brandt、Dong 与 Peters 的论文附录 A.3;其中这份 17 人构造归于 Moulin。
也别把 Borda 与两两比较说成完全无关。 一位选民给某项的 Borda 分,恰好等于排在它后面的候选项数;累加所有选民,就等于它在所有逐对比较中获得的支持票数之和。
区别在于:Borda 累加这些支持票;Condorcet 要求每一场都赢。一个总分高,并不保证每一项比较都过关。
🔄 四、Condorcet 悖论:三个人,三场循环
这次只用 3 人、3 个候选项。
| 选民 | 偏好 |
|---|---|
| 1 | $a\succ b\succ c$ |
| 2 | $b\succ c\succ a$ |
| 3 | $c\succ a\succ b$ |
逐对算票:
- 1 号和 3 号支持 a 胜过 b:a 以 2:1 胜 b。
- 1 号和 2 号支持 b 胜过 c:b 以 2:1 胜 c。
- 2 号和 3 号支持 c 胜过 a:c 以 2:1 胜 a。
这个例子里没有 Condorcet 赢家:每个点都有一场败仗。 三位选民自己的排序都完全传递;失去传递性的是逐对多数汇总后的关系,不是因为个人排序“乱了”。
注意结论的范围:图中有某个环,不代表全图一定没有 Condorcet 赢家。 假如三个人都把新候选项 d 放在第一名,d 就能打败 a、b、c;原来三者之间的环仍然存在。
逐对比较可以找出全胜者,但有些偏好会形成循环。下面的集合用来处理没有全胜者的情况。
🏆 五、没有全胜者时:比较四种锦标赛解
锦标赛解输入一张锦标赛,输出非空的候选项集合。沿用上一章的符号习惯,这里是集合值的 SCC;有些文献也把集合值规则称为 SCF,阅读时以定义为准。
以下四种解都是 Condorcet 一致的。在 14 人例中,它们都只留下 c,因此需要换一张图才能看出差别。
保留这个五人例子,后面四种解都用它
| 选民 | 偏好 |
|---|---|
| 1 | $b\succ d\succ a\succ c$ |
| 2 | $d\succ a\succ c\succ b$ |
| 3 | $b\succ c\succ d\succ a$ |
| 4 | $a\succ c\succ d\succ b$ |
| 5 | $a\succ b\succ c\succ d$ |
六对多数比较如下:
| 胜者 | 败者 | 胜者 : 败者票数 |
|---|---|---|
| a | b | 3 : 2 |
| a | c | 4 : 1 |
| b | c | 3 : 2 |
| b | d | 3 : 2 |
| c | d | 3 : 2 |
| d | a | 3 : 2 |
① Copeland:数直接胜场
在没有平票的锦标赛里,Copeland 分可以直接用出度表示,即打败了几个候选项。分数最高者组成 $CO$;并列者都保留。
| 候选项 | 直接打败谁 | 胜场数 |
|---|---|---|
| a | b、c | 2 |
| b | c、d | 2 |
| c | d | 1 |
| d | a | 1 |
本例 $CO=\{a,b\}$。 若存在 Condorcet 赢家,它有全部胜场,当然独自领先。有平票的多数图需要另外约定平票得分,本节不把这些变体混进来。
② Top Cycle:不限步数,能走到所有人
从 x 出发,若能顺着箭头走到每一个其他候选项,x 就属于 Top Cycle,记作 $TC$。
这里说的是可达路径,不是把间接胜出算成一场真实投票。
本例四个点都能互相到达。例如 c 到 b 要走 c、d、a、b 三条边。于是:
$$TC=\{a,b,c,d\}$$
这次它没有排除任何人。Top Cycle 可以用于先筛选候选范围,但并不承诺给出唯一赢家。
③ Uncovered Set:两步内能走到所有人
先看“覆盖”的含义。x 覆盖 y,需要同时满足:
- x 直接打败 y。
- y 直接打败的每个人,x 也直接打败。
第二条可以写成 $D(y)\subseteq D(x)$。它只比较这张图的胜负关系,不是说 y 在所有价值、所有指标上都更差。
没有被任何人覆盖的候选项组成 Uncovered Set,记作 $UC$。在锦标赛中,一个等价检查法是:能在至多两步内到达其他每一个点;这样的点也叫 king。
| 出发点 | 一步到达 | 两步补到 | 还有谁到不了? |
|---|---|---|---|
| a | b、c | 经 b 到 d | 无 |
| b | c、d | 经 d 到 a | 无 |
| c | d | 经 d 到 a | b;需要第三步 |
| d | a | 经 a 到 b、c | 无 |
本例 $UC=\{a,b,d\}$。 b 覆盖 c:b 打败 c,也打败 c 唯一打败的 d。不存在其他覆盖关系。
这个两步等价刻画针对锦标赛;遇到存在平票、缺边的多数图,不能直接照搬。
④ Banks Set:极大无环子图的第一名
选取一些候选项,并保留它们之间的全部边,这叫顶点导出子图。若这张小锦标赛没有环,它就对应一条传递排序。
“极大”要求:再加入任何一个剩余候选项,都会出现环。 它不是“顶点数量最多”的“最大”。
每个极大无环子图的第一名都算 Banks 赢家;把这些第一名收集起来,得到 $BA$。
| 极大无环子图 | 内部传递排序 | 第一名 |
|---|---|---|
| a、b、c | $a\succ b\succ c$ | a |
| b、c、d | $b\succ c\succ d$ | b |
| a、d | $d\succ a$ | d |
本例 $BA=\{a,b,d\}$。 只有两个点的 a、d 也必须保留:加 b 会出现 a 胜 b、b 胜 d、d 胜 a 的环;加 c 也会出现三点环。
如果误把“极大”理解成“人数最多”,就会漏掉 d——这不是换个措辞,而是会算出不同答案。
为什么找一个 Banks 赢家容易,检查指定的人却可能很难?
找任意一个:从一个点开始,只要加入某个点后仍无环,就继续加入;直到没有点能加入。最终得到一个极大无环子图,取其第一名即可。这能在多项式时间内完成。
检查给定候选项 x 是否属于 Banks 集合:需要知道是否存在某个极大无环子图,恰好让 x 排第一。找到任意一个子图,并不能回答这个指定人的问题。
后一判定问题是 NP-完全的,见 Woeginger(2003)的原始论文摘要。这是随候选项数量增长的最坏情况复杂度,不是说本页四个候选项的小例子算不了。
📊 包含关系:通用结论与本例分开看
对锦标赛,下面三条关系成立:
$$BA(T)\subseteq UC(T)$$
$$CO(T)\subseteq UC(T)$$
$$UC(T)\subseteq TC(T)$$
它们没有给出一条通用的“Copeland 必包含在 Banks 中”的直线层级。
三条包含关系,各看一个短理由
UC 在 TC 内。 两步内可达所有点,当然也满足“不限制步数时可达所有点”。
CO 在 UC 内。 若 x 被 y 覆盖,y 不但赢了 x,还赢了 x 赢的所有人,因此 y 的胜场严格更多。这样 x 就不可能是最高胜场者。
BA 在 UC 内。 设 x 是某个极大无环子图的第一名。若 y 覆盖 x,那么 y 也打败这个子图里的其他所有点;把 y 加到最前面仍然无环,违反极大性。
锦标赛解的定义与两步刻画可核对 《计算社会选择手册》第 3 章,尤其 3.3.2 节。
🧰 六、另外三条 Condorcet 一致的规则
前面的四种解只看多数边的方向。下面的规则还会用到完整排序或支持票数,不宜仅靠一张无权箭头图计算。
Kemeny:让与个人排序的总冲突最少
先提出一个集体排序,再逐位选民、逐对候选项检查:这个排序是否与该选民的先后意见相反?把反向次数全部累加,寻找总数最小的排序。
要数的是各位选民的成对意见,不是简单数“改了几条多数边”。 3:2 与 100:1 的胜负不能被当成同样强的证据。
五人例子中,检查全部 24 种排序,唯一最优排序是 $a\succ b\succ c\succ d$,共有 12 次成对意见冲突。选 Kemeny 赢家时,取所有最优排序的第一名;本例就是 a。
12 次冲突是怎么加出来的?
提出排序 a、b、c、d 后,对每一对数“反过来排”的人数:
| 提出的先后 | 持相反意见的人数 |
|---|---|
| a 在 b 前 | 2 |
| a 在 c 前 | 1 |
| a 在 d 前 | 3 |
| b 在 c 前 | 2 |
| b 在 d 前 | 2 |
| c 在 d 前 | 2 |
相加为 12。六对各自少数票之和为 11,但无法同时满足六条多数边,因为其中有环。任何排序都至少逆转一条严格多数边,至少再增加 1 次冲突,因此 12 达到了下界。
这里只有 a 对 c 的多数差为 3,其余五对差为 1;检查其余排序可确认最优排序唯一。一般规模下求 Kemeny 最优排序是 NP-难问题;小例子穷举可行,并不与这个复杂度结论冲突。
Black:有全胜者就选它,否则看 Borda
先检查 Condorcet 赢家。存在时只选它;不存在时,选择所有 Borda 最高分者。
五人例没有全胜者,Borda 分别为 a:9、b:8、c:6、d:7,因此 Black 选 a。
Nanson:每轮重算,再同时删掉低于平均分者
这里使用严格低于平均分的版本,明确每轮做三件事:
- 只保留当前候选项,重新计算 Borda 分。
- 计算当前候选项的平均分,同时删去所有严格低于平均分者。
- 剩一项,或所有剩余项同分、已无人可删时停止;后一种情况返回全部剩余项。
五人例可以复算成两轮:
| 轮次 | 当前 Borda 分 | 平均分 | 本轮同时删去 |
|---|---|---|---|
| 1 | a:9、b:8、c:6、d:7 | 7.5 | c、d |
| 2 | a:3、b:2 | 2.5 | b |
结果留下 a。 第二轮只比较 a 与 b,名次分改成 1、0;不是继续沿用第一轮的 9 分与 8 分。
它为什么保得住 Condorcet 赢家?版本又有什么区别?
若有 $m$ 个剩余候选项、$n$ 位选民,标准 Borda 的平均分是:
$$\frac{n(m-1)}{2}$$
Condorcet 赢家在与每个对手的比较中都获得超过一半的支持票。把这些支持票相加,它的 Borda 分严格高于平均分,因此不会被删掉。
删除其他人之后,它仍打败每个剩余对手;同样的理由逐轮成立,最后只剩它。
文献也有删除“低于或等于平均分者”的弱版本,并规定全体同分时停止。两种版本不能在例子中混用。关于版本区别可参照 Brandt、Dong 与 Peters 的 Nanson 说明及附录注释。
选规则时分开问两件事:它满足什么选择要求?在当前输入规模下算得动吗? “定义简单”不能代替计算复杂度分析。
🔗 这一章连到哪里
| 去哪里 | 带着什么问题去 |
|---|---|
| 26-不可能定理.html | Arrow 定理还要求哪些条件?不能把它简化成“只要排序传递,就必须独裁” |
| 24-投票规则.html | 同一份选票,六种规则为何给出五个不同赢家? |
| 23-Shapley值.html | 定义、公平要求与计算成本如何区分?精确计算成本还取决于博弈的表示方式 |
| 推荐算法 06 · 工业架构 | 多路候选集合合并、多个完整排序聚合、标量分数融合,分别在做什么? |
推荐里的类比要有限度:如果聚合多个完整排序并按逐对多数决定先后,就可能遇到循环。
但“多路召回的候选集合取并集”不等于排序聚合;按一个标量总分排序本身也不会产生严格循环,平分时另定规则即可。不能用 Condorcet 悖论直接断言多目标加权公式会自相矛盾。
✅ 检查点
- 多数关系怎么数?奇数人数保证无平票还需要哪些前提?
- 14 人例的 Condorcet 赢家是谁?a 的战绩如何?c 有几张第一名票?
- 17 人例中,为什么任意合法的三名次计分都让 b 胜过 a?全胜者又是谁?
- 写出三人循环。个人排序是否不传递?更大的图只要含环就一定没有全胜者吗?
- Copeland 分是什么?五人例的 CO 是多少?
- 覆盖怎么定义?两步刻画适用于什么图?谁被排除出 UC?
- Banks 的“极大”与“最大”有何区别?三个极大子图是谁?计算问题要分哪两种?
- 三条通用包含关系是什么?它们与本例的集合嵌套有什么区别?
- Kemeny 数哪些冲突?Black 如何补充分支?本章 Nanson 每轮如何删选?
核对答案:按题号查,不必一次读完
-
比较把 x 排在 y 前面与反过来的人数。本章是等权、完整严格排序、人人参与每一对比较;这些前提下,奇数人数足以避免平票。
-
c 全胜;a 是 0 胜 4 负;c 没有第一名票。c 与 2-approval 的结果重合,不是第六个不同赢家。
-
b 比 a 多出的分数为 $(s_1-s_2)+(s_1-s_3)>0$;a 却以 9:8 胜 b、10:7 胜 c,是全胜者。这里使用非增、非全相同的名次分数。
-
三张排序为 abc、bca、cab,得到 a 胜 b、b 胜 c、c 胜 a,都是 2:1。个人排序都传递;若另有 d 被全体放在第一,它可成为全胜者,abc 的环仍在。
-
锦标赛中的直接胜场数;a、b 各两胜,c、d 各一胜,所以 $CO=\{a,b\}$。
-
x 胜 y,且 y 胜的人 x 也全胜。在锦标赛中,未被覆盖等价于两步内到达所有其他点。本例 b 覆盖 c,故 $UC=\{a,b,d\}$。
-
极大指无法再加点而保持无环,不要求人数最多。子图为 abc、bcd、ad,第一名分别是 a、b、d。找任意一个 Banks 赢家与判定指定项是否属于 Banks,是不同问题。
-
BA 在 UC 内,CO 在 UC 内,UC 在 TC 内。本例恰有 BA 与 UC 相同,且 CO 在它们内部;这个特例不能被当成通用的 CO 与 BA 包含关系。
-
Kemeny 累加集体排序与各选民的逐对意见冲突;Black 有全胜者选它,否则选 Borda 最高者;严格 Nanson 每轮重算,并同时删除严格低于平均分者。
本节回顾
先记住这三件事
- Condorcet 赢家要直接打败所有对手;它不一定存在。
- 没有全胜者时,四种锦标赛解可以留下不同集合;路径可达不等于直接胜出。
- Banks 用“极大”,不是“人数最多”;复杂规则先用本页的小例子逐项算。
下一节 👉 26-不可能定理.md