§9.3公平选举是可能的吗? @ 什么是选举 所谓选举,其实质就是在评选人对候选人先后(优劣) 次序排队的基础上,根据某一事先规定的选举规则决定出候 选人的一个先后次序,即得出选举结果。现用I={1,2,,n}表 示评选人集合,用有限集A={xy}表示候选人集合,用 >,=,y)表示评选人认 为x优于y,用(x>y)表示选举结果为x优于y并用p表示评选 人的排序,p表示选举结果 A的排序应满足以下性质: (1)择一性x,美系式x>y、(x=y)、(x<y)有且仅有一个成立 (2)传递性Wx,y若x2yy2则必有x≥z
§ 9.3 公平选举是可能的吗? 什么是选举 所谓选举，其实质就是在评选人对候选人先后（优劣） 次序排队的基础上，根据某一事先规定的选举规则决定出候 选人的一个先后次序，即得出选举结果。现用I={1,2,…,n}表 示评选人集合，用有限集A={x,y,…}表示候选人集合，用 >,=,y)i表示评选人i认 为x优于y，用(x>y)表示选举结果为x优于y并用pi表示评选 人i的排序，p表示选举结果。 A的排序应满足以下性质： (1)择一性 x, y 关系式 A (x>y)、(x=y)、(x<y)有且仅有一个成立 (2)传递性 x, y, 若 z x≥y, y≥z, A 则必有x≥z
几种选举规则 >简单多数规则 它规定当且仅当(x>y)的评选人超过半数时选举结果才为(x>y) 例8简单多数规则的主要优点 的选票为 是简单易行,使用方便。 但可惜的是这一规则有时 )/3多数等 会违反传递性 根丑 反传递性(2) you 例S设上(1,23,A=(x,; pI: XY>Z p2: y7X 根据规则,自然应有 p3: Xy (x>y,(y>2)和(z>x
➢ 简单多数规则 几种选举规则 它规定当且仅当(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数规则 记B(p中劣于x的候选人数目,记B(x)=∑F称B(x)为x的 borda数,a数规则规定按Bord数大小排列候选人的优劣次序, 即当B(x)有(x2y),两关系式中的等号必须同时成立。 用 Borda数规则得出 x)=B(y=B(2=3 的结果未必合理为x优于y 例10=(1,2,3,4,Azuy,选票情况为 p,P2p3:(x>>7u>v 用 Borda数规则得出 :y>zu>ⅴ>X 的结果更合乎常理 计算得B(x)=12,B(y)=13 故选举结果为yx
➢ Borda数规则 记Bi (x)为p1中劣于x的候选人数目，记 ，称B(x)为x的 Borda数，Borda数规则规定按Borda数大小排列候选人的优劣次序， 即当B(x)≥B(y)时有(x≥y)，两关系式中的等号必须同时成立。 = = n i i B x B x 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}，选票情况为 p1 p2 p3 : x>y>z>u>v P4 : y>z>u>v>x 计算得 B(x)=12，B(y)=13 故选举结果为 y>x 但有三人认为x优于y 用Borda数规则得出 的结果未必合理
能找到一种在任何情况下都“公平”的选举规则吗 什么是“公平”的选举规则 “公平”的选举规则应当满足以下公理 公理1投票人对候选人排出的所有可能排列都是可以实现的 公理2如果对所有的,有(x2),则必须有(y) 公理3如果在两次选举中,对任意,由(x≥必对得出(x则申 必可得出y) x≥ 公理4如果两次选举中,每个投票人对x、y的排序都未改变,则 对x、y的排序两次结果也应相同
能找到一种在任何情况下都“公平”的选举规则吗 什么是“公平”的选举规则 “公平”的选举规则应当满足以下公理 公理1 投票人对候选人排出的所有可能排列都是可以实现的。 公理2 如果对所有的i，有(x≥y)i，则必须有(x≥y)。 公理3 如果在两次选举中，对任意i，由 必可得出 ，则由 必可得出 。 (1) ( ) i x y (2) ( ) i x y (1) (x y) (2) (x y) 公理4 如果两次选举中，每个投票人对x、y的排序都未改变，则 对x、y的排序两次结果也应相同
公理5 不存在这样的投票人i,使得对任意一对候选人x、y,只要 有(xy),就必有(xy) 有满足上述公理的选举规则吗 Arrow不可能性定理使上述想法终结 定理91 如果至少有三名候选人,则满足公理1公理5的选举规划 事实上是不可能存在的。 将证明由公理1公理4必可导出存在一个独裁者,从而违反了公理5 首先引入决定性集合的概念。 称的子集V为候选人X、y的决定性集合,如果由所有Ⅴ中的 有(X2y)可导出(Xy) 显然决定性集合是必定存在,由公理2际一次选举得到。 找出所有决定性集合中含元素最少的一个,不妨仍记为vy
公理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
证明V只能含有一个元素某评选人 反证假定V至少含有两个元素,则必可分解为两个非空集合的和 即 1) 与非空且不相交,且均不可能是任一对候选人的决定性集合 假设-V≠p 根据公理1,以下选举是允许的: 当当当 l∈ 时,(xy≥z) ∈ (≥x≥y) ig时,(y>z 其中z是任一另外的候选人 考察选举结果 (x≥z)是不可能,否则是、动的决定性集合,故必 有(z>x)。又V是X、y的决定性能合,故必有(X2y) 由传递性(z>x)。得V是y、z的决定性集合,从而导出矛盾。 以上证明说明V不能分解,即Vx={,沩某一投票人
证明 Vxy只能含有一个元素——某评选人i 。 反证 假定Vxy至少含有两个元素，则Vxy必可分解为两个非空集合的和 即 与 非空且不相交 ，且均不可能是任一对候选人的决定性集合 假设 (1) (2) Vxy =Vxy Vxy (1) Vxy (2) Vxy − Vxy I 根据公理1，以下选举是允许的： 当 时， （x≥y≥z）i 当 时， （z≥x≥y）i 当 时， （y＞z＞x）i 其中z是任一另外的候选人 (1) Vxy i (2) Vxy i Vxy i 考察选举结果 (x≥z)是不可能，否则 是x、z的决定性集合，故必 有(z＞x)。又Vxy是x、y的决定性能合，故必有(x≥y)。 由传递性(z＞x)。得 是y、z的决定性集合，从而导出矛盾。 以上证明说明Vxy不能分解，即Vxy={i}，i为某一投票人。 (1) Vxy (2) Vxy
进一步说明:对任意另外的候选人z,V={也是x、-的决定性集合。 考虑另一次选举:(x>≌≥2),而(y≥Ex) 显然,由于全体一致意见,(y≥z)必成立。又{是x、 y的决定性集合,故应有(x>y)。于是,由传递性,必 有(X>z)。再由公理4,y的插入不应影响X、z的排序, 故{也是x、z的决定性集合。类似还可证明,如果u是 异议于x、z的任一候选人,你}也是W、z的决定性集合, 这就是说,评选人i选举的独裁者。 Arrow的公理系统隐含矛盾
进一步说明：对于任意另外的候选人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设={1,2},A={x,y,,考察如下的四次选举: (第一次)Px>y>z(第三次)y>z>x x>y,X=z与y=z y=z 居然同时成立! 四次) Riy>z z>xry z>X>y p 合理线果x=z 结果??? 由公理1,第四次的选举应当是有效的 由公理2,必须有(x>y) 与第二次选举比较并根据公理3,则应有(X=z) 笔三次比较并根据公理3,应有(y =z)(4)
例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) 2 p (1) 1 p (2) p1 (2) 2 p (3) 1 p (3) 2 p (4) 1 p (4) 2 p 由公理1，第四次的选举应当是有效的 由公理2，必须有（x＞y）(4) 再与第二次选举比较并根据公理3，则应有（x=z）(4) 与第三次比较并根据公理3，应有（y=z）(4) x＞y，x=z与y=z 居然同时成立！
改进方案 个可以考虑的改进方案为要求评选人给出他对每一候 选人优劣程度的评价,然后按定量方式决定候选人的顺序 但矛盾仍然不能避免,总可以构造出类似于 Borda数规则中 例那样的例子来 解决这一问题的另一途径是事先适当限制评选人的排序方 式,使得可能出现的情况数减少,以便保证一个合理的选举 规则的存在 由于本节的主要目的是介绍利用逻辑方法讨论实际问题的 Arrow不可能性定理,关于选举问题我们就不再讨论下去了
改进方案 一个可以考虑的改进方案为要求评选人给出他对每一候 选人优劣程度的评价，然后按定量方式决定候选人的顺序， 但矛盾仍然不能避免，总可以构造出类似于Borda数规则中 例那样的例子来。 解决这一问题的另一途径是事先适当限制评选人的排序方 式，使得可能出现的情况数减少，以便保证一个合理的选举 规则的存在。 由于本节的主要目的是介绍利用逻辑方法讨论实际问题的 Arrow不可能性定理，关于选举问题我们就不再讨论下去了