文档介绍：§ 公平选举是可能的吗?
什么是选举
所谓选举,其实质就是在评选人对候选人先后(优劣)次序排队的基础上,根据某一事先规定的选举规则决定出候选人的一个先后次序,即得出选举结果。现用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)有且仅有一个成立
(2)传递性若x≥y, y≥z,则必有x≥z
简单多数规则
几种选举规则
它规定当且仅当(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),两关系式中的等号必须同时成立。
, 计算出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,由必可得出,则由必可得出。
公理4
如果两次选举中,每个投票人对x、y的排序都未改变,则对x、y的排序两次结果也应相同。
公理5
不存在这样的投票人i,使得对任意一对候选人x、y,只要
有(x≥y)i,,就必有(x≥y)。
有满足上述公理的选举规则吗
Arrow不可能性定理使上述想法终结

如果至少有三名候选人,则满足公理1~公理5的选举规划
事实上是不可能存在的。
证:
将证明由公理1~公理4必可导出存在一个独裁者,从而违反了公理5
首先引入决定性集合的概念。
称I的子集Vxy为候选人x、y的决定性集合,如果由所有Vxy中的I
有(x≥y)i必可导出(x≥y)。
显然决定性集合是必定存在,由公理2或实际一次选举得到。
找出所有决定性集合中含元