第十二讲 群体决策模型
数学建模
讲义
NUDT
2023SP
基本概念
- 机制设计 (Mechanism design)、社会选择 (Social choice) 和博弈论 (Game theory) 是现代社会科学家们研究“民主问题”的标准工具.
- 群体决策:根据群体中每个成员的决策结果,综合得出群体的决策结果.
12.1 选举问题
- 个选民:
- 个候选人:
- : 选民 对候选人的一个排序( 维向量);
- : 根据选举规则及排序分布 确定的对 中元素的群体排序结果
排序的性质
对 的任何一个排序应有如下性质:
- 完全性:对一切 , 有且仅有下列关系之一成立
- 传递性:对于 , 若 且 , 则有 .
- 符号约定:
例:球队的排名
30 名学生从 A、B、C、D 共 4 支球队中投票选出最受欢迎的球队,每个学生独立给出其排序结果后,统计结果如右侧所示:
- 问:哪只球队是最受欢迎的球队?
- 似乎人人都有机会,关键看如何确定排名规则!
例:州长选举
1998 年 Minnesota 州州长选举,3 位候选人是 Coleman,Humphrey 和 Ventura,得票结果如下
- Ventura:得到的第 1 名票最多,但 2/3 票为最后 1 名
- Coleman:第 1 名的票数少 2%,且最后 1 名票数最少
- 最终 Ventura 获胜
排名规则:简单多数法
- 简单多数法(plurality method or simple majority method):得到第 1 名票数最多的候选人为获胜者
- 显然,简单多数法没有考虑除第 1 名以外的得票信息
- 候选人越多,问题可能越严重
排名规则:单轮决胜法
- 单轮决胜法(single runoff method):得到第 1 名票数位列第 1、第 2 的两位候选人进入决胜轮,由简单多数法决定决胜轮的获胜者,并确定为最终获胜者
- 首轮 ,
- 决胜轮
- 两轮结果综合,C 胜出
排名规则:系列决胜法
- 系列决胜法(sequential runoff method): 进行多轮决胜投票,每轮只
淘汰得第 1 名票数最少的
候选人,当剩下两位候选人时,由简单多数法决定获胜者,并确定为整个选举的获胜者
- 最终 C 胜出
例:奥运主办城市选举
2004 年夏季奥运会 5 座入围城市是 Athens, Buenos Aires, Cape Tow, Rome, Stockholm. 在奥委会的各轮投票中不要求成员对候选城市排序,只投票给最偏爱的一座城市,每轮投票淘汰得票最少的城市.
排名规则:Coombs法
- Coombs法:进行多轮决胜投票,每轮只
淘汰倒数第 1 名票数最多的
候选人,当剩下两位候选人时,由简单多数法决定获胜者,并确定为整个选举的获胜者.
- 最终 D 胜出
排名规则:Borda 计数法
- Borda 计数法
- 对每一张选票,排倒数第 1 名的候选人得 0 分,排倒数第 2 名的得 1 分,依此下去,排第 1 名的得分是候选人的总数减 1
- 将全部选票中各位候选人的得分求和,总分最高的为获胜者
- Borda 数:,其中 为 中劣于 的元素的数目
- 各位候选人的 Borda 数:
- 根据 Borda 计数法,D 胜出
进一步的讨论
- ,按 Borda 数规则应有
- 此例说明,在 Borda 数规则之下,个别人的意向更容易左右群体决策的结果,从而为 策略投票 提供了机会
策略选举与 Borda 数规则
- 设有 15 个选民与 3 个候选人 ,有意向表
- 则 , , ,所以依据 Borda 数规则,最后投票结果为 .
- 以上称为 真诚选举 或 非策略选举.
- 如果支持 的 7 位选民采用 策略选举,不按照他们的真实意向投票,而改为 ,则 , , ,于是,结果为.
12.2 选举中的公平性准则
1. 多数票准则
- 多数票准则:超过半数的选民认为 ,则最终排名应为
- 简单多数法、单轮决胜法、系列决胜法、Coombs 法和 Borda 数规则都不满足多数票准则.
- 按多数票准则,D 胜!
- 按简单多数法 B 胜,按单轮、系列决胜法,C 胜!
- 按多数票准则,B 胜!
- 按Coombs法,D 胜!
- 由于 ,按 Borda 数规则应有 .
- 而按多数票准则, 是获胜者
Condorcet 悖论
- 由多数票准则将得到 , , .
- 此时的情况称为 投票悖论(paradox of voting)或 Condorcet 悖论(paradox of Condorcet)
2. 获胜者准则
- 获胜者准则(Condorcet 准则):如果候选人 在与每一位候选人的两两对决中(按照多数票准则)都获胜,那么 应当是获胜者
- 简单多数法、单轮决胜法、系列决胜法、Coombs 法和 Borda 数规则都不满足 Condorcet 准则
- D 与 A:21:9,D 胜
- D 与 B:19:11,D 胜
- D 与 C:20:10,D 胜
- 综上,D 胜
- 所以,简单多数法、单轮决胜法、系列决胜法都不满足 Condorcet 准则
- 在与所有候选人的两两对决中获胜,但按 Coombs 法, 胜. 所以 Coombs 法不满足 Condorcet 准则
- 在与所有候选人的两两对决中获胜,但按 Borda 法, 胜. 所以 Borda 数规则不满足 Condorcet 准则
3. 独立性原则
- 无关选择独立性(简称 独立性原则): 假定在最终排序中候选人 领先于候选人 ,则如果其他一位候选人退出选举,或者一位新的候选人进入选举,在最终排序中候选人 仍应领先于候选人
4. 单调性准则
- 单调性准则: 在两次投票中,假定第 2 次投票时所有选民对候选人 的排位都没有退后,且对其他候选人之间的相对排序均未改变,则 在第2 次投票中的最终排位不应落后于第 1 次投票中的排位
- 简单多数法,Coombs 法和 Borda 数规则都满足单调性准则.
- 单轮决胜法和系列决胜法不满足单调性准则.
Kenneth J. Arrow
- 1921-2017, 美国著名经济学家,在微观经济学、社会选择等方面卓有成就
- 1951 年,Arrow 在他的博士论文 Social Choice and Individual Values(社会选择与个人价值)中,首次运用数理逻辑的分析工具,对社会决策和社会民主程序设计之间的关系做了形式化的深入研究
- 所得出的 “不可能性定理” 在西方经济学界引起了轰动,被认为是近数十年来数学应用于社会科学所取得的一项突出成果
Arrow 不可能定理
- Arrow 认为除非我们在不同个体之间进行功利比较,我们就无法得出一个满足所有条件的社会偏好理论
- "如果我们排除了人与人之间衡量功利(utility)的可能性,那么能够将个人偏好转换至社会偏好、且广泛适用于个人排序的方法都将是被强制性或者独裁性的"
- 1972 因一般均衡理论和福利经济学方面的先驱性贡献而获诺贝尔经济学奖
Arrow 公理
- 非独裁性(nondictatorship):不存在这样的投票人,使得候选人的最终排序总是与他的排序相同
- 普遍性(个人选择独立性):投票人对候选人的任何排序都是允许的
- 一致性:如果每个投票人都将某一个候选人置于另外一个之前,在群体排序中这两个候选人也应如此排序
- 独立性 (无关选择独立性)
- 单调性
Arrow 不可能定理
对于至少有三名候选人和两名选民的投票,任何一种满足可传递性的投票方法都至少违反下列准则之一:非独裁性、普遍性、一致性、独立性、单调性.
- 不存在一种能保证效率、尊重个人意向、并且不依赖程序的多数规则的投票方案。或者说,不可能通过一定的程序准确地表达社会全体成员的个人意向来达到合意的公共决策
- 完美无缺的程序民主不存在!
12.3 越野长跑团体赛竞赛规则的公平性
- 越野长跑团体赛的 (5,2)规则 如下:每个参赛团体由 7 名队员组成,取该团体
跑在前面的 5 个队员在所有参赛选手中的排名顺序之和
为该团体的得分,然后根据各参赛队得分的顺序决定比赛排名.
- 试讨论该竞赛规则的合理性并提出改进方案.
比赛公平性的几个判断准则
- 准则一:二元独立性(binary independence): A 与 B 两个队的相对顺序不应当依赖于任何其他队的表现.
- 准则二:Condorcet 准则(Condorcet Criterion): 一个队如果与任一个队的两两对决中获胜,则这个队应当是整个比赛的优胜者.
- 准则三:单调性(Monotonicity Criterion): A 队是一次竞赛的获胜者,假如在另一次竞赛中所有的参赛队与选手都不变,A 队的一个选手 a 提高了名次,而除 a 之外的其他所有参赛选手之间的相对顺序都不变,则 A 队仍应是获胜者.
- 准则四:Pareto 条件(Pareto Condition): 如果 A、B 两队各有 个队员参赛,且有 , ,则 A 队排名应优于 B 队.
(5, 2) 规则的公平性
实例 1 设一次越野团体赛有 33 个队 231 名队员参加,其中 3 个队的队员成绩如下:风队
: 1,2,3,8,27,36,45(总分41);越野者队:4,12,15,24,35,49,55(总分90);酷跑队:10,11,13,28,30 ,43,69(总分92).
- 考虑后两队的顺序:
- 结论 1: (5, 2) 规则不满足二元独立性.
(5,2)规则的公平性判断
实例 2 设一次比赛有 A、B、C、D 四支队伍参加,成绩如下:A:1 2 3 25 26 27 28(57);B:4 9 11 14 16 18 20(54);C:5 7 12 13 19 21 22(56);D:6 8 10 15 17 23 24(56).
- 总分 B 队第一,A 队垫底!
- 但在与 A 队两两对决中,A 队前 5 名名次为:1 2 3 11 12,得分 29,而其他队名次都是 4 到 10,得分 30,A 队胜!
- 结论 2: (5, 2) 规则不满足 Condorcet 准则
(5,2)规则的公平性判断
- 结论 3:(5, 2) 规则满足单调性
- 结论 4:(5, 2) 规则满足 Pareto 条件
- 总体来说,(5, 2) 规则还是比较合理的
其他竞赛规则评价
- 名次加权 (m,l) 规则:名次差异非均匀化
- 不满足二元独立性与 Condorcet 准则,但满足单调性与 Pareto 条件
- 迭代 (m,0) 规则:每次淘汰最后一名,然后重新计算名次
- 满足 Condorcet 准则与 Pareto 条件,但不满足单调性,也不满足二元独立性
- 顺序 Condorcet 规则:按任意顺序,前两队对决,胜者与下一队对决,如此进行下去,最后留下的队就是获胜队
- 满足 Condorcet 准则和单调性,但不满足二元独立性与 Pareto 条件
- 非团队规则:存在 ,使得
实例 3 考虑 3 个队参加的一次比赛,采用迭代 规则,比赛进行到一半时,成绩如下:
- 三队目前得分为:38, 40, 42. 淘汰 C 队后成绩如下:
- 第二轮得分为:25,30,故最终 A 队将夺冠
假设在 A 队教练的督促下, 从第 11 名前进到了第 6 名
- 此时得分为:33, 45, 42,B 队将被淘汰
- 第二轮得分为:A:28, C:27, A 队被淘汰,C 队夺冠!
- 故迭代 (5, 0) 规则不满足单调性
实例 4:考虑 4 个队参加的一次比赛,采用顺序 Condorcet 规则,两两对决时采用 (3, 0) 规则. 比赛结果为:
- 设两两对决顺序为 A B C D
- A vs B,11:10,B 胜
- B vs C,11:10,C 胜
- C vs D,12: 9,最终 D 胜!
- 注意到:, ,所以不满足 Pareto 条件.
实例 5:(非团体规则)考虑 2 个队的比赛,每个队派两名队员,共有 6 种可能结果:
- 假设满足 Pareto 条件,则 A 赢得 1、2,B 赢得 4、5。
- 如果 A 赢得 3,则对称的,B 赢得 6,这时的胜负实际上由各队的第一人决定,因此是非团体规则
- 反过来,如果 A 赢得 6,B 赢得 3,这时的胜负由各队的第二人决定,仍然是非团体规则
越野团体赛计分规则的 Arrow 定理
以名次为排序依据,那么,在有至少三个队参加的越野团体赛中,如果一个规则同时满足二元独立性与 Pareto 条件,则该规则是非团体规则.
- 由于 Pareto 是必须满足的,所以,此定理的结论也说明,就名次排序规则而言,满足二元独立性是一种奢望
12.4 实际竞赛方案
- 时间排序规则:按各队前 5 名队员的竞赛时间之和排名
- 该规则同时满足二元独立性、Condorcet 准则、单调性和Pareto 条件
- 时间排序规则的不足
- 人的体能是有限的,要提高相同的时间,水平越高的运动员,要付出越多的努力
- 百米成绩从 20 秒提高到 19 秒很容易,而从 10 秒提高到 9 秒则付出毕生精力也未必能达到,若按时间计成绩,他们对团体名次的贡献却是一样的
合理计分规则
- 准则 5:成绩与训练难度匹配原则
- 合理计分规则:采用 竞赛方案,记录所有运动员比赛时间,按照《国际田联田径项目分值表》转换为得分,取各队前 名队员的总得分为排序依据.
实例 6:从《2010 北京马拉松男子全程成绩表》中取出 14 名选手分作两个团体,成绩及转换分数如表:
最终成绩
小结
- 深入分析公平性的内涵,提出公平性准则;
- 构造合适的实例来说明问题;
- 国际田联积分表的应用,以及北京国际马拉松成绩的利用,增强了模型的说服力
课后思考题
()请论证或举例说明,简单多数法、单轮决胜法、系列决胜法、Coombs 法和 Borda 数规则是否满足独立性准则.