🏠 总目录📚 本教程 25 · Condorcet 与锦标赛 ← →

多数两两比较若出现循环,怎样选出候选集合?

读后可检查:从多数关系和原选票出发,区分 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 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$

逐对算票:

三场都是 2:1:a 胜 b,b 胜 c,c 胜 a。每个候选项都输一场。2:12:12:1abc箭头:多数胜者 → 败者
顺着箭头会回到起点;这三个候选项中,没有谁打败所有对手。

这个例子里没有 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
五人例的六条边:a 胜 b、c;b 胜 c、d;c 胜 d;d 胜 a。abcd箭头:多数胜者 → 败者
箭头表示直接胜出;间接可达不算直接胜场。

① 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,需要同时满足:

  1. x 直接打败 y。
  2. 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 = BA;CO 是它们的子集TCUC = BACOabdc
仅本例:UC、Banks 去掉 c,Copeland 还去掉 d。
三条包含关系,各看一个短理由

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:每轮重算,再同时删掉低于平均分者

这里使用严格低于平均分的版本,明确每轮做三件事:

  1. 只保留当前候选项,重新计算 Borda 分。
  2. 计算当前候选项的平均分,同时删去所有严格低于平均分者。
  3. 剩一项,或所有剩余项同分、已无人可删时停止;后一种情况返回全部剩余项。

五人例可以复算成两轮:

轮次 当前 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 悖论直接断言多目标加权公式会自相矛盾。


✅ 检查点

  1. 多数关系怎么数?奇数人数保证无平票还需要哪些前提?
  2. 14 人例的 Condorcet 赢家是谁?a 的战绩如何?c 有几张第一名票?
  3. 17 人例中,为什么任意合法的三名次计分都让 b 胜过 a?全胜者又是谁?
  4. 写出三人循环。个人排序是否不传递?更大的图只要含环就一定没有全胜者吗?
  5. Copeland 分是什么?五人例的 CO 是多少?
  6. 覆盖怎么定义?两步刻画适用于什么图?谁被排除出 UC?
  7. Banks 的“极大”与“最大”有何区别?三个极大子图是谁?计算问题要分哪两种?
  8. 三条通用包含关系是什么?它们与本例的集合嵌套有什么区别?
  9. Kemeny 数哪些冲突?Black 如何补充分支?本章 Nanson 每轮如何删选?
核对答案:按题号查,不必一次读完
  1. 比较把 x 排在 y 前面与反过来的人数。本章是等权、完整严格排序、人人参与每一对比较;这些前提下,奇数人数足以避免平票。

  2. c 全胜;a 是 0 胜 4 负;c 没有第一名票。c 与 2-approval 的结果重合,不是第六个不同赢家。

  3. b 比 a 多出的分数为 $(s_1-s_2)+(s_1-s_3)>0$;a 却以 9:8 胜 b、10:7 胜 c,是全胜者。这里使用非增、非全相同的名次分数。

  4. 三张排序为 abc、bca、cab,得到 a 胜 b、b 胜 c、c 胜 a,都是 2:1。个人排序都传递;若另有 d 被全体放在第一,它可成为全胜者,abc 的环仍在。

  5. 锦标赛中的直接胜场数;a、b 各两胜,c、d 各一胜,所以 $CO=\{a,b\}$。

  6. x 胜 y,且 y 胜的人 x 也全胜。在锦标赛中,未被覆盖等价于两步内到达所有其他点。本例 b 覆盖 c,故 $UC=\{a,b,d\}$。

  7. 极大指无法再加点而保持无环,不要求人数最多。子图为 abc、bcd、ad,第一名分别是 a、b、d。找任意一个 Banks 赢家与判定指定项是否属于 Banks,是不同问题。

  8. BA 在 UC 内,CO 在 UC 内,UC 在 TC 内。本例恰有 BA 与 UC 相同,且 CO 在它们内部;这个特例不能被当成通用的 CO 与 BA 包含关系。

  9. Kemeny 累加集体排序与各选民的逐对意见冲突;Black 有全胜者选它,否则选 Borda 最高者;严格 Nanson 每轮重算,并同时删除严格低于平均分者。


本节回顾

先记住这三件事

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

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