博弈论——选举投票（voting）
⽂章⽬录
前⾔
本⽂详细讲述了博弈论中选举（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）
