文章目录
- 前言
- 一、相对多数投票法(Plurality Voting)
- 二、孔多塞准则(The Condorcet Criterion)
- 三, 谷轮法(Copeland method
- 四,波达计数法(Borda Count)
- 五,选举的三个性质
- 帕累托最优(Pareto Efficiency)
- 无关因素独立性(Independence of Irrelevant Alternatives (IIA))
- 非独裁(Nondictatorship)
- 弱帕累托最优(Weak Pareto Efficiency)
- 单调性(Monotonicity)
- 策略选举(Strategic Voters)
- 总结
前言
本文详细讲述了博弈论中选举(voting)的理论知识
一、相对多数投票法(Plurality Voting)
让我们考虑一个场景,在一个学术聚会上,15名学者对饮品进行了投票选择。eg:对于学者1,他的偏好是beer>wine>milk
候选项(牛奶,啤酒,白酒)根据其被排名第一的次数排名:
如图所示:
啤酒得到六次第一
白酒得到两次第一
牛奶得到七个第一
即,牛奶胜出
但是,这是大多数人都不喜欢的结果,除了学者13
孔多塞驳论(The Condorcet Paradox)考虑以下情况:
我们无法从这三个人的偏好顺序当中选取Plurality Vote winner。
•无论选择哪种选项,三分之二的选民将更喜欢另一种选择!
•Condorcet的悖论告诉我们,在某些情况下,无论我们选择哪种结果,大多数选民将不开心。
二、孔多塞准则(The Condorcet Criterion)
Condorcet赢家是在全部的成对相对多数投票策略选举中都胜出的人。
Condorcet赢家并不总是存在。
如果投票系统始终选择存在的Condorcet赢家,则该投票系统满足Condorcet的条件。
满足此属性的规则称为Condorcet方法,并被称为Condorcet一致。
例如上题:
•Beer vs Wine: Beer=7, Wine=8
• Wine vs Milk: Wine=8, Milk=7
• Beer vs Milk: Beer=8, Milk=7
因为,wine在每次成对的对比中都获胜,所以wine是孔多塞赢家。
三, 谷轮法(Copeland method
)
每个候选人都是根据其成对的胜利减去其成对的损失来得分的。
•候选人根据分数排名(最高分数排在首位)。
•容易看出该方法符合孔多塞准则。
•葡萄酒赢了两次,啤酒赢了1次,输了1次,牛奶总是输。
所以针对例题,谷轮法的结果不变:Wine>Beer>Milk
但是谷轮法在没有孔多塞冠军时依然可以选出赢家。
考虑如下情况:选举有5名候选人,由100人投票:
31人:A>E>C>D>B
30人:B>A>E (没人选C D)
29人:C>D>B (没人选A E)
10人:D>A>E (没人选B C)
两两对比的结果如下:
当A vs B时,(31+10)/(30+29) = 41/59 以此类推得上图。
观察可得,由于A,B,C,D,E都没有在成对的比较中全部获胜,所以没有孔多塞冠军。但是由于A赢的次数最多,所以我们成A为谷轮冠军(Copeland winner)。
四,波达计数法(Borda Count)
•之前的投票程序仅考虑排名靠前的候选人。
•Borda计数考虑了优先顺序中的所有信息。
•此方法进行如下:
•对于x个候选人,每个投票人将x分数奖励给他们的第一选择,x − 1奖励给他们的第二选择,依此类推。
•得分最高的候选人获胜。
如例题:6人将啤酒排在第一位,3人排在第二位,6人排在第三位
所以啤酒的得分为 63+32+6*1=30
同理,白酒31,牛奶29.
即 wine>beer>milk
注意,Boeda Count不符合孔多塞准则 例如下图:
五,选举的三个性质
为了评判选举过程是否合理,我们觉得选举应该符合以下三个性质
帕累托最优(Pareto Efficiency)
对于全部的N个排列顺序,如果A都在B之前,那么最后的结果A一定在B之前。
无关因素独立性(Independence of Irrelevant Alternatives (IIA))
两个人的相关顺序不变的话,其他参与者的相对位置发生了变化,那么这两个人的相对位置也不会发生变化。 投票问题(voting theory)中,假如有四个候选人,即A、B、C和D,如果大多数民众(即超过一半)一致认为A优于C,那么B和D的相对位置发生了变化,也不会影响大多数民众的偏好上A优于C。
非独裁(Nondictatorship)
不存在这样的选民,使得他的选择一定为最后结果。
注意!没有任何一种选举方式可以同时满足以上三个条件。对于具有两名以上候选人的选举,任何满足帕累托效率和IIA要求的社会福利职能都是独裁的————Arrow’s公理。
弱帕累托最优(Weak Pareto Efficiency)
如果,选举中的每一个代理人比较A和B时都更喜欢A,那么B不可能是最终的选举结果
单调性(Monotonicity)
一个社会选择四个候选人,即a,b,c和d。每个人对这四个候选人都有各自的偏好顺序。我们暂且把这个每个人的偏好顺序的集合为u,而社会最终选出的结果为a。假如,存在一个社会偏好集合v,而这个v满足如下三个条件,
1)对于除了a之外的其余三个候选人b,c,d,对于任何两个候选人(暂且为b和c),如果满足u(b)>u©,则v(b)>v©成立;
2)a在v当中的顺序相对于u集合,至少相等或改善;
3)v不等于u,因此,a在v中的相对次序比u至少向前移了一步。
那么,在社会偏好集合v中,最后选出来的肯定是a。
一句话来概括的话,两个社会偏好集当中,有一个候选人a的位置向前移了一步,其余的候选人相对位置都没有发生变化,那么如果原来的社会偏好选择a的话,在新的社会偏好当中也会选择a。这就是单调性。
穆勒-萨特斯韦特定理(Muller-Satterthwaite’s Theorem)
对于拥有两名以上候选人的选举,任何满足弱帕累托效率低和单调性的社会选择功能都是独裁的。
策略选举(Strategic Voters)
如果选民的行为是战略性的,当他们战略性的进行投票时,会产生不一样的结果。换句话说,当选民可能通过单方面改变自己的偏好使最后的结果更符合自己的期望,这种方式可能是谎报偏好。
我们可以设计无法操作的投票程序吗?
Gibbard-Satterthwaitte定理
任何具有至少三个满足citizen sovereignty(民主权)并且不可操纵的结果的社会选择功能都是独裁的。
总结
一、相对多数投票法(Plurality Voting)
二、孔多塞准则(The Condorcet Criterion)
三, 谷轮法(Copeland method
四,波达计数法(Borda Count)
五,选举的三个性质
帕累托最优(Pareto Efficiency)
无关因素独立性(Independence of Irrelevant Alternatives (IIA))
非独裁(Nondictatorship)(Arrow’s Theorem)
弱帕累托最优(Weak Pareto Efficiency)
单调性(Monotonicity)(Muller-Satterthwaite’s Theorem)
策略选举(Strategic Voters)(Muller-Satterthwaite’s Theorem)