§ 9.3 公平选举是可能的吗?
什么是选举
所谓选举，其实质就是在评选人对候选人先后（优劣）
次序排队的基础上，根据某一事先规定的选举规则决定出候
选人的一个先后次序，即得出选举结果。现用 I={1,2,…,n}
表示评选人集合，用有限集 A={x,y,… }表示候选人集合，
用 >,=,<分别表示优于、等于、劣于，用 (x>y)i表示评选人 i
认为 x优于 y，用 (x>y)表示选举结果为 x优于 y并用 pi表示评选
人 i的排序,p表示选举结果。
A的排序应满足 以下 性质：
(1)择一性 关系式 (x>y),(x=y),(x<y)有且仅有一个成立Ayx ??,
(2)传递性 若 x≥y,y≥z,则必有 x≥zAzyx ??,,
? 简单多数规则
几种选举规则
它规定当且仅当 (x>y)i的评选人超过半数时选举结果才为 (x>y)。
有时要超过 2/3多数等
例 8 设 I={1,2,3},A={x,y,u,v},三位评选人的选票为
p1,x>y>u=v
p2,y>x>u>v
p3,x=u>v>y
根据选举规划, 结果应为
P,x>y>u>v
例 9 设 I={1,2,3},A={x,y,z}
p1,x>y>z
p2,y>z>x
p3,z>x>y
根据规则，自然应有
(x>y),(y>z)和 (z>x)
违反传递性（ 2）
简单多数规则的主要优点
是简单易行，使用方便。
但可惜的是这一规则有时
会违反传递性
? Borda数规则
记 Bi(x)为 p1中劣于 x的候选人数目，记,称 B(x)为 x
的 Borda数,Borda数规则规定 按 Borda数大小排列候选人的优劣次
序，即当 B(x)≥B(y)时有 (x≥y)，两关系式中的等号必须同时成立。
?
?
? n
i
i xBxB
1
)()(
对于例 11.9,计算出 B(x)=B(y)=B(z)=3
故选举结果为 x=y=z
用 Borda数规则得出
的结果更合乎常理
例 10 I={1,2,3,4},A={x,y,z,u,v},选票情况为
p1p2p3,x>y>z>u>v
P4, y>z>u>v>x
计算得 B(x)=12,B(y)=13
故选举结果为 y>x
但有三人认为 x优于 y
用 Borda数规则得出
的结果未必合理
能找到一种在任何情况下都, 公平, 的选举规则吗
什么是, 公平, 的选举规则
“公平, 的选举规则应当满足 以下 公理
公理 1 投票人对候选人排出的所有可能排列都是可以实现的。
公理 2 如果对所有的 i,有 (x≥y)i,则必须有 (x≥y)。
公理 3 如果在两次选举中，对任意 i，由 必可得出,
则由 必可得出 。
)1()( iyx ? )2()( iyx ?
)1()( yx ? )2()( yx ?
公理 4 如果两次选举中，每个投票人对 x,y的排序都未改变，则
对 x,y的排序两次结果也应相同。
公理 5 不存在这样的投票人 i,使得对任意一对候选人 x,y,只要
有 (x≥y)i,，就必有 (x≥y)。
有满足上述公理的选举规则吗
Arrow不可能性定理使上述想法终结
定理 9.1 如果至少有三名候选人，则满足公理 1~公理 5的选举规划
事实上是不可能存在的。
证：
将证明由公理 1~公理 4必可导出存在一个独裁者，从而违反了公理 5
首先引入决定性集合的概念。
称 I的子集 Vxy为候选人 x,y的决定性集合，如果由所有 Vxy中的 I
有 (x≥y) i必可导出 (x≥y) 。
显然决定性集合是必定存在，由公理 2或实际一次选举得到。
找出所有决定性集合中含元素最少的一个，不妨仍记为 Vxy 。
证明 Vxy只能含有一个元素 ——某评选人 i 。
反证 假定 Vxy至少含有两个元素,则 Vxy必可分解为两个非空集合的和
即
与 非空且不相交,且均不可能是任一对候选人的决定性集合
假设
)2()1( xyxyxy VVV ??
)1(xyV )2(xyV
??? xyVI
根据公理 1,以下选举是允许的：
当 时, （ x≥y≥z） i
当 时, （ z≥x≥y） i
当 时, （ y＞ z＞ x） i
其中 z是任一另外的候选人
)1(xyVi?
)2(xyVi?
xyVi?
考察选举结果
(x≥z) 是不可能，否则 是 x,z的决定性集合，故必
有 (z＞ x)。又 Vxy是 x,y的决定性能合，故必有 (x≥y) 。
由传递性 (z＞ x)。得 是 y,z的决定性集合，从而导出矛盾。
以上证明说明 Vxy不能分解,即 Vxy={i},i为某一投票人。
)1(xyV
)2(xyV
进一步说明,对于任意另外的候选人 z,V={i}也是 x,z的决定性集合 。
考虑另一次选举, (x＞ y≥z)i，而（ y≥z≥x） j≠I
显然，由于全体一致意见，（ y≥z ）必成立。又 {i}
是 x,y的决定性集合，故应有（ x＞ y）。于是，由传递
性，必有（ x＞ z）。再由公理 4,y的插入不应影响 x,z
的排序，故 {i}也是 x,z的决定性集合。类似还可证明，
如果 ω 是异议于 x,z的任一候选人,{i}也是 w,z的决定
性集合，这就是说,评选人 i是选举的独裁者 。
Arrow的公理系统隐含矛盾
例 11 设 I={1,2},A={x,y,z},考察如下的四次选举：
（第一次） x＞ y＞ z （第三次） y＞ z＞ x
x＞ y＞ z z＞ y＞ x
结果应有 x＞ y 合理结果 y=z
（第二次） x＞ z＞ y （第四次） x＞ y＞ z
z＞ x＞ y z＞ x＞ y
合理结果 x=z 结果？？？
)1(2p
)1(1p
)2(1p
)2(2p
)3(1p
)3(2p
)4(1p
)4(2p
由公理 1，第四次的选举应当是 有效 的
由公理 2，必须有 （ x＞ y） (4)
再与第二次选举比较并根据公理 3，则应有 （ x=z） (4)
与第三次比较并根据公理 3，应有 （ y=z） (4)
x＞ y,x=z与 y=z
居然同时成立 ！
改进方案
一个可以考虑的改进方案为要求评选人给出他对每一候
选人优劣程度的评价, 然后按定量方式决定候选人的顺序,
但矛盾仍然不能避免, 总可以构造出类似于 Borda数规则中
例那样的例子来 。
解决这一问题的另一途径是事先适当限制评选人的排序
方式, 使得可能出现的情况数减少, 以便保证一个合理的选
举规则的存在 。
由于本节的主要目的是介绍利用逻辑方法讨论实际问题
的 Arrow不可能性定理, 关于选举问题我们就不再讨论下去
了 。
什么是选举
所谓选举，其实质就是在评选人对候选人先后（优劣）
次序排队的基础上，根据某一事先规定的选举规则决定出候
选人的一个先后次序，即得出选举结果。现用 I={1,2,…,n}
表示评选人集合，用有限集 A={x,y,… }表示候选人集合，
用 >,=,<分别表示优于、等于、劣于，用 (x>y)i表示评选人 i
认为 x优于 y，用 (x>y)表示选举结果为 x优于 y并用 pi表示评选
人 i的排序,p表示选举结果。
A的排序应满足 以下 性质：
(1)择一性 关系式 (x>y),(x=y),(x<y)有且仅有一个成立Ayx ??,
(2)传递性 若 x≥y,y≥z,则必有 x≥zAzyx ??,,
? 简单多数规则
几种选举规则
它规定当且仅当 (x>y)i的评选人超过半数时选举结果才为 (x>y)。
有时要超过 2/3多数等
例 8 设 I={1,2,3},A={x,y,u,v},三位评选人的选票为
p1,x>y>u=v
p2,y>x>u>v
p3,x=u>v>y
根据选举规划, 结果应为
P,x>y>u>v
例 9 设 I={1,2,3},A={x,y,z}
p1,x>y>z
p2,y>z>x
p3,z>x>y
根据规则，自然应有
(x>y),(y>z)和 (z>x)
违反传递性（ 2）
简单多数规则的主要优点
是简单易行，使用方便。
但可惜的是这一规则有时
会违反传递性
? Borda数规则
记 Bi(x)为 p1中劣于 x的候选人数目，记,称 B(x)为 x
的 Borda数,Borda数规则规定 按 Borda数大小排列候选人的优劣次
序，即当 B(x)≥B(y)时有 (x≥y)，两关系式中的等号必须同时成立。
?
?
? n
i
i xBxB
1
)()(
对于例 11.9,计算出 B(x)=B(y)=B(z)=3
故选举结果为 x=y=z
用 Borda数规则得出
的结果更合乎常理
例 10 I={1,2,3,4},A={x,y,z,u,v},选票情况为
p1p2p3,x>y>z>u>v
P4, y>z>u>v>x
计算得 B(x)=12,B(y)=13
故选举结果为 y>x
但有三人认为 x优于 y
用 Borda数规则得出
的结果未必合理
能找到一种在任何情况下都, 公平, 的选举规则吗
什么是, 公平, 的选举规则
“公平, 的选举规则应当满足 以下 公理
公理 1 投票人对候选人排出的所有可能排列都是可以实现的。
公理 2 如果对所有的 i,有 (x≥y)i,则必须有 (x≥y)。
公理 3 如果在两次选举中，对任意 i，由 必可得出,
则由 必可得出 。
)1()( iyx ? )2()( iyx ?
)1()( yx ? )2()( yx ?
公理 4 如果两次选举中，每个投票人对 x,y的排序都未改变，则
对 x,y的排序两次结果也应相同。
公理 5 不存在这样的投票人 i,使得对任意一对候选人 x,y,只要
有 (x≥y)i,，就必有 (x≥y)。
有满足上述公理的选举规则吗
Arrow不可能性定理使上述想法终结
定理 9.1 如果至少有三名候选人，则满足公理 1~公理 5的选举规划
事实上是不可能存在的。
证：
将证明由公理 1~公理 4必可导出存在一个独裁者，从而违反了公理 5
首先引入决定性集合的概念。
称 I的子集 Vxy为候选人 x,y的决定性集合，如果由所有 Vxy中的 I
有 (x≥y) i必可导出 (x≥y) 。
显然决定性集合是必定存在，由公理 2或实际一次选举得到。
找出所有决定性集合中含元素最少的一个，不妨仍记为 Vxy 。
证明 Vxy只能含有一个元素 ——某评选人 i 。
反证 假定 Vxy至少含有两个元素,则 Vxy必可分解为两个非空集合的和
即
与 非空且不相交,且均不可能是任一对候选人的决定性集合
假设
)2()1( xyxyxy VVV ??
)1(xyV )2(xyV
??? xyVI
根据公理 1,以下选举是允许的：
当 时, （ x≥y≥z） i
当 时, （ z≥x≥y） i
当 时, （ y＞ z＞ x） i
其中 z是任一另外的候选人
)1(xyVi?
)2(xyVi?
xyVi?
考察选举结果
(x≥z) 是不可能，否则 是 x,z的决定性集合，故必
有 (z＞ x)。又 Vxy是 x,y的决定性能合，故必有 (x≥y) 。
由传递性 (z＞ x)。得 是 y,z的决定性集合，从而导出矛盾。
以上证明说明 Vxy不能分解,即 Vxy={i},i为某一投票人。
)1(xyV
)2(xyV
进一步说明,对于任意另外的候选人 z,V={i}也是 x,z的决定性集合 。
考虑另一次选举, (x＞ y≥z)i，而（ y≥z≥x） j≠I
显然，由于全体一致意见，（ y≥z ）必成立。又 {i}
是 x,y的决定性集合，故应有（ x＞ y）。于是，由传递
性，必有（ x＞ z）。再由公理 4,y的插入不应影响 x,z
的排序，故 {i}也是 x,z的决定性集合。类似还可证明，
如果 ω 是异议于 x,z的任一候选人,{i}也是 w,z的决定
性集合，这就是说,评选人 i是选举的独裁者 。
Arrow的公理系统隐含矛盾
例 11 设 I={1,2},A={x,y,z},考察如下的四次选举：
（第一次） x＞ y＞ z （第三次） y＞ z＞ x
x＞ y＞ z z＞ y＞ x
结果应有 x＞ y 合理结果 y=z
（第二次） x＞ z＞ y （第四次） x＞ y＞ z
z＞ x＞ y z＞ x＞ y
合理结果 x=z 结果？？？
)1(2p
)1(1p
)2(1p
)2(2p
)3(1p
)3(2p
)4(1p
)4(2p
由公理 1，第四次的选举应当是 有效 的
由公理 2，必须有 （ x＞ y） (4)
再与第二次选举比较并根据公理 3，则应有 （ x=z） (4)
与第三次比较并根据公理 3，应有 （ y=z） (4)
x＞ y,x=z与 y=z
居然同时成立 ！
改进方案
一个可以考虑的改进方案为要求评选人给出他对每一候
选人优劣程度的评价, 然后按定量方式决定候选人的顺序,
但矛盾仍然不能避免, 总可以构造出类似于 Borda数规则中
例那样的例子来 。
解决这一问题的另一途径是事先适当限制评选人的排序
方式, 使得可能出现的情况数减少, 以便保证一个合理的选
举规则的存在 。
由于本节的主要目的是介绍利用逻辑方法讨论实际问题
的 Arrow不可能性定理, 关于选举问题我们就不再讨论下去
了 。
