9.3公平选觉是可能的吗？.ppt

9.3公平选举是可能的吗,什么是选举,所谓选举，其实质就是在评选人对候选人先后（优劣）次序排队的基础上，根据某一事先规定的选举规则决定出候选人的一个先后次序，即得出选举结果。现用I{1,2,,n}表示评选人集合，用有限集A{x,y,}表示候选人集合，用,,yi表示评选人i认为x优于y，用xy表示选举结果为x优于y并用pi表示评选人i的排序，p表示选举结果。,A的排序应满足以下性质,简单多数规则,几种选举规则,它规定当且仅当xyi的评选人超过半数时选举结果才为xy。,有时要超过2/3多数等,根据选举规划，结果应为Pxyuv,根据规则，自然应有xy,yz和zx,,违反传递性（2）,简单多数规则的主要优点是简单易行，使用方便。但可惜的是这一规则有时会违反传递性,Borda数规则,记Bix为p1中劣于x的候选人数目，记，称Bx为x的Borda数，Borda数规则规定按Borda数大小排列候选人的优劣次序，即当Bx≥By时有x≥y，两关系式中的等号必须同时成立。,对于例11.9，计算出BxByBz3故选举结果为xyz,用Borda数规则得出的结果更合乎常理,例10I{1,2,3,4},A{x,y,z,u,v}，选票情况为p1p2p3xyzuvP4yzuvx,计算得Bx12，By13故选举结果为yx,,但有三人认为x优于y,用Borda数规则得出的结果未必合理,能找到一种在任何情况下都“公平”的选举规则吗,什么是“公平”的选举规则,“公平”的选举规则应当满足以下公理,公理1,投票人对候选人排出的所有可能排列都是可以实现的。,公理2,如果对所有的i，有x≥yi，则必须有x≥y。,公理3,如果在两次选举中，对任意i，由必可得出，则由必可得出。,公理4,如果两次选举中，每个投票人对x、y的排序都未改变，则对x、y的排序两次结果也应相同。,公理5,不存在这样的投票人i，使得对任意一对候选人x、y，只要有x≥yi,，就必有x≥y。,有满足上述公理的选举规则吗,Arrow不可能性定理使上述想法终结,定理9.1,如果至少有三名候选人，则满足公理1公理5的选举规划事实上是不可能存在的。,证,将证明由公理1公理4必可导出存在一个独裁者，从而违反了公理5,首先引入决定性集合的概念。称I的子集Vxy为候选人x、y的决定性集合，如果由所有Vxy中的I有x≥yi必可导出x≥y。显然决定性集合是必定存在，由公理2或实际一次选举得到。找出所有决定性集合中含元素最少的一个，不妨仍记为Vxy。,,,,证明Vxy只能含有一个元素某评选人i。反证假定Vxy至少含有两个元素，则Vxy必可分解为两个非空集合的和即与非空且不相交，且均不可能是任一对候选人的决定性集合假设,根据公理1，以下选举是允许的当时，（x≥y≥z）i当时，（z≥x≥y）i当时，（y＞z＞x）i其中z是任一另外的候选人,,考察选举结果x≥z是不可能，否则是x、z的决定性集合，故必有z＞x。又Vxy是x、y的决定性能合，故必有x≥y。由传递性z＞x。得是y、z的决定性集合，从而导出矛盾。以上证明说明Vxy不能分解，即Vxy{i}，i为某一投票人。,考虑另一次选举x＞y≥zi，而（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＞xx＞y＞zz＞y＞x结果应有x＞y合理结果yz（第二次）x＞z＞y（第四次）x＞y＞zz＞x＞yz＞x＞y合理结果xz结果,由公理1，第四次的选举应当是有效的由公理2，必须有（x＞y）4再与第二次选举比较并根据公理3，则应有（xz）4与第三次比较并根据公理3，应有（yz）4,x＞y，xz与yz居然同时成立,