（管理科学与工程专业论文）对一种投票方法的研究.pdf

中圈科学技术大学研究生学位论文 对一种投票方法的研究 摘要：本篇文章首先回顾了社会福利经济学和社会选择理论发展的历史，简要介绍了这个 研究方向上，一些具有代表性的经济学家的理论贡献。文章的第二部分介绍了一些常见的社 会选择函数及其性质。第三部分讨论了在由b o r d a 规则延伸出的整数计分投票方法中，投票 结果使备选方案集产生全排序( 任意两个备选方案的总分值不同) 的概率p 的问题，并从 这个意义上指出麻如何设计雨j 调整孳；! 数计分投票规则。文章给出了在一定假设条件下计算p 值的公式，并通过分析运行计算机程序得到的相关数据，讨论了整数计分投票问题的三个主 要变量对p 值的影响，最后得到一些结论。 关键词：社会福利经济学；社会选择理论；整数计分投票规则；全排序概率 中国科学技术人学研究生学位论文 r e s e a r c ho nas o r to fv o t i n gr u l e a b s t r a c t ：i nt h ef i r s tp a r to ft h i sp a p e r , t h eh i s t o r yo ft h ed e v e l o p m e n to fs o c i a lw e l f a r e e c o n o m i c st h e o r ya n ds o c i a lc h o i c et h e o r yi sr e v i e w e d i nt h es e c o n dp a r tw ei n t r o d u c es o m e s o c i a lc h o i c ef u n c t i o n s i nt h et h i r dp a r tw ef o c u so nt h ep m b 曲n 时po ff u l lr a n k i n g ( a n y2 a l t e r n a t i v e sd o n tr e c e i v eas a m et o t a ls c o r e ) w i t hi n t e g e r - s c o r i n gv o t i n gr u l e ，w h i c hi sd e r i v e d f r o mb o r d ac o u n t , a n df r o mt h i sp o i n to fv i e ww ei n d i c a t eh o wa ni n t e g e r - s c o r i n gv o t i n gr u l e s h o u l d b ed e s i g n e da n da d j u s t e d w eb r i n gf o r t hf o r m u l a st h a tc o m p u t ep u n d e rc e r t a i n a s s u m p t i o t i s c o m p u t e rp r o g r a m sa r ed e s i g n e da n du s e dt oc o m p u t et h ev a l u e so f ew i t ht h ed a t a o b t a i n e d ，w ed i s c u s s e dh o wt h et h r o ev a r i a n t so fa ni n t e g e r - s c o r i n gv o t i n gr u l ei n f l u e n c et h e v a l u e so f p s o m ec o n c l u s i o n sa r ed r a w n k e yw o r d s ：s o c i a lw e l f a r ee c o n o m i c ；s o c i a lc h o i c et h e o r y ；i n t e g e r - s c o r i n gv o t i n gr u l e ； p r o b a b i l i t yo f f u l lr a n k i n g 2 中国科学技术大学研究生学位论文 前言 所谓社会选择就是将社会成员的偏好集结社会群( 社会) 的偏好。从形式上看社会选择 是典型的群决策问题，但从更深的层次分析，社会选择理论研究的是“个人价值与社会选择 之间的冲突与一致性的条件”。类似于实证经济学和规范经济学的分类，社会选择理论可以 分为两大部分，实证社会选择和规范社会选择。前者研究各种投票机制和选举机制，后者则 主要讨论各种规则的前提假设的合理性。 西方学者从近代开始对投票选举方法进行系统化研究，其中，法国学者b o r d a ，对于简 单多数投票法的缺陷，提出了自己的投票方法，即所谓的b o r d a 法。著名数学家l a p l a c e 应 用概率的方法对偏好序的赋值问题进行了系统研究，并提出了等同丁b o r d a 法的，按各方案 所赋总值的入小对方案进行排序的投票方法。在一定的条件下，研究一类投票问题出现某种 结果的概率是研究投票问题性质的一个重要方面。如基于c o n d o r c e t 准则，考察当存在 c o n d o r c e t 胜者时，某种投票规则选出c o n d o r c e t 胜者的概率，定义这个概率为c o n d o r c e t 效 率，并以此作为评价投票规则优劣的标准。 在实际生活中，我们有时会用到另一种由b o r d a 法延伸出的投票方法，即制定最高分和 最低分的标准，要求投票人用0 和d ( d 是整数，通常大于方案个数) 之间的整数给方案打 分，再以方案的总得分对方案排序。事实上，可以把它看成一类整数计分投票方法，b o r d a 法是其中的一个特例。本文从概率的角度讨论了这种投票方法的特定性质，即投票结果产生 全排序( 任意两个备选方案总得分不同) 的概率p 的相关问题。 4 中圃科学技术人学研究生学位论文 第1 章社会选择理论发展的历史 1 1 现代以前对投票选举方法的研究 中世纪是迄今已知的最早开始对投票方法进行研究的时期，其代表人物有r o m a n l u l l 和n u o l 笛c u s a n u s 。l u l l 在自己的短文中提出了一种形式上完全等价于当今各国议会便决中 常用的“修正案表决程序”的选举方法。这种方法本质上可以说是c o n d o r c 2 t 两两比较法。 c u a s a n u s 对投票方法的贡献在于他也提出了一种形式上是两两比较，本质上为b o r d a 洼的选 举方法1 4 2 j 。 从近代开始，西方学者开始对投系统票选举方法进行系统的研究，其代表人物有以下几 位。 j e a n c h a r l e sd eb o r d a ，法国国家科学院院十。被认为是第一位对选举的数学理论做出杰 出贡献的思想家。他在1 7 8 1 年发表的一篇文章中通过一个简单的例子表现出简单多数法的 缺陷，即根据简单多数法得到的获胜者在与其他候选人的两两比较中，有可能不能战胜其他 候选人【，2 0 , 2 2 1 。对于这种不足，b o r d a 给出了两种修正方法。这两种方法都等同于现在所称 的b o r d a 法。该方法曾一度被用于法国皇家科学院新院士的增选选举中 m a r q u i sd ec o n d o r c c t ，法国国家科学院院士c o n d o r c c t 对投票选举理论的主要贡献是 他发现了对投票理论研究产生深远影响的“投票悖论”，即以多数法两两比较的结果没有传 递性的性质；提出了一种判断选举方法优劣的准则一一c o n d o r c e t 准则，即如果存在 c o n d o r c e t 胜者( 两两比较中战胜所有其它候选方案的某方案) 时，投票规则应该将c o n d o r c e t 胜者选出，和当存在c o n d o r c c t 负者( 两两比较中负于所有其它候选方案的某方案) 时该 方案不席被选出1 5 ”? 2 】；此外，首次将概率引入投票理论的研究中嘲。 m a r q u i sd el a p l a c e ，著名数学家。l a p l a c e 应用概率的方法对偏好序的赋值问题进行了 系统研究，提出了偏好集结中偏好序的赋值方式：在此基础上，提出了按各方案所赋总值的 大小对方案进行排序的方法，事实上，该方法等同于b o r d a 法：l a p l a c e 还发现，在该方法 的应用中，投票人很容易通过谎报偏好对选举结果进行攘缴 锄。 除了上述学者外，c l d o d g s o n ，e j ，n a n s o n f r a n c i sg a l t o n 等对投票选举理论的研究 也作出了很大的贡献【5 , 2 2 1 。 1 2 b e r g s o n ( 1 9 3 8 ) 和s a m u e l s o n ( 1 9 4 7 ) 提出的社会福利函数 中国科学技术大学研究生学位论文 在福利经济学中，经济学家所关注的是一个社会或集体的选择行为。如果社会选择依赖 于其成员的偏好或者意向，那么我们就称社会选择满足“个人主义”或者“非强制性”，福 利经济学士耍研究满足“竹强制性”的事十会选择行为。与个人决策中的备选方案不同。一个 公共选项往往与多个社会成员的福利状况或者效n j 水平有关，因此在进行社会选择时。如何 权衡不同社会成员的福利得失就成为一个无法避免的问题。这个问题可以这样描述：如果给 定每个成员的理性偏好，是否存在和存在什么样的依赖于个人偏好的社会福利标准，可以“公 正”地指导社会选择。这一问题对福利经济学的整个研究框架都具有基本性的意义，因此把 它称为福利经济学的基本问题。 为了解决这一问题，首先必须在理论上明确社会福利标准的严格定义。b e r g s o n “1 和 s a m u e l s o n ”完成了这一工作( 在涉及社会福利函数的信息基础时，s a m u e l s o n 不同于b e r g s o n 之处在于，他明确强调了个人效用是序数性质的) ；他们所提出的社会福利函数概念第一次 对丰十会丰l ；利标准作出了精确的描述。根据这一定义，指导社会选择的福利标准可以用一个以 所有社会成员的效州水平为臼变颦的( 序数性质的) 实值函数来表示，而这一函数即社会福 利函数。借助于这一定义，福利经济学的基本问题可以清楚的表述为：1 ) 社会福利函数是 否存在，2 ) 社会福利函数的具体形式是什么 以b e r g s o n 和s a m u e l s o n 为代表的新福利经济学摒弃了传统个人分析中的基数效用论，而 采用序数效用论，由此构成了社会福利判断的新框架通过对个人偏好序的集结得到社会 偏好序。这种框架结构与投票理论所研究的模型结构是一致的。从此，社会选择理论的两大 基本来源传统的投票理论和新福利分析由于问题的基本模型结构的一致而结合，形 成了现代社会选择理论的雏形【1 , 8 , 2 2 3 3 阗。 1 3 现代对社会选择理论的研究 1 3 id b l a c k 提出的委员会决策问题 b l a c k 在其1 9 5 8 年发表的著作t h e t h e o r y o f c o m m i t t e e s a n d e l e c t i o n s 中，首次提出了委 员会决策( c o m m i t t e ed e c i s i o n ) 问题，并对委员会的投票、选举问题进行了深入、系统和全 面的研究。构造了投票选举理论研究的基本理论框架p 茁娜1 。 1 3 2 a r r o w 不可能定理 现代意义的社会选择理论形成的标志是2 0 世纪5 0 年代a r r o w 不可能定理的提出 i 五7 , 1 1 , 1 4 ，2 0 j 2 , 3 6 。a r r o w 开创性地把起源于1 8 世纪的投票选举理论引入到福利经济学基本问题 的研究中来，成功地建立起一个关于社会福利标准的存在性的抽象模型。在a r r o w 之前， 6 中国科学技术人学研究生学位论文 对投票选举机制的多数研究成果是令人失望的。研究者既无法穷举出所有的投票方法做出不 可能性的判断，也不能找到一种令人满意的具体的选择机制并得到可能性的结论。对社会选 抒存在性问题的研究陷入既不能证实，也不能证伪的局面。这一僵局最终被a r r o w 不可能 定理打破。 a r r o w 的研究从对个人选票信息的抽象认识开始。他认为，每张选票所能提供的信息最 多可以用一个关于所有备选方案的完整捧序表示；不同的选票之间是相互独立的。a r r o w 的 社会福利函数的定义域是全部选举人所有可能的个人偏好序的组合的集合，而值域是所有可 能的偏好序的集合。接下来，a r r o w 认为，一个可以接受的社会福利函数并不是随意的，它 应该满足以下的性质， 1 ) 无限制性定义域社会选择函数必须适用丁所有可能的个人偏好端面，简称( u ) ： 2 ) 社会偏好与个人偏好之间正的联系。假设对于一个特定的偏好端面，社会认为z 优 于如果对偏好断面作这样的修改，每个人都或者提高，或者保持x 对其它方案的偏好关 系，而不改变其它任何方案之间的偏好关系那么，社会仍然认为x 优于y ； 3 ) 朴会桶利函数必须满足某种p a r e t o 标准。a r r o w 川的是一种较弱的p a r e t o 标准，既 当社会所有成员认为x 严格优y - y 时，社会必须认为x 严格优于 这一性质被称为弱p a r e t o 原则，简称( 岍) ； 4 ) 无关方案的独立性。社会对于任意两个备选方案的偏好关系，只与社会成员对这两 个备选方案的偏好芙系有关，简称( i ) ； 5 ) 1 独裁性。不存在一个社会成员。对丁任何一对方案x 和y ，当他认为x 优于一社 会就认为x 优于y 。无论其他成员对这两个方案的偏好如何，简称( n d ) 。 以上的性质并不是严格的约束，是人们通常都会接受的，然而a r r o w 证明了这样的关 丁礼会选择函数存在性的结论：如果备选方案的个数人丁等丁3 ，那么不存在一个社会选择 函数同时满足上述的5 个条什。这就是a r r o w 不可能定理。 a r r o w 建立的理论框架首先实现了群体决策理论和福利经济学的第一次结合，使得群体 决策的抽象分析框架成为研究福利经济学的标准框架；其次，它是对以往所有社会选择理论 的一次高度总结和重要发展，一定程度上终结了人们关丁群体决策机制的诸多猜测；第三， 它成功地描述了社会福利函数的决定机制，使这一抽象的概念具备了丰富的现实内容；最后。 它实际上为人们提供了一条最终找到一个具体的社会福利函数的可能途径f 4 3 1 。 1 3 3 以a r r o w 的理论框架为基础对福利经济学基本问题的深入研究 a r r o w 不可能定理的结论虽然是悲观的，但是为现代社会选择理论的发展奠定了重要的 中国科学技术大学研究生学位论文 基础。在a r r o w 的基础上，以s e n 为代表的经济学家对福利经济学的基本问题进行了深入 的探索，这一过程持续到上个世纪8 0 年代初，大致完成了对基本问题的解答，并提出了一 个比较成熟的解决方案。这探索过程的主要内容，是对a r r o w 不可能理论框架的二个问 题的解答i 。 第一个问题，a r r o w 不可能定理否认的是适_ h j 丁所有个人偏好组台的社会选择机制的存 在性。而福利经济学的基本问题是一个特定的个人组合集结成为社会偏好的可能性。这两个 问题并不是等价的。如果个人的偏好组合发生了变化，是否可以使用另外一个个人偏好组合 的集结机制? 如果是这样，就从某种程度上避开了a r r o w 不可能定理。但是这个可能性被 k e m p 和n g1 2 4 j 和p a r k s 删的研究推翻。他们证明，即使是为一个给定的个人偏好组合设计 的集结机制，也不能同时满足类似与a r r o w 不可能定理中所要求的温和的条件。这一结果 被称为k e m p - n g - p a r k s 不可能定理，它表明，通过否认a r r o w 不可能定理和福利经济学基 本问题的关系来摆脱个人偏好集结机制的不可能性是不可能的。 第二个问题，一个a r r o w 理论框架中的社会偏好集结机制是否隐含着一个 b e r g s o n s a m u e l s o n 式的社会福利函数? 为了解决福利经济学的基本问题，必须保证从社会 偏好集结机制( 也就是a r r o w 的社会福利函数) - - 9 得到一个b e r g s o n - s a m u e l s o n 式的社会 福利函数。为此，需要社会偏好集结机制满足什么条件? d a s p r e m o n t 和g e v e r s l 证明，只 要社会偏好集结机制满足( u ) 、( 1 ) 和( s p ) ( 强p a r c = t o 标准) 性质，它就是中立的，即排 除了非选票信息影响集结结果的可能，而从一个中立的社会偏好集结机制可以得到一个 b e r g s o n - s a m u e l s o n 式的社会福利函数。 第三个问题，a r r o w 不可能定理成立的本质原因是什么，如何排除这些因素得到社会福 利函数的存在性结论。以s e n 为代表的经济学家研究了a r r o w 不可能定理的约束条件。在 排除了( u ) 和( w p ) 这两个无法挑剔的假设后，s e n l ”l 把a r r o w 不可能定理的三个信息约 束作为考察对象：( 1 ) 选票信息_ j 偏好序的形式表示；( 2 ) 人际间效用的不可比性；( 3 ) 无 笑方案的独立性。对丁约束( 1 ) ，s e n 证明了它并非a r r o w 不可能定理成立的必要条件m 1 ， 即使采用基数效用函数从而考虑了偏好强度问题，维持其他条件不变，a r r o w 不可能定理依 然成立。对于约束( 2 ) ，h a r s a n y i i n 】和n g 嘲证明了它是不可能定理的一个必要条件对于 约束( 3 ) ，n a s h l 2 6 , 2 1 发展的合作博弈模型证明了它也是不可能定理的必要条件之一。 既然a n d w 不可能定理的本质可以用过于严格的信息约束来概括，那么，通过放松这 些约束条件，在新的条件下考察社会福利函数的存在性问题，就是下一步的研究思路。经过 对上述约束条件现实依据的分析，s e n 决定以第一和第二个信息约束作为突破口p 6 i 。这意味 8 中国科学技术大学研究生学位论文 着引入偏好强度的信息和人际间效用的可比性，囡此在理论上需要一个更具现实性的社会选 择理论，以容纳多样化的信息基础；这个框架是a r r o w 原有的理论的一个特例。s e n 为建立 这一新框架做出重要贡献。他以效用函数代替偏好序来描述个人的投票信息，他还开创性地 给出了人际效用比较的严格定义，通过考察不同人际效用比较的假设对社会偏好集结机制存 在可能性的影响发展了a r r o w 的理论。s e n 成功地论证了一些特殊的人际比较情况下社会偏 好集结机制和社会福利函数的存在性l 。此后，在s e n 建立起的新的社会选择理论框架之 上，随着多样化的信息基础，即不同人际效用比较假设的引入，使覆盖的社会选择过程更加 广泛，福利经济学家成功地论证了一系列社会偏好集结机制和社会福利函数的存在性 p 0 3 8 3 1 , 3 2 , 3 7 1 。这些理论成果很好的回答了a r r o w 不可能定理理论框架的第三个问题。 1 3 4g i b b a r d s a t t e r t h w a i t e 防策略投票不可能定理 目前社会选择理论的主要研究内容，除了关于社会选择机制存在性的a r r o w 不可能定 理外，还有g i b b a r d s a t t e r t h w a i t e 防策略投票不可能定理( g i b b a r d - s a t t e r t h w a i t e s t r a t e g y p r o o f n e s si m p o s s i b i l i t yt h e o r e m ) 和s e n 个人主权不可能定理( s e nl i b e r t a r i a n i m p o s s i b i l i t yt h e o r e m ) 人们很早就注意到投票选举过程中“策略行为”的存在。投票选举理论的奠基人之一 c l d o d g s o n ( l e w i sc r r o l l ) 经过大量的对比研究认为：投票程序的“可操纵性”是“普遍 存在”的p 2 2 1 。m d u m m e t t l l 2 和r f a r q u h a r s o n l l 4 ) 通过对投票稗序的“稳定性”( s t a b i l i t y ) 即 防操纵性的研究，大胆地猜想：“在一定条件下，任何投票选择程序都是不稳定的，即可操 纵的。”在2 0 世纪7 0 年代中后期，g i b b a r d t l 7 l i f es a r e r t h w a i t e 3 4 】提出防策略不可能定理，证 明满足以下条件的社会选择函数是不存在的， 1 ) 约束域条件。备选方案的个数和投票人数火丁：等于3 ；对任意的偏好序组台，社会 选择函数值非空： 2 ) 单值性。对于任意给定的偏好组合，社会选择函数的值是唯一的即社会选择函数 的结果只有一个； 3 ) o i b b a r d s a t t e r t h w a i t e 防策略条f 1 ：。没有圭l 票人可以通过改变自己的偏好，使得对于 这个投票人来说，改变后社会选择的结果优丁- 原来的结果； 4 ) 值域中的元素个数大于等于3 ； 5 ) 非独裁性条件。 防策略不可能定理的提出经济领域的资源合理配置理论的存在性和合理性提山了巨人 的挑战。类似对a r r o w 不可能定理的研究学者f f j 通过对约束条件的修改和定义新的防策 9 中国科学技术人学研究生学位论义 略条件，得到一些新的防操纵不可能定理和一些特定条件下的防操纵性可能性。在委员会决 策理论的实际应用中，由于无法设计出防操纵性的社会选择规则，因此采用一些具有“计算 复杂性”( c o m p u t a t i o nc o m p l e x i t y ) 性质的投票规则使得实际上对投票程序进行操纵是不可 能的嘲，但是这种做法往往会牺牲程序的其他性质和增加程序设计的难度。 1 3 5s e n 个人主权不可能定理 如何处理个人主权和集体选择间的关系并使它们保持一致，也是社会选择理论研究中 经常引起人 j 注意的问题。按照一般的观念，个人权利往往被认为是不可侵犯的。但当进行 社会选择时，个人的权利就有可能与集体选择发生矛盾。s e n 个人主权不可能定理证明了这 一命题 3 6 , 3 9 , 4 0 l 。它的内容如是，不存在同时满足以下i 条件的社会选择函数， 1 ) 无约束域条件； 2 ) p a r e t o 准则； 3 ) s e n 个人主权条件，社会中的所有个体有权利选择自己所处的状态。 同样类似与对a r r o w 不可能定理的研究，既然p a r e t 0 准则和个人主权之间存在矛盾， 解决问题的方法有两种，即放弃p a r c t o 准则或者限制个人主权。两种方法都有价值观和现 实依据的支持。 1 4 社会选择理论的发展方向 从a n d w 不可能定理以来社会选择理论的发展历史来看，经济学家们的研究思路可以 这样概括，从一些不可能定理山发，即以一定的现实情况为依据。通过改变或放松不可能定 理的“过于严格”的约束条件，来得到新的不可能定理和存在性定理。这一过程，实际上 是对a n o w 抽象化的理论框架的不断具体化和现实化的过程，以使新的理论框架可以解释 更多的社会选择现象，具有更广泛的现实基础。 最只有典型性的例子就是1 3 3 中提到的对入际间效用不可比性约束条件的研究。原有 的理论框架是基于序数效用雨1 人际效用不可测性的，这就排斥了许多可以用以集结的偏好信 息，导致了不可能性结论。然而对于实际的社会选择问题，人们所面临的偏好信息并不是绝 对的“不可测”和“不可比”。因此，实际的社会选择问题应是基于所谓“相容信息”的偏 好集结问题。“相容信息”不是指偏好的完全可测和完全可比，而是在社会选择过程中适当 地引入一些有助于偏好集结的信息【8 , 1 6 , 1 q ”j “。此外，除了社会选择过程中的功利主义原则， 还可以引入其他一些道德准则；这方面的研究表明道德准则的适当引入，可以增多个体偏 好的显示方式，在不改变效用的可测性和可比性的前提f ，丰富用以集结的偏好信息【3 堋】。 1 0 中国科学技术大学研究生学位论文 目前，基于相容信息的社会选择问题已成为社会选择理论研究的热点。这个方向上的 研究，突破了传统研究方法的局限，有可能从根本上克服现有理论研究中的不足和困难，从 而推动社会选择理论的发展”。 中国科学技术大学研究生学位论文 第2 章常用社会选择函数及其性质 2 1 一些定义 讨论委员会( 或集体、社会) n = 1 , 2 ，3 ，r l ( n 3 ) 对备选方案( 或候选人) 集a ； ( q ，如，( m 2 2 ) 的选择问题用一和，表示群中成员i 的偏好，g 和一g 表示 根据某种规则集结而成的群的偏好：n ( x y ) 表示群中认为方案x 优于方案y 的成员数， 即n ( j y ) = l i l j 一只i e n l 。给定的方案集a 上的社会选择函数记为c ( a ) 。 定义l ：简单多数规则( s h n p l em a j o r i t yv o t i n g ，简称s m v ) v x y a ， ( 1 ) 若n ( 工 y ) a t ( j ， x ) ，则x - c y ： ( 2 ) 若n ( x y ) = n ( j ，一x ) ，则z g y 。 定义2 ：c o n d o r c e t 集 设“ l 产( r 1 ，r 2 ，碥) lv f n r ，w ( x ) 记 c o n ( a ) = x e a iv y e a ，x j ， 称g m ( a ) 为给定偏好面“下的c o n d o r c e t 集。 定义3 ；c o n d o r c e t 候选方案 设x e a ，若x c o n ( a ) ，则称x 为备选方案集a 中的c o n d o r c e t 候选方案。 定义4 ：c o n d o r c e t 原则 若方案集中存在c o n d o r c e t 候选方案，则c o n d o r c e t 候选方案应该当选( 获胜) 。显然， c o n d o r c e t 原则是合理社会选择规则必须满足的基本条件。 定义5 ：p a r e t o 准则p 设x , y a ，在给定偏好断面下，v i e n ，若x p , y ，则，毛c ( a ) 。 定义6 ：无关方案独立性条件i 设x ，y a ， r ，) ， r ： 为两个给定的偏好断面，v i e n ，r 。i ”= r ；t 圳，有 ( i ) 若x ，_ y c ( r 。 ，a ) ，则x ，y e c ( r ： ，a ) ； ( 2 ) 若工c ( r ， ，a ) 且) ，毛c ( r ，a ) ，则工c ( ( r ： ，a ) 且y 毛c ( r ：) ，a ) ； ( 3 ) 若) ，c ( ( r ， ，a ) 且x g c ( r ，) ，a ) ，则y c ( r ：) ，a ) 且x 毛c ( r ： ，a ) 。 1 2 中国科学技术人学研究生学位论文 定义7 ：非独裁性条件d l i e n ，v u e u h q j v y e a x ，若j r ) ，则扛 = c ( a ) 。 2 2c o n d o r c e t 函数 c o n d o r c e t 函数是一种常用的社会选择函数。由m a r q u i sd ec o n d o r c e t 最早提出。 定义8 ：c o n d o r e e t 值 设“ “= ( r l ，r 2 ，r 。) lv i e n ，r ，w ( x ) ，x e a ，记 工2 ，m 。m i i j l n ( 。一力 则称馋) 为给定偏好端面“下的方案z 的c o n d o r c e t 值。 方案x 的c o n d o r c e t 值就是方案x 与其他方案的两两比较中，得票最少的那一次所的票 数。 定义9 ：c o n d o r e e t 函数 设口f “= ( r i ，r 2 ，r n ) fv f n ，w ( x ) ，记 c “a ) = x l 五( 砷2 五t y ) ，v y a w u 称c “a ) 为给定偏好断面t l 。卜的c o n d o r c e t 函数。 撤据定义可知，c o n d o r c e t 函数实际上就是c o n d o r c e t 值最大的方案的集合。可以证明， c o n d o r c e t 函数满足c o n d o r c e t 原则，满足无约束域条件u 、p a r e t o 准则p 和非独裁性条件d ， 但不满足无关方案独立性条件i 。 2 3 b o r d a 函数 b o r d a 函数是最常用的社会选择函数之一，在政治、经济、文化和体育等领域有大量的 应用。 定义1 0 ：b o r d a 分 设“ “= ( r l ，r 2 ，心) iv f n w ( ) ( ) ，x a ，记 似) = , v ( x r - , y ) y e a 、 x 则称f n ( x ) 丛j 给定偏好断面“f 的方案j 的b o r d a 分。 定义1 1 ：b o r d a 函数 设“ “= ( r l ，r 2 ，氏) iv f n ，r , e w 4 ( x ) ，记 c 口( a ) = x i 五0 ) 删，v y a ) t 3 中田科学技术人学研究生学位论空 则称g ( a ) 为给定偏好断面h 下的b o r d a 函数。 根据定义可知。b o r d a 函数实际上就是b o r d a 分最大的方案的集合可以证明，b o r d a 函数不满足c o n d o r c e t 原则，满足无约束域条件u 、p a r e t o 准则p 和非独裁性条件d ，但不 满足无关方案独立性条件i 。 2 4c o p e l a n d 函数 除c o n d o r c e t 函数和b o r d a 函数之外，c o p e l a n d 函数也是一种常用的社会选择函数。 定义1 2 ；c o p e l a n d 值 设u e “= ( r l ，r 2 ，) iv i e n ，r ，w ( x ) ，x a ，记 m x ) = i ，l x j 弘v y e a ) l i ) ，i y 。b x ， d y e a i 则称五舡) 为给定偏好断面下的方案x 的c o p e l a n d 值。 方案x 的c o p e l a n d 值就是用备选方案j 与其他方案逐一比较，在比较中的获胜次数与 失败次数之差。 定义1 3 ：c o p e l a n d 函数 设u e “= ( 凡，r 2 ，凡) iv f n ，氏、h x ) ，记 c o ( a ) = x l 。岛( 磅，vj ，a 则称q _ ( a ) 为给定偏好断面“下的c o p e l a n d 函数。 根据定义可知，c o p e l a n d 函数是c o p e l a n d 函数最人的方案的集合。c o p e l a n d 函数满足 c o n d o r o e t 原则，满足无约束域条件u 、p a r e t o 准则p 和非独裁性条件d ，但不满足无关方 案独立性条件i 。 2 5d o d g s o n 函数 当a = 口j ，啦，a 。 ，n = 1 ，2 ，月) 时，记 f n 2 ，玎为偶数 2 1 ( 疗+ 1 ) 2 ，硇奇数 i n ( a t a t ) 。k 2 1 。2 m 勘壬k n n 2 0 。j i k 定义1 4 ：d o d g s o n 值 设u e “= ( r i ，r 2 ，凡) iv i e n ，r ，w ( x ) ，z a ，记 1 4 中闻学技术人学研冗生学位论文 f d ( a j ) ：芝堕玉粤，- l ，2 ，棚) i l 厶 叫 则称矗( 口，) 为给定偏好断面“下的方案a j 的d o d g s o n 值。 方案白的d o d g s o n 值就是方案与其他方案的两两比较中，能战胜其他所有方案所需增 加的支持票的总数。 定义1 5 ：d o d g s o n 函数 设u e = ( r i ，r 2 ，凡) iv f n ，w ( x ) ，记 c j ( a ) = j lf o ( x ) 删，r y e a l 贝0 称c o ( a ) 为给定偏好断面u 卜的o o d g s o n 函数。 根据定义可知td o d g s o n 函数实际上就是d o d g s o i l 值最小的方案的集合。d o d g s o n 函数 满足c o n d o r e e t 原则，满足无约束域条件u 、p a r e t o 准则p 和1 f 独裁性条件d ，但不满足无 关方案独立性条件i 。 2 6n a n s o n 函数 按如下方式构造方案集序列翻j ( f m ) ： ( 1 ) 4 0 = a ： ( 2 若 a i - 1 则令以2 正、 x i f k x ) 2 璎簪五( y ) ；若 = a 则停止计 算。 定义1 6 ：n a n s o n 函数 设u e 恤2 ( r l ，r 2 ，) lv i e n ，r , e w ( x ) ，在方案集序列似 中t 设4 = 4 - t ，记 c 舭) = 4 则称c a ) 为给定偏好断面“下的n a m o n 函数。 由定义可知，n a n s o n 函数实际上是一种逐步淘汰法。在计算出所有方案的b o r d a 分后， 不是直接按得分排序，而是将b o r d a 分最小的方案淘汰出局，排在末位；再以新方案集为考 察对象，淘汰其中新b o r d a 分最小的方案，将它排在第一个被淘汰的方案之前：如此继续宣 到所有方案都被排序。 n a n s o n 幽数是对b o r d a 函数的改进，它满足c o n d o r e e t 原则，满足无约束域条件u 、p a r e t o 准则p 和非独裁性条件d ，但不满足无关方案独立性条件i 。 2 7 整数计分投票规则 中国科学技术大学研究生学位论文 天t 二文多次提刨的b o r d a 法( b o r d a 函数) ，最甲由法国学者b o r d a 提出。他注意剑 当时的一些群体决策规则( 如简单多数法) ，只考虑了投票人认为最好的方案，而不考虑每 个人对其他备选方案的偏好，这样得出的结果可能无法反映所有投票人真实的偏好。b o r d a 举出了反例并提出了自己的投票方法，即所谓的b o r d a 法：投票人对方案排序，使得对每个 投票人，每个方案都被赋予一个整数值，排序最高的方案得a 分( 口为备选方案的总数) 。 捧序第二的方案得口一1 分，以此类推，排序最低的得1 分；每个方案的总得分为方案在所 有投票人那里的得分的总和，最后的群体决策结果就是方案总得分从高到低的排序。 b o r d a 法被认为可以直接得到。折衷”的方案，从而减少为取得一致的妥协方案而可能 付出的渐在成本，所以它是“当为达到一个共同的目标寻求一个有效的途径时，求得全体 接受的正确决定的最好的i ：具，当必须统一有分歧的愿望时，最公平的方法”1 1 3 。 另一方面，对b o r d a 法的批评，主要有以f 几点。批评之一。与其它群体决策方法相比， b o r d a 法更容易被操纵”o 3 0 l 。比较常见的操纵方式，第一种是投票人虚假的表现自己的偏好， 故意压低自己最偏好方案的主要竞争对手的排序；第- 二种与b o r d a 法不满足无关方案的独立 性有关，典型的例子有所谓的日程操纵，即一部分投票人在自己最偏好方案b 没有获胜 后，要求在方案集中加入一个方案c ，并且这些企图操纵的投票人知道在大多数人看来，方 案c 仅次于b 而优于所有劣于b 的方案，这样，方案b 有可能在新的投票结果中成为胜者。 批评之二二，当存在一个c o n d o r c e t 胜者( 方案两两进行多数比较得到的最终胜者) 时，采用 b o r d a 法得到的胜者可能不是c o n d o r c e t 胜者嘲。批评之三，b o r d a 法强制的认为相邻方案 的分蒡为1 ，限制了投票入打分的自由，不能准确地反映投票人的偏好强度1 2 ”。 上述的第二个缺点，很早就被注意到，而近儿年提出的模糊b o r d a 法，允许投票人用0 和1 之间的数来表示偏好的强度，正是针对b o r d a 法这个缺点的自然延伸 9 j 5 , 2 ”。在实际生 活中，我们有时会用到另一种由b o r d a 法延伸出的投票方法，即制定最高分和最低分的标准， 要求投票人用0 和d ( d 是整数。通常大于方案个数) 之间的整数给方案打分，再由方案的 总得分对方案排序。事实上，可以把它看成一类整数计分投票方法，b o r d a 法是其中的一个 特例。 一个整数计分投票规则用可以用以下组成部分描述： 1 ) 备选方案集a ，记口= i a i ，4 2 ； 2 ) 投票人集v ，记v = l v f ，v 3 ： 3 ) 投票人对方案打分的分值集合，d = ( s l j = 0 ，1 2 ，d d a - i 。 1 6 中国科学技术大学研究生学位论文 这里，符号“i j ”表示集合的势。令( 屯e d ) 为第i ( f = 1 2 v ) 个投票人对 力寡x 的n 分鱼s i 。 s 。x 卜y ，s m 2 s 。x 一y 定义1 7 ：整数计分投票规则 记 蝌) = 川如，v y e a i - i = 1 则称铱a ) 为关于整数投蔡问题( a ，vd ) 的整数计分投票函数。 定理：整数计分投票函数不满足c o n d o r c c t 原则，满足无约束域条件u 、p a r c t o 准则p 和1 独裁性条件d ，但不满足无关方案独立性条件i 。 证明：由定义可知，帮数计分投票函数满足无约束域条件。卜面_ i i i ! 明它不满足c o n d o r c e t 原则，满足无约束域条件u 、p a r e t o 准则p 和非独裁性条件d 。不满足无关方案独立性条 件i 。 ( 1 ) 由定义可知b o r d a 法是整数计分投票规则的一个特例。当d = a - i 时，整数计分 投票规则一定程度上类似于b o r d a 法。当d a - i 时，同样可以举出反例证明它不满足 c o n d o r c e t 原则。所以。整数计分投票函数不满足c o n d o r c e t 原则。 ( 2 ) 不妨设v f ( f 2 1 2 v ) ，x - , y 。根据定义可知，v f ( f 。1 2 ，v ) ，如 所以屯，如， y g c a ) 。得证。 ，t i件i ( 3 ) 假设存在一个独裁者，不妨设为投票人1 。对于投票人1 ，v ) ，a 、扛) 根据独裁性条件，x “a ) 。 对丁其他投票人i ( f 2 2 一，v ) ，屯2 勘，。此时， & 。= + ( v 1 ) o l= 蜘1 ) 一= ( 2 v ) ( 以，- 0 ，) 因为v 3 ， 如tx 毛c a ) ，与假设矛盾。得证。 l l ( 4 ) 可以举出反例证明整数计分投票函数不满足无关方案独立性条件i 。 1 7 ( s ， 故 中国科学技术大学研究生学位论文 第3 章整数计分投票方法下全排序概率研究 3 1 问题的提出 在一定的条件f ，研究一类投票问题出现某种结果的概率，是研究投票问题性质的一个 重要方面。这一章主要讨论的就是在整数计分投票方法卜，方案集产生全排序的概率的问题。 一个计分投票规则产生全排序的概率过低，将造成决策群体无法对方案集中的若干个方案排 序，所以，如果要求一个计分投票过程对方案集产生一个全排序。使群体在任意两个方案之 间都有非无差异的偏好关系，那么我们会希望产生全排序的概率p 足够的大。p 值如何计算； 在设计一个计分投票规则时，应注意到哪些冈素影响和如何影响p 值；当p 值不够高时， 如何调整这些因素，是下面要讨论的问题。 3 2 计算全排序概率p 的公式 f 面是一些符号的约定： ( 1 ) 勺根据一个整数计分投票规则投票结束以后，定义投票入j 对方案i ( 忙1 2 ”砧 j = l 2 ，) 打分的分值为s ，o s 口而且对于投票人j 来说，方案m 劣于方 案i 1 ，= s _ 方案m 无差异于方案n ； ( 2