§9.3公平选举是可能的吗? @ 什么是选举 所谓选举,其实质就是在评选人对候选人先后(优劣) 次序排队的基础上,根据某一事先规定的选举规则决定出候 选人的一个先后次序,即得出选举结果。现用I={1,2,,n}表 示评选人集合,用有限集A={xy}表示候选人集合,用 >,=,<分别表示优于、等于、劣于,用(x>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,…}表示候选人集合，用 >,=,<分别表示优于、等于、劣于，用(x>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