第二部分
排名理论
61
第九章 社会选择理论
人类行为是由一系列选择（choice）和决策（decision making）构成，理解人类行为的一切
思想都以研究选择为基础，如古希腊先哲苏格拉底（Socrates）和亚里斯多德（Aristotle）认为愿
望和信仰是人类做出选择的前。19世纪，人们开始构建人类选择的量化模型，比如实验心理学的
奠基人恩斯特·海因里希·韦伯Ernst Heinrich Weber 通过建立心理活动和可度量物理行为间的关
联，出著名的韦伯定律，成为心理学量化分析人类心理活动（包括选择）的基石。承其衣钵的学
生古斯塔夫·费希纳Gustav Theodor Fechner扩展韦伯定律，创立出更为精确的度量系统，称作费
希纳定律。20世纪初，法国路易斯·列昂·瑟斯顿Louis Leon Thurstone
➊
基于韦伯–费希纳定律
发展出比较性评价（comparative judgment）系统 [25]，基于成对比较的瑟斯顿模型由此诞生。
社会选择（social choice），也称“集体决策”（collective decision）是将社会成员的个人意
愿或偏好汇集成群体意愿或偏好的过程，属于典型的群体决策问题。选举制度是社会选择的
一个制度性体现，为民主国家反映民意的一个主要机制。为了体现少数服从多数的民主理念，
人们出多数代表制（majoritarian representation）或多数制（plurality voting）， 认 定 得 票 最
多的候选人胜出。为了确保反映社会多元化的意见，1846年瑞士学者Victor Considerant出比
例代表制（proportional representation）， 根 据 政 党 或 参 选 组 别 得 票 比 例 分 配 议 席 。 由 于 不 同 选
区人口或经济地位的差异，人们根据每个选区所代表的议席数目，将选举方法分成单一选区
制（single-member district）或“小选区制”（small constituency system）、 复数选区制（multi-
member district）或“大选区制”（large-size district）。 单 一 选 区 制 每 个 选 区 只 有 一 个 议 席 ， 而 复
数选区制每个选区对应多个议席。多数制在单一选区制下也称作简单多数制（first-past-the-post,
single choice voting, simple plurality, simple majority）或相对多数制（relative majority）
➋
；在
复数选区制下称作胜者全拿（winer-takes-all）。 如 果 根 据 选 举 规 则 无 法 选 出 一 个 合 适 的 候 选 人 ，
可能是平局，也可能是不满足一定的规则，为避免出现此类状况，人们出决胜选举（run-off）进
行多轮投票直至有人胜出。
我们将在后续章节介绍社会选择的相关概念、公理性推导、社会选择方法与投票准则、评价社
会选择的标准、各种社会选择方法的关联以及几个著名的社会选择悖论，最后介绍社会选择理论最
➊ 路易斯·列昂·瑟斯顿Louis Leon Thurstone（1887-1955）， 美 国 心 理 学 家 ， 美 国 心 理 测 量 学 会 的 创 立 者 之 一 ， 并 任 第 一 届 心 理 测 量
学会主席，在测量理论、社会评价等理论应用方面均作出巨大贡献。1933年当选为美国心理学会主席，1938年当选为国家科学院院士。
➋ 多数制别称相对多数制，与之对应的是绝对多数制（absolute majority）：候选人得票数只有超过其他候选人得票数之和才算胜出。
63
搜索与排名 Searching and Ranking
!"#
新进展计算社会选择（Computational Social Choice，CSC）， 以 及 社 会 选 择 理 论 在 推 荐 系 统 评 分
预测、网络排名聚合、体育竞技排名等领域的应用研究。
9.1 符号定义
社会选择通常依赖于可排列对象的排列变换（permutation）
➊
，为此我们对相关概念给出统
一的数学定义。假设A = {x, y, z, . . .}是可排序
➋
的对象集，如决策时的备择选项（alternatives）、
选举投票时的候选人集合（candidates）、 在 线 购 物 评 分 时 的 商 品 列 表 （ items）等，并且|A| = n，
A上的一个排列（ranking or ballot）定义为从A 到{1, 2,...,n}上的一个双射：
π : A -→ {1, 2,...,n}, (9.1)
并使用π(i)表示A中第i个对象在排列变换π作用下的排名，π
−1
(i)表示在π作用下排在第i位的原始
对象。通常，我们也使用π和π
−1
分别表示由A中所有对象的排名向量、有序排列的对象向量。对
象集A可以产生n!种可能的全排列组合，可以构成一个非交换群，记为Π[A]或Π[n]。如果我们选择
一部分对象，比如{π
−1
(1), π
−1
(2),...,π
−1
(K)}，从群Π[n]中筛选出所有第i 位对应π
−1
(i) 的排列，
1 ≤ i ≤ K ≤ n，构成Π[n] 的一个子群，记作Π[n, K, π]：
Π[n, K, π]=
,
σ ∈ Π(n)|σ
−1
(i)=π
−1
(i), 1 ≤ i ≤ K
-
∈ 2
Π[n]
. (9.2)
假设存在一组决策者M = {X, Y, Z,. . .}，比如投票选举时的选民（voters）、 电 影 评 价 时 的 影 评 人
（raters）等，并且|M| = m，每个决策者都有一个A上的个人偏好排名（individual preferential
ranking），从而可以构成一个社会偏好集（social preference profile）
Π[A, M]=Π[n, m]={π
i
}
m
i=1
∈ 2
Π[n]
(9.3)
其中π
i
∈ Π[n]表示M上第i个决策者对A 做出的一个线性排序。在不产生混淆的情况下，我们
简记作Π ! Π[n, m]。如果存在一个社会选择函数F : Π[n, m] -→ Π[n]，能够基于Π[n, m] 给出A
的一个全局性的评价，则全局线性排序记作π
F
∈ Π[n]，也成社会偏好排名（social preferential
ranking）。 对 于 任 意 一 个 A上的线性序π，都对应一个特殊的决策方。给定任意两个对象x, y ∈ A，
我们用x ≻
π
y 表示x 在π中的排名高于y，或者π偏好x甚于y。为了强调决策方，比如决策者Z偏
好x甚于y，则记作x ≻
Z
y。如果F 偏好x甚于y，则记作x ≻
F
Π[n,m]
y，或简记作x ≻
F
Π
y。如果存在
一个社会选择函数F : Π[n, m] -→ A，则它能够基于Π[n, m]选择A上的一个成员，并称其为社会选
择（social choice）。
➊ 英文单词Permutation存 在 两 个 中 文 字 面 翻 译：排列或 置换。本文对两种翻译不作具体区分，主要使用第一种翻译意思。
当permutation作为一个变换算子出现时，我们称其排列变换；当permutation作为一个有序列表出现时，我们称其排名列表。读者
如果对排列和置换之间的差异感兴趣，可参考潘庆年教授的一篇注解[26]。
➋ 可排序依赖于空间上定义的二元全序关系，我们将在后文给出严格定义。
$%"&'#(
64
)!*+",$
9.1. 符号定义
!"#
例9.1. 2014年7月7日至10日，盖洛普（Gallup）对民主党五位2016年总统选举候选人Hillary Clin-
ton、Elizabeth Warren、 Andrew Cuomo、 Martin O’Malley、Joe Biden组织了一次民意调查
➊
，统计
公众对几位候选人的了解情况，具体统计数据见下表： 表格中每一行代表一位候选人，第二列是
Candidate Familiar (%) Favorable (%) Unfavorable (%) Net Favorable (%)
Hillary Clinton 91 55 36 19
Elizabeth Warren 38 21 17 4
Andrew Cuomo 51 27 24 3
Martin O’Malley 19 7 9 -2
Joe Biden 80 38 42 -4
表 9.1: 2014年7月7日至10日盖洛普民主党2016总统候选人民调数据
公众认识候选人的比例，第三列是公众认同候选人的比例，第四列是公众不认同候选人的比例，最
后一列则是公众认同候选人减去不认同的比例，属于净认同的比例。根据数据可知，五位总统候选
人A =
,
Clinton，Warren，Cuomo，O’Malley，Biden
-
中，美国前第一夫人、前国务卿Clinton是公
众最为熟知、最受公众欢迎的民主党候选人。前副总统Biden虽为公众所知，认同他的民众却少于
不认同他的人数。
我们现在用一组连续的自然数{1, 2, 3, 4, 5}为他们编号，则1号对应Clinton，3号对应Cuomo。
如果根据第二列的公众熟知比例为他们排名，则会产生一个新的排名列表π
1
= ⟨1, 4, 3, 5, 2⟩，那
么π
−1
1
(4) = 2表示排名列表π
1
中位列第4的对象是2号候选人Warren，π
1
(5) = 2表示5号候选人Biden
在列表π
1
中排名第2 位。 类 似 地， 我 们 按 照 最 后 一 列 排 列 候 选 人 名 单， 又 会 产 生 一 个 排 名 列
表π
4
= ⟨1, 2, 3, 4, 5⟩。
我们根据社会选择法的步骤及输出数据类型[27, 28]，将社会选择方法分成位置评分法、位置
筛选法和概率模型法。位置评分准则赋予每个候选人一个对应分值，分值的产生可能源于整体排
序（如波达计数[29]、Footrule法[30]、中位数法[31]、CPS模型[32] 和矩阵分解方法[33]）， 或 者 源
于序对比较（如孔多塞法、凯梅尼─杨格方法和马尔科夫方法）。位置筛选法综合候选人的位置、
多数投票得分等因素，逐步缩短偏好列表的长度，剔除不合格的候选人直至最优人选诞生，如单记
可让渡投票制。概率模型法建立候选人排列的概率分布，包括瑟斯顿模型 [25]、布雷德利─特里模
型 [34]、马洛斯模型 [35] 和普拉基特─卢斯模型 [36, 37]。我们在后续几个小节简要介绍几种代表
性的社会选择方法，并基于1980年美国参议院议员选举为例解释各种方法。
例9.2. [38] 1980年美国纽约州参议院选举在保守派的Alphonse D’Amato、自由派的Elizabeth Holtz-
man与Jacob Javits之间展开，三名候选人的得票率如表9.2所示，22%的选民对于三名候选人的个人
偏好为D ≻ H ≻ J，4%的选民存在个人偏好J ≻ D ≻ H，每名候选人使用其姓氏首字母表示。为
简化表示，我们在后续章节使用本例数据时直接省略百分号。
➊ Gallup: Clinton Is Best Known, Best Liked Potential 2016 Candidate, 2015-09-14
$%"&'#(
65
)!*+",$
搜索与排名 Searching and Ranking
!"#
29% 23% 22% 15% 7% 4%
H D D H J J
J J H D H D
D H J J D H
表 9.2: 1980年美国纽约州参议院选举
9.2 位置评分法
位置评分法根据每个偏好列表对所有候选人评分，然后累加候选人在所有偏好集上评分得
到总的分值，利用各候选人的综合评分可以选出优胜者或者建立所有候选人的综合排名。假
设V
π
∈ R
n
表示A在偏好列表π上的得分向量，则A内所有候选人的综合得分向量
V
Π
= V
Π
=
"
π ∈ Π
V
π
=
"
π ∈ Π
.
V
1
π
,V
2
π
,...,V
n
π
/
, (9.4)
其中V
i
π
表示A中第i个候选人在偏好列表π下的得分分值，1 ≤ i ≤ n。
9.2.1. 多数投票法
多数投票法是一种最常见的投票选择方法，也是英国大选采用的一种选举方法。它只利用所有
偏好列表排名第一的数据确定出最终赢家。对于个选民偏好列表π，根据候选人集合A 在偏好名
单π上的名次，只有排名第一的候选人可以得到一个点数，其他位置上的候选人没有得分。对于例
子9.1，多数投票法只考虑排名第一的候选人，各候选人的得分如下：
V
D
= 23 + 22 = 45，V
H
= 29 + 15 = 44，V
J
= 7 + 4 = 11,
候选人D’Amato以45比44险胜Holtzman，社会偏好为D ≻ H ≻ J。
9.2.2. 波达计数
1770年，法国数学家、政治学家让─查尔斯·波达Jean-Charles de Borda[29]设计出一种新的
投票计数方法，称作波达计数（Borda Count），用于评选法国科学院院士。波达计数根据选民偏好
名单中的排名给候选人一定的点数，一般地排名越高点数越高，如排名第一的候选人得到n − 1个
点，排名靠后依次逐渐减少一个点。后来，由于波拿巴·拿破仑的干预，弃用波达计数，并采纳拉
普拉斯的意见，使用绝对多数准则评选科学院院士。根据波达计数法，例9.1三名候选人得分
⎡
⎢
⎢
⎢
⎣
V
D
V
H
V
J
⎤
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎣
022101
201210
110022
⎤
⎥
⎥
⎥
⎦
×
⎡
⎢
⎢
⎢
⎢
⎢
⎣
29
23
22
15
7
4
⎤
⎥
⎥
⎥
⎥
⎥
⎦
=
⎡
⎢
⎢
⎢
⎣
109
115
74
⎤
⎥
⎥
⎥
⎦
,
可知候选人Holtzman胜出，社会偏好为H ≻ D ≻ J。
$%"&'#(
66
)!*+",$
9.2. 位置评分法
!"#
9.2.3. 记分投票法
多数投票法与波达计数都是建立在排序投票系统之上，选民只是根据自己的偏好对候选人进
行排列。实际上，如果选民能够对候选人进行顺次排序，我们可以给予其更多的自由，使用限定的
离散分值给候选人打分，从而能够更有效地反映出选民的意愿。这种投票选举的方法称作计分投票
法（range voting，rating summation，scoring）， 在 网 络 空 间 有 广 泛 应 用 ， 比 如 网 民 对 电 影 、 图
书、 商品的1–5级评分。计分投票法根据每个候选人所有评分均值、中值（majority judgment）或
加和，评分最高者胜出。如果离散分值只有两个{0, 1}或者{同意，反对}，则称计分投票法为同意
投票法（approve voting）。 我 们 可 以 从 计 分 投 票 中 构 建 每 个 选 民 的 偏 好 排 名 ， 允 许 一 对 一 的 对 决 ，
满足各种良好的性质，如传递性、一致性等。可以如果存在策略性投票行为，由于每张选票每个候
选人的可能分值是一个区间范围，即便是离散数字，也比排名列表形式的选票更难操纵。
9.2.4. 孔多塞方法
1785年，法国启蒙思想家马奎斯·孔多塞Marquis de Condorcet[39]在研究民主决策时，出
一种序对型选举投票方法，称为孔多塞方法。孔多塞方法根据选民的偏好集合Π，统计所有可能的
偏好序对，根据多数准则选出得票最多的赢家。如果Π存在一个候选人（比如x）， 在 和 其 他 每 个 候
选人一对一对决（round-robin or one-on-one or head-to-head）
➊
时，都能获得多数选票，即有
∀y ∈ A,
6
6
{π ∈ Π : x ≻
π
y}
6
6
>
6
6
{π ∈ Π : y ≻
π
x}
6
6
, (9.5)
则称其孔多塞赢家（Condorcet winner）。 根 据 孔 多 塞 方 法 ， 例 子 9.1中三个候选人的一对一对决统
计结果如表9.3所示，候选人Holtzman是一个孔多塞赢家，并且社会偏好为H ≻ D ≻ J。如果一
偏好 得票 偏好
H ≻ D 51 > 49 D ≻ H
H ≻ J 66 > 34 J ≻ H
D ≻ J 60 > 40 J ≻ D
表 9.3: 孔多塞赢家
个候选人是Π[n]上的孔多塞赢家，则它在一对一对决中从未被其他候选人击败，即是说其他每个候
选人至少被此孔多塞赢家所击败一次，他们不可能是孔多塞赢家。由此可知，孔多塞赢家只要存在
必然唯一，但它并非总是存在。
例9.3. 假设某次社会投票选举只有三个候选人{x, y, z}参选，他们的偏好集如表9.4所示。根据孔多
塞方法，统计每个候选人一对一对决结果，比如有20个选民存在偏好x ≻ y，只有10个选民有偏
➊ 体育运动竞技比赛，如网球、足球、国际象棋、桥牌、拳击运动，经常要运动员或团队之间进行多轮形式的循环赛（round-robin
tournament）， 表 示 所 有 参 赛 选 手 彼 此 进 行 多 次 两 两 对 决 。 17世纪初，round-robin衍生出新的涵义，表示“圆形签名请愿书”。在签署控诉
书、请愿书等多人署名文件时，顺着一个圆圈署名，籍此让人分不出署名的先后顺序，以保护领头人免于遭受报复。
$%"&'#(
67
)!*+",$
搜索与排名 Searching and Ranking
!"#
好y ≻ x，前者得两票胜出，则x ≻ y；类似可知y ≻ z与z ≻ x。孔多塞方法在此社会偏好集上产生
一个偏好回路（preferential cycle）x ≻ y ≻ z ≻ x，存在一个内在矛盾：社会偏好x甚于y，偏好y甚
于z，但又偏好z甚于x，孔多塞赢家并不存在，出现孔多塞悖论（Condorcet’s paradox）。
票数 偏好列表
10 x ≻ y ≻ z
10 y ≻ z ≻ x
10 z ≻ x ≻ y
偏好 票数 偏好
x ≻ y 20>10 y ≻ x
y ≻ z 20>10 z ≻ y
z ≻ x 20>10 x ≻ z
表 9.4: 孔多塞悖论
孔多塞在分析投票方法时还给出一个著名的孔多赛陪审团定理（Condorcet’s Jury Theo-
rem）：“如果每个陪审员做出正确决定的概率都大于0.5，那么陪审员越多，则陪审团做出正确决
定的可能性就越大。当陪审员达到一定规模，陪审团做成正确判决的概率会无限趋近于1”。
当法庭作出项审判决定时，陪审团按照多数准则进行表决，只有当表决赞同或反对法庭审判
决定的陪审员达到一定比例，陪审团同意或否决法庭判决的决议才能生效。孔多塞陪审团定理假定
“每个陪审员都能独立做出决定，赞同或否决法庭判决，并且做出正确决定的概率相同”
➊
。我们
现在从概率统计的角度进行分析，设陪审团由n名陪审员组成，每个陪审员独立做出正确决定的概
率是p，则整个陪审团能否做出正确判决取决于多数陪审员的意见，陪审团做出正确判决概率ˆp可以
表示成二项分布部分和形式：
ˆp =
"
n/2≤i≤n
.
n
i
/
p
i
(1 − p)
n−i
=1−
"
0≤i≤n/2−1
.
n
i
/
p
i
(1 − p)
n−i
. (9.6)
可以证明，如果p>0.5，当n →∞时，ˆp → 1。图9.1表示陪审团做出正确决定的概率与陪审团人数
的关系：随着陪审团人数的增加，当p =0.51 > 0. 5时（红色），做出正确决定的概率越大；反之，
如果p =0.49 < 0.5（蓝色），则概率越低。
孔多赛陪审团定理的不足之处在于其假设过于理想，比如陪审员或者投票人每个人的价值观
念都不同，由于相互影响，可能更多的是以团体形式进行表决或投票，因此独立性假设与等概率假
设就站不住脚；此外，在投票理论中，候选人不能通过简单的优化理论做出评价，从而难以选择出
“最佳”候选人；当投票人不同、候选人得票率不同的情况下，利用简单的多数投票准则并不能得
到满意的结果，即出现投票分割问题。
孔多塞方法是一类方法，我们下面介绍几个典型的孔多塞方法：柯普兰方法、凯梅尼─杨格方
法、最小最大法、南森方法、道奇森方法、排名序方法和舒尔茨方法，并分析各自的性质。
➊ 公元前399年，70岁的苏格拉底由于被指控不敬神和败坏青年而站到雅典的法庭上，一个由501名公民构成的陪审团在第一轮投票
以280对221的微弱优势判处苏格拉底有罪，在第二轮以360对141的多数优势判其死刑，陪审团通过民主的程序将激怒他们的苏格拉底处
死。西德尼·吕美特执导的《十二怒汉》（12 Angry Men）告诉我们“陪审员独立作出决定”是一种理想化的设定，可能促成陪审团做出
正确的决定或相反，多数同意准则不一定就是民主的、永远有效的表决方案。
$%"&'#(
68
)!*+",$
9.2. 位置评分法
!"#
200
400
600
800
1000
0.3
0.4
0.5
0.6
0.7
图 9.1: 陪审团做出正确决定的概率
定义9.1 (孔多塞准则). 对于任意的A及偏好集Π[A, M]，如果候选人x ∈ A是一个孔多塞赢家，
则x是F在偏好集Π[A, M]上的社会选择，并且是唯一的社会选择，则称社会选择函数F满足孔多塞
准则或孔多塞赢家准则（Condorcet Winner Criterion，CWC）。
I. 柯普兰方法
柯普兰方法（Copeland method）是一种孔多塞方法，它利用个候选人在和其他候选人一对
一循环对决中胜出局数与落败局数之差，换而言之是其所击败的候选人数目减去将其击败的候选
人数目，作为其投票分值，最终投票分值最高的候选人胜出。根据柯普兰方法，例子9.1中三名候
选人的得分如下
V
H
=2,V
D
=0,V
J
= −2.
柯普兰方法属于零和博弈（zero sum game）： 候 选 人 Holtzman是孔多塞赢家，将其他两个候选
人D’Amato和Javits悉数击败，而Javits则是孔多塞输家（Condorcet loser）， 在 与 其 他 两 名 候 选 人
对决时皆落败。根据柯普兰得分，孔多塞赢家Holtzman胜出，并且社会偏好为H ≻ D ≻ J。
II. 凯梅尼─杨格方法
凯梅尼─杨格方法（Kemeny-Young method） [40]，也称凯梅尼规则、最大似然模型，也是
一种基于成对比较的投票方法。KY方法考虑每个可能的偏好排名，根据社会偏好集Π[n, m]计算各
个偏好排名的分值，分值最高的排名是社会选择偏好排名。KY方法将每个个体偏好排名拆解成所
有可能序对偏好，利用社会偏好集确定含有对应序对偏好的票数，将对应序对偏好的票数加和即是
个个体偏好的得分。
定义9.2 (排名分值). 对于候选集A，可以生成n(n-1)种可能的偏好序对。对于某个排名π ∈ Π，
有π
−1
(1) ≻ π
−1
(2) ≻ ···≻ π
−1
(n)，可抽取出n(n-1)/2种序对偏好π
−1
(i) ≻ π
−1
(j)，1 ≤ i<j≤ n。
$%"&'#(
69
)!*+",$
搜索与排名 Searching and Ranking
!"#
如果个体偏好排名σ ∈ Π[n, m]包含某个序对偏好，则为其投一票，遍历偏好集可算出每个序对偏
好在社会偏好集上的得票
V (x, y)=
"
σ ∈Π[ n,m]
I(x ≻
σ
y), ∀ x, y ∈ A, (9.7)
则排名π的分值等于其上所有可能的偏好序对的得票之和
V
π
=
"
x≻
π
y
V (x, y)=
"
x,y∈A
7
I(x ≻
π
y)
"
σ∈ Π[ n,m]
I(x ≻
σ
y)
8
. (9.8)
定义9.3. 凯梅尼─杨格方法是搜索Π选择出排名分值最大的偏好排名，即解如下形式的优化模型
π
F
= arg max
π ∈Π
V
π
. (9.9)
最优排名π
F
中排名最高的候选人π
−1
F
(1) ∈ A是社会偏好集Π[n, m]上的社会选择。
定理9.1. 凯梅尼─杨格方法等价于从Π搜索一个与社会偏好集Π[n, m]内所有个体偏好最近的偏好排
名π
F
，以尽可能和所有选民的个人偏好保持一致。
π
F
= arg min
π ∈ Π
"
σ ∈ Π[n,m]
τ(π, σ), (9.10)
其中，τ表示肯德尔距离度量公式。
例9.4. 根据例子9.1，我们可以构建序对偏好计票表与排名分值分布表9.5。对于偏好排名D ≻ H ≻
J，其分值是D ≻ H、D ≻ J和H ≻ J三个序对偏好分值之和V
D≻H≻J
=49+60+66=175。根据偏好
排名的分值可知社会选择是孔多塞赢家Holtzman，社会偏好排名是H ≻ D ≻ J，而排名分值最低
的偏好排名是J ≻ D ≻ H，恰好是社会偏好排名的完全逆排列。为了验证定理9.1，我们计算所有
偏好列表对的肯德尔距离以及每个个体偏好排名与社会偏好集Π[n, m]的肯德尔距离，如表9.6 所
示，表的末行数据是根据公式9.10计算得到的肯德尔距离之和，其他行数据表示对应行偏好列表
与列偏好列表之间的肯德尔距离。比如个体偏好H ≻ J ≻ D 与J ≻ D ≻ H的肯德尔距离是2/3，
而J ≻ D ≻ H与社会偏好集的肯德尔距离
τ(J ≻ D ≻ H, Π[n, m]) = 2/3 × 22 + 1/3 × 23 + 1 × 15 + 2/3 × 29 + 0 × 4+1/3 ×7 = 177/3
最大，而H ≻ D ≻ J与社会偏好集的肯德尔距离最小，式9.9和9.10的等价性得到实例验证。
KY方法是一个NP-Hard问题 [41]，需要遍历整个偏好排名空间Π，难以直接优化求解。可以
证明，KY方法与其他几种方法之间存在紧密联系：它是孔多塞方法的最大似然估计 [42]，并且还
与波达计数法对赢家和输家持有完全一致的偏好 [43]。
9.3 位置筛选法
$%"&'#(
70
)!*+",$
9.4. 概率模型法
!"#
DH J
D – 49 60
H 51 – 66
J 40 34 –
偏好排名 排名分值 偏好排名 排名分值
D ≻ H ≻ J 175 D ≻ J ≻ H 143
H ≻ D ≻ J 177 H ≻ J ≻ D 157
J ≻ D ≻ H 123 J ≻ H ≻ D 125
表 9.5: 序对偏好计票表（左）与偏好排名分值分布表（右）
D ≻ H ≻ JD≻ J ≻ HH≻ D ≻ JH≻ J ≻ DJ≻ D ≻ HJ≻ H ≻ D
D ≻ H ≻ J 0 1/3 1/3 2/3 2/3 1
D ≻ J ≻ H 1/3 0 2/3 1 1/3 2/3
H ≻ D ≻ J 1/3 2/3 0 1/3 1 2/3
H ≻ J ≻ D 2/3 1 1/3 0 2/3 1/3
J ≻ D ≻ H 2/3 1/3 1 2/3 0 1/3
J ≻ H ≻ D 1 2/3 2/3 1/3 1/3 0
τ(π, Π[n, m]) 125/3 157/3 123/3 143/3 177/3 175/3
表 9.6: 偏好排名肯德尔距离矩阵
9.3.1. 单记可让渡投票制
单记可让渡投票制（single transferable voting，STV），肇始于19世纪50年代，由英国的Thomas
Hare和丹麦的George Andrae发明，用以选出唯一的赢家。
1871年美国建筑师威廉·罗伯特·威尔William Robert Ware出排序复选制（instant-runoff
voting，IRV），也称选择投票制（alternative voting）或偏好投票制（preferential voting）， 1918年
始澳大利亚众议院选举、2010年奥斯卡最佳影片的评选都采纳了IRV方法。IRV方法统计候选人的
第一票数（first choice or first preference），任何候选人只要第一票数超出半数则胜出，选举结束；
否则，将第一票数最低的候选人剔除，所有含有此候选人的偏好列表也要做剔除处理，重新统计第
一票数，依次类推，直至有候选人以超过半数胜出。显然，IRV是STV的一个特例。
9.4 概率模型法
9.4.1. 马洛斯模型
马洛斯模型（Mallows Model）是一种基于距离的排名聚合方法，它利用排列空间Π[n]上定义
的距离度量指标，比如肯德尔距离、斯皮尔曼距离等，确定排列空间上的概率分布。假设初始排列
（location permutation）为σ，对任意的排列π ∈ Π[n]，马洛斯模型定义如下形式的概率分布
P (π|σ; c)=
exp{−c × d(π, σ)}
(
π
′
∈Π[n]
exp
,
− c × d ( π
′
, σ)
-
, (9.11)
$%"&'#(
71
)!*+",$
搜索与排名 Searching and Ranking
!"#
其中参数c>0称作离散因子（disperse）， 用 以 控 制 排 列 空 间 上 的 距 离 权 重 。 根 据 模 型 定 义 ， 构 建
排列空间上的概率分布需要遍历整个空间，其计算复杂度高达O(n!)，以致于无法实际应用。
9.4.2. 瑟斯顿模型与TrueSkill排名
9.4.3. 布雷德利─特里─卢斯模型
9.4.4. 普拉基特─卢斯模型
普拉基特─卢斯模型（Plackett-Luce model，也称“卢斯模型”，简称PL模型）是一种分步排
名方法，假设每个参与排名的对象都对应一个隐性分值z，利用隐性分值评估Π[n]的分布概率。如
果决策者根据种准则产生一个排列π，则对象π
−1
(i)在排列π中排到第i位的概率P
i
，依赖于其自
身的评分z
π
−1
(i)
，以及其他所有排名在它下面的其他所有对象的评分之和
(
i≤k≤n
z
π
−1
(k)
。PL模型对
每个评分统一作单调变换，有如下形式的定义
P
i
=
exp(z
π
−1
(i)
)
(
i≤k≤n
exp(z
π
−1
(k)
)
, 1 ≤ i ≤ n.
根据独立性假设，则由隐性评分列表生成排列π的概率为
P (π)=
n
!
i=1
P
i
=
n
!
i=1
exp(z
π
−1
(i)
)
(
i≤k≤n
exp(z
π
−1
(k)
)
. (9.12)
如果计算排列π的生成概率，只考虑位置靠前的对象评分信息，排名靠后的对象评分信息直接
忽略掉，实际上对于概率评估影响甚微。比如，只考虑前K个位置上的对象评分信息，可以计算生
成排列π的近似生成概率P (π; K)，则有定义
P (π; K)=
K
!
i=1
exp(z
π
−1
(i)
)
(
i≤k≤n
exp(z
π
−1
(k)
)
≥ P (π), (9.13)
这个概率称作n个对象排列的TopK概率。当K = n − 1时，由于P
n
=1，则有
P (π; n − 1) = P (π; n)=P (π) .
当K =1时有
P (π; 1) =
exp(z
π
−1
(i)
)
(
i≤k≤n
exp(z
π
−1
(k)
)
. (9.14)
如果记n个对象生成的所有排列集合为Π[n]，我们可以建立P (π)与P (π,K)二者之间的联系：
P (π; K)=
"
σ ∈ Π[n,K,π]
P (σ). (9.15)
例9.5. 假设四个对象{1, 2, 3, 4}存在隐性分值Z = {0.5, 0.8, 0.3, 0.1}，随机排列可以生成4! = 24种可
能的结果，如图9.2所示的多面体，每个定点对应一个排列，根据卢斯模型可以计算生成各个排列
$%"&'#(
72
)!*+",$
9.4. 概率模型法
!"#
的概率。如表9.7所示，所有排列概率之和等于1，排列π = ⟨1, 2, 3, 4⟩的概率P (π)=0.068102079，
排列π = ⟨2, 1, 4, 3⟩的概率P (π)=0.063594464。如果根据隐性分值进行排名，可以得到最理想
的排列π = ⟨2, 1, 3, 4⟩，其概率最大P (π)=0.07767445，对应图9.2中最大节点，最不理想的排列
是π = ⟨4, 3, 1, 2⟩，其概率最小P (π)=0.019200285，对应图9.2中最小节点。
图 9.2: 排列分布及分布肯德尔距离，1234 ! ⟨1, 2, 3, 4⟩
π ⟨1, 2, 3, 4⟩ ⟨1, 2, 4, 3⟩ ⟨1, 3, 2, 4⟩ ⟨1, 3, 4, 2⟩ ⟨1, 4, 2, 3⟩ ⟨1, 4, 3, 2⟩
P (π) 0.068102079 0. 055757275 0.05019727 0.024927228 0.038285447 0.023221297
π ⟨2, 1, 3, 4⟩ ⟨2, 1, 4, 3⟩ ⟨2, 3, 1, 4⟩ ⟨2, 3, 4, 1⟩ ⟨2, 4, 1, 3⟩ ⟨2, 4, 3, 1⟩
P (π) 0.07767445 0.063594464 0.069244944 0.046416276 0.052066751 0.042628653
π ⟨3, 1, 2, 4⟩ ⟨3, 1, 4, 2⟩ ⟨3, 2, 1, 4⟩ ⟨3, 2, 4, 1⟩ ⟨3, 4, 1, 2⟩ ⟨3, 4, 2, 1⟩
P (π) 0.047184467 0. 023431114 0.057067546 0.038253525 0.020143783 0.027191263
π ⟨4, 1, 2, 3⟩ ⟨4, 1, 3, 2⟩ ⟨4, 2, 1, 3⟩ ⟨4, 2, 3, 1⟩ ⟨4, 3, 1, 2⟩ ⟨4, 3, 2, 1⟩
P (π) 0.03430199 0.020805209 0.040900468 0.033486473 0.019200285 0.025917675
表 9.7: 排列分布表
根据定义，Top-2的排列分布（表9.8）可通过Top-3的排列分布计算，比如⟨1, 2, ∗, ∗⟩的概率等
于⟨1, 2, 3, 4⟩ 与⟨1, 2, 4, 3⟩ 的概率之和，即有
P (⟨1, 2, 3, 4⟩)+P (⟨1, 2, 4, 3⟩)=0.068102079 + 0.055757275
= P (⟨1, 2, ∗, ∗⟩)=0.123859355.
$%"&'#(
73
)!*+",$
搜索与排名 Searching and Ranking
!"#
Top-1排列分布（表9.8）可以通过Top-2的排列分布进行计算，如⟨3, ∗, ∗, ∗⟩的概率又等于⟨3, 1, ∗, ∗⟩、
⟨3, 2, ∗, ∗⟩和⟨3, 4, ∗, ∗⟩ 的概率之和，即有
P (⟨3, 1, ∗, ∗⟩)+P (⟨3, 2, ∗, ∗⟩)+P (⟨3, 4, ∗, ∗⟩)=0.070615583 + 0.095321069 + 0.047335044
= P (⟨3, ∗, ∗, ∗⟩)=0.2133.
π;2 ⟨1, 2, ∗, ∗⟩ ⟨1, 3, ∗, ∗⟩ ⟨1, 4, ∗, ∗⟩ π;1 ⟨1, ∗, ∗, ∗⟩
P (π; 2) 0.123859355 0.075124501 0.061506748 P (π; 1) 0.2605
π;2 ⟨2, 1, ∗, ∗⟩ ⟨2, 3, ∗, ∗⟩ ⟨2, 4, ∗, ∗⟩ π;1 ⟨2, ∗, ∗, ∗⟩
P (π; 2) 0.141268922 0.11566122 0.094695399 P (π; 1) 0.3516
π;2 ⟨3, 1, ∗, ∗⟩ ⟨3, 2, ∗, ∗⟩ ⟨3, 4, ∗, ∗⟩ π;1 ⟨3, ∗, ∗, ∗⟩
P (π; 2) 0.070615583 0.095321069 0.047335044 P (π; 1) 0.2133
π;2 ⟨4, 1, ∗, ∗⟩ ⟨4, 2, ∗, ∗⟩ ⟨4, 3, ∗, ∗⟩ π;1 ⟨4, ∗, ∗, ∗⟩
P (π; 2) 0.055107202 0.074386937 0.045117957 P (π; 1) 0.1746
表 9.8: Top-2与Top-1排列分布表
9.4.5. Elo排序系统
9.4.6. Colley方法
9.4.7. Massey方法
由于地理、文化等社会人文环境的差异，世界范围内已经诞生数量可观的社会选择方法。为
了分析各种方法，便于对其区分和归类，人们出一系列性质良好的投票系统准则，如多数准则
（majority criterion）、 孔 多 塞 一 致 性 准 则 （ Condorcet consistency）等单赢家投票系统准则。我们
使用一个小节专门来介绍它们。
9.5 投票系统准则
定义9.4 (多数准则). 如果半数以上的选民选择（或偏好）某个候选人，则此人一定是社会选择。
推论9.1. 孔多塞方法、IRV方法、Bucklin方法和多数投票方法都满足多数准则。
定义9.5 (孔多塞准则). 如果存在一个候选人，在和其他候选人的一对一循环对决中总能胜出，则此
候选人必然胜出。
推论9.2. 如果一个单赢家投票系统满足孔多塞准则，则它必然也满足多数准则。
推论9.3. 布莱克方法、柯普兰方法、道奇森方法、凯梅尼─杨格方法、最小最大法、南森方法、有
序对方法（ranked pairs）和舒尔茨方法都满足孔多塞准则。
$%"&'#(
74
)!*+",$
9.6. 阿罗不可能定理
!"#
定义9.6 (一致性准则). 假设将社会偏好集Π[n, m]任意分割成两个或多个子集，使得某个候选
人x ∈ A是每个社会偏好子集上的社会选择，如果x也是Π[n, m]上的社会选择，则称对应社会选择
函数满足一致性准则（consistency criterion）或可分性准则（separability criterion）。
推论9.4. 如果一个排序投票系统（ranked voting system）满足一致性，当且仅当它也是一个位置投
票系统（positional voting system）。波达方法满足一致性，但柯普兰方法、IRV方法、凯梅尼─杨格
方法、最小最大法、有序对方法（ranked pairs）和舒尔茨方法都违反一致性准则。
定义9.7 (排名一致性准则). 假设将社会偏好集Π[n, m]任意分割成两个或多个子集，使得某个排
序π ∈ Π[n]是每个社会偏好子集上的社会选择排序，如果π也是Π[n, m]上的社会选择排序，则称对
应社会选择函数满足排名一致性准则（ranking consistency criterion）。
推论9.5. 凯梅尼─杨格方法满足排名一致性准则。
9.6 阿罗不可能定理
1951年，美国经济学家肯尼斯·阿罗Kenneth Arrow [44, 45]使用数学公理化的方法研究社会
决策时，证明了一个重要的结论：如果众多的社会成员具有不同的偏好，而社会又有多种备选
方案，那么在民主的制度下不可能得到令所有的人都满意的结果。 换句话说，依靠简单的“少数
服从多数”的投票原则，在各种个人偏好中选择出一个共同一致的顺序，无法实现。 简而言之，
阿罗证明“完美的投票体系是不存在的”，即声名远播的阿罗不可能定理（Arrow’s Impossibility
Theorem）或阿罗悖论（Arrow’s Paradox）。阿罗悖论不啻于一声惊雷，对当时的政治哲学和福利
经济学产生了巨大的冲击，并为阿罗摘得1972年的诺贝尔经济学奖。
社会选择，在数学上表示一个建立在所有个体偏好上的函数（或映射），其性质反映了一定的
价值规范，如公民权、帕累托有效、无独裁性等。社会选择最重要的问题是：能否从逻辑上协调所
有这些价值规范。阿罗使用公理性的证明，向人们宣告一个不幸的消息：世上没有同时满足个人偏
好的无限制性、帕累托有效
➊
、非相关目标独立性与非独裁性四个基本公理的社会选择函数。
定义9.8 (个人偏好的无限制性). 如果社会选择函数F允许所有逻辑上可能存在的个人偏好自由表
达，则称其满足无限制性（unrestricted domain）或完整性（universality）。
定义9.9 (帕累托有效性). 对任意x, y ∈ A，如果所有决策者一致认定x ≻ y，则社会偏好列表π
F
也
有x ≻ y，即x ≻
F
Π[n,m]
y，则称社会选择函数F满足帕累托有效性（Pareto efficiency）， 也 称 一 致 同
意性（unanimity）。
➊ 帕累托Vilfredo Pareto（1848～1923）， 意 大 利 经 济 学 家 和 社 会 学 家 。 曾 在 都 灵 大 学 就 读 ， 后 在 意 大 利 一 家 大 型 铁 路 公 司 担 任 工 程 师 ，
升至主管，1893年起任瑞士洛桑大学教授。在经济学和社会学两个领域做出突出贡献，1906年出帕累托最优状态（Pareto optimal）的
概念，也成帕累托有效性（Pareto efficiency）， 奠 定 了 现 代 福 利 经 济 学 的 基 础 。 他 认 为 ， 只 要 有 可 能 使 至 少 一 个 人 更 富 裕 ， 而 同 时 又 能 使
其他人保持在原来的生活水平，社会资源分配就没有达到最佳状态。
$%"&'#(
75
)!*+",$
搜索与排名 Searching and Ranking
!"#
定义9.10 (非相关目标独立性). 对于两个社会偏好集Π[n, m]={π
i
}
m
i=1
与Π
′
[n, m]={π
′
i
}
m
i=1
，
π
i
与π
′
i
对应同一个决策者，1 ≤ i ≤ m。如果每个决策者关于x, y ∈ A的个人偏好保持不变：
x ≻
π
i
y ⇔ x ≻
π
′
i
y, 1 ≤ i ≤ m, (9.16)
则集体关于x, y的社会偏好在两个社会偏好集Π[n, m]和Π
′
[n, m]上也不会发生变化：
x ≻
F
Π[n,m]
y ⇔ x ≻
F
Π
′
[n,m]
y, (9.17)
此时称社会选择函数F满足非相关目标独立性（Independence of Irrelevant Alternatives，IIA）。
定义9.11 (非独裁性). 对于一个决策者，如果社会选择F完全等价于其个人偏好π，即
x ≻
π
y ⇔ x ≻
F
Π
y, (9.18)
则称其为独裁者（dictator）。 如 果 集 合 M中没有独裁者，则称社会选择函数F满足非独裁性
（non-dictatorship）。
定义9.12 (线性序). 非空集合A上的二元关系≻称作是线线线性性性序序序（linear ordering），如果它满足
• 反对称性（anti-symmetric）：对任意的x, y ∈ A，只要x ≻ y, y ≻ x，都有x = y，
• 传递性（transitive）：对任意的x, y, z ∈ A，只要x ≻ y, y ≻ z，都有x ≻ z，
• 完备性（complete）：对任意的x, y ∈ A，要么x ≻ y，要么y ≻ x。
定义9.13 (社会福利函数). 如果社会选择函数F : Π[n, m] -→ Π[n]是A上的一个线性序，则称其为线
性投票规则或社会福利函数（social welfare function），而其完备性对应于个人偏好的无限制性。
定理9.2 (阿罗不可能性定理). 如果|A| = n>2，则兼具帕累托有效性、非独裁性和IIA的线性投票
规则F不存在。换言之，兼具帕累托有效性和IIA的线性投票规则一定存在独裁者。
我们下面详细介绍1998年诺贝尔经济学奖得主阿马蒂亚·森Amartya Sen
➊
对阿罗不可能性定
理的证明思路，为此先引入决定性联盟（decisive coalition）的概念。
定义9.14 (决定性联盟). 对于非空集合M
c
⊂ M，以及x, y ∈ A，如果满足
x ≻
F
Π[A,M
c
]
y ⇔ x ≻
F
Π[A,M]
y, (9.19)
则称M
c
是决定社会选择F关于(x, y)偏好的决定性联盟。如果对任意x, y ∈ A，M
c
都是决定F关
于(x, y)偏好的决定性联盟，则称M
c
是F的决定性联盟。如果M
c
是所有偏好x甚于y的决策者集
合，
➊ 阿马蒂亚·森1933年生于英属印度西孟加拉邦桑蒂克尼盖登，1953年获加尔各答大学文学学士学位，1955年前往剑桥大学攻读第二个
学士学位，并于1959年在剑桥大学获得博士学位。1971年起在伦敦经济学院任教，1977年起任牛津大学经济学教授，70年代末转教于美国
哈佛大学。1998年1月又返回英国剑桥大学，担任三一学院（Trinity College，Cambridge）院长。他克服了阿罗不可能定理衍生的难题，
对福利经济学基础理论做出巨大贡献。
$%"&'#(
76
)!*+",$
9.6. 阿罗不可能定理
!"#
决定性联盟可以操控社会选择，严重侵害其他社会成员的利益。如果|M
c
| > 1，决定性联盟构
成寡头，在寡头集团操控下的政治生态形成寡头政治。如果|M
c
| =1，决定性联盟就是独裁者。我
们可以证明：如果F满足帕累托有效性，则M是F的决定性联盟。森巧妙地利用决定性联盟，推导
出阿罗不可能性定理：兼具个人偏好无限制性、帕累托有效性和IIA的线性投票规则由单点集决定
性联盟所操纵，即存在独裁者。
定义9.15 (弱决定性联盟). 给定投票规则F，称非空集G ⊆ N是F对(x, y)的弱决定性联盟，若对
任意排序组合π，只要G中的成员恰好是x ≻ y 的所有赞成者，则社会排序F(π)中也有x ≻ y，
即x ≻
F
π
y。
若G是F对(x, y)的决定性联盟，则G也是F对(x, y)的弱决定性联盟。 反过来是否成立呢？如
果F满足帕累托条件和独立性条件，则反过来不仅成立，而且我们还有如下更强的结论：
引理9.1. 设F是满足帕累托条件和独立性条件的线性投票规则。若G是F对(x, y) 的弱决定性联盟，
则G是F的决定性联盟，即G是F对任意(x
′
,y
′
)的决定性联盟。
证明： 设F是满足帕累托条件和独立性条件的线性投票规则。设G是F对(x, y)的弱决定性联盟，任
给(x
′
,y
′
)，我们证明G是F对任意(x
′
,y
′
)的决定性联盟。不妨设x
′
,y
′
与x, y均不相同（相同的情况类
似可证）。任给排序组合
π
，使得
G
中所有成员一致认为
x
′
≻ y
′
，只需证x
′
≻
F
π
y
′
。考虑如下的排序
组合π
′
，其中
• G中的投票者认为：x
′
≻
F
π
y
′
；
• G之外的投票者认为：x
′
≻ x，y ≻ y
′
，y ≻ x，且对x
′
,y
′
的排序与π保持一致。
易见，G中中的成员恰好是x ≻ y的所有赞成者，由于G是F对(x, y)的弱决定性联盟，故x ≻
F
π
′
y。
由于在π
′
中所有人都认为x
′
≻ x且y ≻ y
′
，据帕累托条件有，x
′
≻
F
π
′
x且y ≻
F
π
′
y
′
，据社会排序的传
递性可得，x
′
≻
F
π
′
y
′
。注意到π与π
′
关于x
′
,y
′
的排序上是一样的，由独立性条件有，x
′
≻
F
π
y
′
，证
毕。现在我们可以证明下面的收缩引理了。
引理9.2 (收缩引理). 设F是满足帕累托条件和独立性条件的线性投票规则。若非单点集G是F的决
定性联盟，则G的某个真子集G
′
也是F的决定性联盟。
证明： 由于G是非单点集，故可将G拆分成两个不相交的非空子集G
1
和G
2
。考虑满足如下条件的
排序组合π（由于备选项超过两个，故可以做到）：
• G
1
中的投票者认为：x ≻ y ≻ z；
• G
2
中的投票者认为：y ≻ z ≻ x；
• G之外的投票者（如果有的话）认为：z ≻ x ≻ y。
$%"&'#(
77
)!*+",$
搜索与排名 Searching and Ranking
!"#
注意到G中所有投票者都认为y ≻ z，由G是F的决定性联盟可得，y ≻
F
π
z。现在分别考虑两种情况
（由于F(π)是完全的，故有且仅有两种情况）：
• x ≻
F
π
z。任给排序组合π
′
，使得G
1
中的成员在π
′
中恰好是x ≻ z的所有赞成者，由于
在π中G
1
中的成员也恰好是x ≻ z的所有赞成者，故由独立性条件可得，x ≻
F
π
′
z，这意
味着G
1
是F对(x, z)的弱决定性联盟，再据引理1有，G
1
是F的决定性联盟。
• z ≻
F
π
x。此时，据F(π)的传递性有y ≻
F
π
x。同理于情况1可证，G
2
是F的决定性联盟。
综上，总有G的真子集是决定性联盟，证毕
➊
。
9.7 吉伯德－萨特思韦特定理
19世纪80年代，投票选举理论的奠基人之一查尔斯·勒特威奇·道奇森Charles Lutwidge
Dodgson
➋
开始关注对投票规则的研究，认为人们在投票时的行为更倾向于策略投票。个人出于
种目的策略性的需要，通过谎报自己的真实偏好，使得决策结果往有利的方向变化。个人谎报其
真实偏好，可能会造成损人不利己的后果，选出对各方均不利的候选人，对公众权利产生不利影
响。为此有必要深入研究策略性投票对选举的操纵，以期设计出防止策略性投票的社会选择方法。
如果在投票选举时存在策略性投票，个人所表达的偏好偏离其真实偏好，研究学者有理由重新
审视阿罗不可能定理。20世纪70年代密歇根大学的阿兰·吉伯德Allan Gibbard 和西北大学的马克
·萨特思韦特Mark Satterthwaite分别独立出两个几乎相同的定理，统称吉伯德－萨特思韦特定
理（Gibbard–Satterthwaite Theorem）防策略投票的不可能性定理，引起数学、经济学、计算机
科学和哲学等诸多领域学者的广泛关注。
定义9.16 (战略免疫性). 如果其他个体均真实披露自己偏好信息，某个特定个体只有真实显
示自己的偏好时社会选择对自己才最有利，则称对应社会选择规则可免于战略性投票操纵
（non-manipulable），即具有战战战略略略免免免疫疫疫性性性（strategy-proofness）。
定理9.3 (吉伯德－萨特思韦特定理). 在社会选择规则集合内不存在同时满足个人偏好无限制性、帕
累托有效性、非独裁性、传递性和战略免疫性五个基本公理的选择规则。
根据吉伯德─萨特思韦特定理，我们意识到非独裁性和战略免疫性两个属性可能存在内在矛
盾，任何合理的社会选择规则都难以两面兼顾：在所有可能的社会选择规则下，能够同时满足个人
偏好无限制性、帕累托有效性、传递性和战略免疫性的只有独裁规则。如果存在一个社会选择规则
兼具个人偏好无限制性、帕累托有效性、非独裁性和传递性，则它必定无法免于战略性投票操纵。
➊ Logic：阿罗不可能性定理的证明
➋ 查尔斯·勒特威奇·道奇森（1832–1898）， 笔 名 路 易 斯 · 卡 罗 尔 Luis Carroll，英国数学家、《艾丽丝漫游奇境记》及续篇《爱丽丝镜
中奇遇》的作者。他天赋异禀，在几何学、线性代数、矩阵与逻辑学面都颇有研究，写出十多本数学著作，为线性代数与概率论两大领域
供了新思路。
$%"&'#(
78
)!*+",$
9.8. 梅定理
!"#
许多社会选择方法满足一系列良好的公理性质，但是却免不了受到战略性投票的操控，总是存
在隐瞒自己真实偏好的个体，试图取得对自己有利的选举局面。人们无法设计出一个确保或诱使
所有个体能够道出其真实偏好（revelation principle）的社会选择机制。人们只能另辟蹊径，将目
光转移到社会选择战略性操纵复杂度的研究，通过增加战略性投票操纵的成本，以降低人们投出
违心选票的动机，比如20世纪90年代乔治亚理工学院教授约翰·巴托尔迪三世John Bartholdi III等
人[46, 41]的卓越工作，促进了计算社会选择的快速发展：以高计算复杂度阻止策略性投票操纵，
间接地迫使个体对其偏好做出真实的回应。由于选举操纵能够抑制部分个体耍诈，已然成为衡量一
个社会选择准则优劣性的一个指标。
9.8 梅定理
定义9.17 (匿名性). 如果集体选择的结果只依赖于各个个体的偏好与决策，与特定决策由具体谁做
出无关，则称此集体选择具备匿匿匿名名名性性性（anonymity），或称决策者是对称主体。
定义9.18 (中立性). 如果决策规则在任意两个备选对象之间是中立的，则称它具备中中中立立立性性性
（neutrality）。
定义9.19 (正向响应). 正向响应（positively responsive）
定理9.4 (梅定理May’s Theorem). 在集体选择的备选对象是二元的情况下，一种集体决策规则是简
单多数规则，当且仅当它满足匿名性、中立性和正向响应。
9.9 排名聚合
排名聚合（Rank Aggregation）， 也 称 数据融合（Data Fusion）， 源 于 投 票 选 举 问 题 ， 通 过 融
合多个来源的对象排名结果，从而更加准确地反映对象间的优先等级秩序。目前，排名聚合已经在
网络信息检索、统计检验、体育竞技排名等多个领域得到广泛应用，比如元搜索引擎接收用户交
的检索词，同时向多个基本搜索引擎的发送检索请求，将多个基本搜索引擎的搜索结果聚合而形成
最终结果反馈给用户。
排名聚合的目标是从Π[n]中搜索一个理想的排列ˆπ，使得它和所有已知排名列表{π
1
, π
2
,...}保
持尽可能的一致，数学上等价于解一个优化问题：
ˆπ = arg max
π ∈ Π[n]
"
i
s(π, π
i
) = arg min
π ∈ Π[n]
"
i
d(π, π
i
), (9.20)
其中s(π, σ)是衡量两个排名列表π和σ之间的相似性指标，d(π, σ)是由相似性指标s(π, σ)导出的种
距离度量，如肯德尔Tau。
例9.6. 人们在使用搜索引擎检索信息时，比如提交检索词“health”， 不 同 搜 索 引 擎 搜 索 并 返 回 的
结果通常也不相同。目前，正常提供服务的搜索引擎不下于1,000个。 2011年10 月22 日，我们使
$%"&'#(
79
)!*+",$
搜索与排名 Searching and Ranking
!"#
编号 网址 编号 网址
1 abcnews.go.com/health 8 www.cnn.com/HEALTH
2 en.wikipedia.org/wiki/Health 9 www.health.com
3 en.wikipedia.org/wiki/Health care 10 www.mayoclinic.com
4 health.yahoo.net 11 www.nytimes.com/pages/health/
5 health.gov 12 www.pacificprime.com
6 reuters.com/news/health 13 www.webmd.com
7 wiki.ask.com/Health
表 9.9: 九个搜索引擎检索关键词“health”的十三条搜索结果
搜索引擎 搜索结果 搜索引擎 搜索结果 搜索引擎 搜索结果
AOL ⟨9, 13, 10, 2, 8⟩ Bing ⟨2, 13, 4, 5, 11⟩ DuckDuckGo ⟨4, 13, 2, 1, 6⟩
Excite ⟨13, 2, 11, 4, 8⟩ Google ⟨2, 3, 9, 4, 12⟩ HotBot ⟨2, 13, 4, 8, 10⟩
Lycos ⟨2, 13, 4, 8, 10⟩ Teoma ⟨9, 13, 10, 7, 8⟩ Yahoo! ⟨13, 2, 4, 8, 10⟩
表 9.10: 九个搜索引擎检索关键词“health”的前5条搜索结果
用9个搜索引擎：AOL、Bing、DuckDuckGo、Excite、Google、HotBot、Lycos、Teoma和Yahoo!，分
别检索关键词“Health”，提取每个搜索引擎的前5条搜索条目汇集成13条搜索结果，如表9.9所示根
据字母顺序为搜索条目对应网址编号，表9.10是每个搜索引擎前5条搜索条目的排列结果。根据波
达计数法则对搜索条目进行评分，如表9.11所示，第2 列至第14列是各个搜索引擎在对应搜索条目
上的评分，聚合排名的结果是
π = ⟨13, 2, 4, 8, 10, 9, 11, 3, 1/5/7, 6/12⟩,
其中a/b表示a和b评分相同，无法区分。如果我们预先对各个搜索引擎设定一个权值，比如
ω = {ω
A
, ω
B
, ω
D
ω
E
, ω
G
, ω
H
, ω
L
, ω
T
, ω
Y
}
= {0.80, 0.98, 0.80, 0.80, 1.00, 0.85, 0.85, 0.88, 0.95},
重新计算加权评分，则有聚合排名结果
π
ω
= ⟨2, 13, 4, 8, 10, 9, 11, 3, 5, 12, 7, 1, 6⟩.
9.9.1. 序对投票准则
设有n个候选人{1, 2,...,n}，每个选民都从中选出部分候选人并排列，所有选民的排列集合记
作Π。每个排列π ∈ Π反映一个选民对部分候选人的偏好，越是其喜欢的候选人在选票中的排名越
靠前。我们出一种序对投票（pairwise voting, PV）准则，根据所有候选人组合在π 中的相对名
$%"&'#(
80
)!*+",$
9.9. 排名聚合
!"#
Rank 1 2 3 4 5 6 7 8 9 10 11 12 13
A(0.80) 10 9 13 11 12
B(0.98) 13 11 10 9 12
D(0.80) 10 11 13 9 12
E(0.80) 12 10 9 11 13
G(1.00) 13 12 10 11 9
H(0.85) 13 11 10 9 12
L(0.85) 13 11 10 9 12
T(0.88) 10 9 13 11 12
Y(0.95) 12 11 10 9 13
TS 10 97 12 77 10 9 10 57 37 49 20 9 98
WTS 8.0 85.64 12.0 68.33 9.8 7.2 8.8 48.82 32.84 42.33 17.62 9.0 84.67
表 9.11: 波达排名与加权波达排名列表：首列括号内数值是各搜索引擎的权值，TS是各条目的总得
分（Total Score）， WTS是各条目的加权总得分（Weighted Total Score）。
次进行评分。PV准则对所有没有入选π的候选人等同视之，则有π(i)=|π| +1。对于个候选人组
合(i, j)，我们根据如下形式的序对投票准则构建序对评分矩阵V (π) ∈ R
n×n
：
v
π
(i, j)=
π(j) − π(i)
min{π(i), π(j)}
. (9.21)
当π(i) < π(j)时，候选人i在π中的排名比j的排名靠前，则v
π
(i, j) > 0；当π(i) > π(j)时，候选
人i在π中的排名比j的排名靠后，则v
π
(i, j)=−v
π
(j, i) < 0；当v
π
(i, j)=v
π
(j, i)时，则v
π
(i, j)=0。
由此可知，序对评分矩阵V (π)是一个反对称矩阵V (π)=−V
T
(π)。
每个候选人对应评分矩阵V 的一行，如果计算序对评分矩阵的行和，则可以直接确定候选人从
单个选民排名列表中的综合得分。实际上，评分矩阵每个行元可以看作是一次比赛结果。如果比赛
胜利，则得分为正，比赛失利则得分为负。对于任意一个候选人i，它从个选民排名列表π ∈ Π获
得的总分记作V
i
(π)，则有
V
i
(π)=
"
1≤j≤n
v
π
(i, j)=
"
1≤j≤n
π(j) − π(i)
min{π(i), π(j)}
. (9.22)
如果记P
i∗
(π)={1 ≤ j ≤ n, π(i) < π(j)}，P
∗i
(π)={1 ≤ j ≤ n, π(j) < π(i)}分别对应π中排
到候选人i之后的候选人集合、排到候选人i之前的候选人集合，利用它改写上式，则有
V
i
(π)=
(
1≤j≤n
π (j)−π(i)
min{π(i),π(j)}
=
(
j∈P
i∗
(π )
π (j)−π(i)
π (i)
+
(
j∈P
∗i
(π )
π (j)−π(i)
π (j)
=
(
j∈P
i∗
(π )
#
π ( j)
π( i)
− 1
$
+
(
j∈P
∗i
(π )
#
1 −
π (i)
π (j)
$
,
=
(
π (i)+1 ≤ k≤|π|
#
k
π (i)
− 1
$
+[n − |π|][
|π|+1
π (i)
− 1] +
(
1≤k≤π(i)−1
#
1 −
π (i)
k
$
.
(9.23)
$%"&'#(
81
)!*+",$
搜索与排名 Searching and Ranking
!"#
可以证明：V
i
(π)是一个关于π(i)单调不增函数。当候选人落选π，π(i)=|π| +1，前两部分都等于
零，则有
V
i
(π)=|π| − π(i)
"
1≤k≤|π|
1
k
. (9.24)
对于排在首位的候选人i，π(i)=1，其分值V
1
(π)=m(2n − m − 1)/2。
我们根据PV准则确定每个选民排名列表产生的评分矩阵，通过行和运算获得每个候选人在各
个排名列表π所得综合评分。如果累积候选人在所有选民排列上的综合评分，从而可以算得其最终
投票得分
V
i
=
"
π ∈ Π
V
i
(π)=
"
π∈Π
"
1≤j≤n
v
π
(i, j)=
"
π ∈ Π
"
1≤j≤n
π(j) − π(i)
min{π(i), π(j)}
, 1 ≤ i ≤ n. (9.25)
我们依据候选人最终投票得分进行排名。此外，如果我们拥有各个选民的权值信息ω，可以对聚合
评分进行加权处理，则有
V
i
=
"
π ∈ Π
ω
π
V
i
(π)=
"
π ∈ Π
ω
π
"
1≤j≤n
π(j) − π(i)
min{π(i), π(j)}
, 1 ≤ i ≤ n. (9.26)
我们下面使用例9.6介绍PV准则，搜索条目{1,...,13} 对应13个候选人，9个基本搜索引擎：AOL、
V
i
(π
A
) V
i
(π
B
) V
i
(π
D
) V
i
(π
E
) V
i
(π
G
) V
i
(π
H
) V
i
(π
L
) V
i
(π
T
) V
i
(π
Y
) V
i
1 -8.7 -8.7 -0.1 -8.7 -8.7 -8.7 -8.7 -8.7 -8.7 -69.68
2 -0.1 50.0 6.5 18.0 50.0 50.0 50.0 -8.7 18.0 233.72
3 -8.7 -8.7 -8.7 -8.7 18.0 -8.7 -8.7 -8.7 -8.7 -51.60
4 -8.7 6.5 50.0 -0.1 -0.1 6.5 6.5 -8.7 6.5 58.43
5 -8.7 -0.1 -8.7 -8.7 -8.7 -8.7 -8.7 -8.7 -8.7 -69.68
6 -8.7 -8.7 -4.8 -8.7 -8.7 -8.7 -8.7 -8.7 -8.7 -74.42
7 -8.7 -8.7 -8.7 -8.7 -8.7 -8.7 -8.7 -0.1 -8.7 -69.68
8 -4.8 -8.7 -8.7 -4.8 -8.7 -0.1 -0.1 -4.8 -0.1 -40.80
9 50.0 -8.7 -8.7 -8.7 6.5 -8.7 -8.7 50.0 -8.7 54.30
10 6.5 -8.7 -8.7 -8.7 -8.7 -4.8 -4.8 6.5 -4.8 -36.25
11 -8.7 -4.8 -8.7 6.5 -8.7 -8.7 -8.7 -8.7 -8.7 -59.22
12 -8.7 -8.7 -8.7 -8.7 -4.8 -8.7 -8.7 -8.7 -8.7 -74.42
13 18.0 18.0 18.0 50.0 -8.7 18.0 18.0 18.0 50.0 199.30
ω 0.80 0.98 0.80 0.80 1.00 0.85 0.85 0.88 0.95
表 9.12: 序对投票准则下的搜索排名聚合
Bing、 DuckDuckGo、 Excite、 Google、 HotBot、 Lycos、 Teoma和Yahoo!构成评价搜索条目9个
$%"&'#(
82
)!*+",$
9.9. 排名聚合
!"#
选民，分别产生一个等长度（|π| =5）的搜索排名列表：
π
A
= ⟨9, 13, 10, 2, 8⟩, π
B
= ⟨2, 13, 4, 5, 11⟩, π
D
= ⟨4, 13, 2, 1, 6⟩,
π
E
= ⟨13, 2, 11, 4, 8⟩, π
G
= ⟨2, 3, 9, 4, 12⟩, π
H
= ⟨2, 13, 4, 8, 10⟩,
π
L
= ⟨2, 13, 4, 8, 10⟩, π
T
= ⟨9, 13, 10, 7, 8⟩, π
Y
= ⟨13, 2, 4, 8, 10⟩.
依据PV评分准则，我们可以计算每一个搜索条目从9个排名列表得到的评分。如表9.12所示，第9个
搜索条目在Google给出的搜索排名列表中排在第3位，它从中可以得到的分值为
V
9
(π
G
)=
"
4≤k≤5
#
k
3
− 1
$
+ (13 − 5) (
5+1
3
− 1) +
"
1≤k≤2
#
1 −
3
k
$
=6.5 .
如表9.12最后一列所示，利用PV评分准则得到的聚合排名列表为
π = ⟨2, 13, 4, 9, 10, 8, 3, 11, 1, 5/7, 6, 12⟩.
如果使用例9.6中供的搜索引擎权向量ω（见表9.12末行数据），可以得到加权聚合排名
π = ⟨2, 13, 4, 9, 8, 10, 3, 11, 1, 7, 5, 6, 12⟩.
对比结果见图9.3，加权排名聚合结果是严格的不含平手项的聚合排名列表，加权结果破除了条
目5和7平手的局面，调整搜索条目8与10的相对位置。如果统计9个搜索引擎的搜索排名列表可以发
现，条目8排到条目10之前列表有4个，条目8排到条目10之后的只有2个，在其他列表都没有出现，
加权结果似乎更加合乎事实。
图 9.3: 序对投票准则下的搜索排名聚合（左）与加权排名聚合（右）
$%"&'#(
83
)!*+",$
第十章 排名收敛
传统数值迭代方法，如牛顿法、高斯-赛德尔方法、超松弛迭代、雅克比方法和幂法，大多根
据相邻迭代结果之间偏差界作为判定迭代收敛而终止迭代计算的准则，我们称其为数值收敛准则
（convergence in value）。
在网页搜索领域，PageRank是影响搜索引擎排名的一个重要因素，计算网页PageRank分值的
方法有多种，幂法是其中应用最广泛的一种，关于PageRank的研究论文达上万篇
➊
，然而绝大多数
关于PageRank 分值的计算都是基于数值收敛准则。由于PageRank主要应用在网页排名，相比精
确分值而言，我们更关心的是各个网页的排名顺序。
Peserico和Pretto在[47, 48]首次正式给出迭代排名算法的ϵ-排名收敛（convergence in rank）
直观性的定义，并出一些开放性的问题，比如数值收敛与排名收敛是否存在强关联性，链接图的
类型对两种收敛准则的影响等。本文旨在解决此类开放性问题，首先从“序”的概念出发，定义一
种基于序稳定性的收敛准则，再从数学上严格证明序稳定性与数值稳定性之间的联系。我们将序稳
定性收敛准则应用到PageRank算法的计算，从而大幅升网页排名计算的性能。
定义10.1 (排列模式). 对于一个长度为n的排列π = π
1
π
2
...π
n
，其中π
i
表示排列中的第i个数。比
如，在排列π = 391867452中，π
1
=3，π
9
=2。如果排列π存在一个子列（不必连续）与排列σ具
有相同的相对序关系，则称π包含σ，排列σ称作π的一个模模模式式式（pattern）， 并 记 作 σ ≤ π。由于排
列π = 391867452中含有子列（91674, 91675, 91672）， 则 称 它 含 有 模 式 σ = 51342。每个子列都称
作σ的一个复复复本本本 （copy）或出现一次σ。由于π不包含一个长度为4的递增序列，可以说它不包含模
式1234。
定义10.2 (序关系). 对于非空集合A上的二元关系≺，如果
1. 对任意的a ∈ A，都有a ≺ a，则称它满足自自自反反反性性性（reflexive）；
2. 对任意的a, b, c ∈ A，只要a ≺ b, b ≺ c，都有a ≺ c，则称它满足传传传递递递性性性（transitive）；
3. 对任意的a, b ∈ A，只要a ≺ b, b ≺ a，都有a ≺ a，则称它满足反反反对对对称称称性性性（anti-symmetric）；
4. 对任意的a, b ∈ A，要么a ≺ b，要么b ≺ a，则称它满足完完完备备备性性性（complete）。
➊ 根据Google Scholar搜索结果，截止2013年03月26日下午16:30，标题中包含PageRank关键词的可下载PDF文献有10,800条。
85
搜索与排名 Searching and Ranking
!"#
如果二元关系≺满足自反性和传递性，则称它是“预预预序序序”（pre-order）关系；如果还满足反对称性，
则称它是“偏偏偏序序序”（partial order）关系，A是“偏序集”（partial order set，poset）； 如 果 还 满 足 完
备性，则称它是“全全全序序序”（total order）关系，也称“线线线性性性序序序”（linear order）或“简简简单单单序序序”（simple
order）。
本文在不产生混淆的情况下，使用“序关系”表示n 维实向量，比如u =(u
1
,u
2
,...,u
n
)
T
各
元素（实数）之间的全序关系≤。
性质10.1. 实数集上的二元关系“<”是偏序关系，但不是全序关系；“≤”既是偏序也是全序关
系。
定义10.3 (排列).
定义10.4 (偏好关系).
定义10.5 (实数排列). 对于向量u ∈ R
n
，对向量所有元素按照二元序关系≤进行排列，如果逐
次记录所有维度上的排名序构成一个新的向量，则称它是向量u的“序序序数数数列列列”，记作π(u)，符
号π(u
i
) ∈ R表示u
i
的序序序/排排排 名名名 ， π
−1
i
(u)表示向量u按照“序关系”排在i位的元素，元素的数值越小
则“序”越大。 假设以u的序数列为标准，我们称π(u)为“““理理理想想想序序序数数数列列列”””，相应的各个元素的序为
“““理理理想想想序序序”””。
定义10.6 (保序映射). 假设≺
A
和≺
B
分别是定义在集合A和B上的全序关系，f : A -→ B是从集合A到
集合B上的一个双射，对任意的x, y ∈ A，如果x ≺
A
y，则有f(x) ≺
B
f(y)，那么f称作是从集
合A到集合B的一个保保保序序序映映映射射射（preserving mapping）。
定义10.7. 如果向量u, v ∈ R
n
满足
#
π(u
i
) −π(u
j
)
$#
π(v
i
) −π(v
j
)
$
> 0, ∀1 ≤ i ̸= j ≤ n，则称u和v同同同
序序序，否则称两者逆逆逆序序序。如果存在函数f : R
n
-→ R
n
，使得f(u)与u同序，则称f是保保保序序序函函函数数数。
例10.1. 对于5维向量u =(0.2, 0.1, 0.6, 0.5, 0.3)
T
，则0.1 ≤ 0.2 ≤ 0.3 ≤ 0.5 ≤ 0.6，则π(u)=
(4, 5, 1, 2, 3)，而π(u
5
)=3，π
−1
2
(u)=0.5。对于向量
v =(0.4, 0.2, 1.2, 1.0, 0.6)
T
,w=(0.3, 0.2, 0.7, 0.6.0.4)
T
它们与u相互“同序”。由此可知，对于任意向量u，变换
f : u
i
-→ u
i
+ a
g : u
i
-→ λu
i
其中，a ∈ R, λ > 0，则变换f, g都是保序的。
定义10.8 (序距). 对于任意的u, v ∈ R
n
，π(u), π(v) ∈ R
n
，如果δ : R
n
× R
n
-→ R满足如下性质：
1. 如果u和v同序，则δ(u, v)=0；
$%"&'#(
86
)!*+",$
!"#
2. 如果u和v逆序，将v中元素随机排列构成集合V ，对任意v
α
∈ V ，都有δ(u, v) ≥ δ(u, v
α
) ≥ 0；
3. 如果以π(u)为理想序数列，对任意的i<j<k，交换元素π
−1
i
(u)和π
−1
j
(u)的位置（序/排名），
得到u
β
，交换元素π
−1
i
(u) 和π
−1
k
(u)的位置，得到u
γ
，保持其他元素的位置不变，则δ(u, u
β
) >
δ(u, u
γ
)。
则称δ是u和v的序序序距距距（ordinal distance）。
定义10.9 (序稳定性与序收敛准则).
$%"&'#(
87
)!*+",$
