多主体系统中社会选择与机制设计 多主体系统 基础与应用 中山大学逻辑与认知研究所

第十章多主体系统中社会选择与机制设计 1 中山大学逻辑与认知研究所 本次课程主要参考资料 Vidal FundamentalsofMultiagentSystem 8章YoavKevin Leyton Brown MultiagentSystems Algorithmic Game Theoretic andLogicalFoundations 第9 10章社会选择的理论与进展 罗云峰等 第1 2 3章 2 3 内容安排 MAS的社会选择投票与孔多塞悖论社会选择函数与阿罗不可能定理MAS机制设计机制设计简介显示原理VCG分布式机制设计 4 投票问题 为何投票 在MAS中 尽管个人的偏好是足够清楚的 但是由个人组成的集体的偏好是如何定义的呢 一种加总agent个体偏好的常见方法易于理解不过 是集中式的 5 投票问题 6 投票问题 7 投票问题 8 投票的类型 非排序投票 多数票 每个投票者投一次票 选择一个大多数人偏爱的结果 累计投票 每个投票者有k张选票 选票分布在多个候选项上 可以对某个选项投多张票 获得票最多的候选项当选 批准式投票 Approvalvoting 每个投票者可以给任意多的候选项投一张票 获得票最多的候选项当选 9 投票的类型 排序投票 每个人选择最喜欢的结果得票最少的被淘汰重复直到留下一个结果 给每个结果指定一个数值 最偏好的结果得到n 1 其次n 2 依此类推 最不喜欢的0 最每个结果的得票求和统计 得分最高的当选 配对淘汰 带淘汰的多数票 首先确定配对比较的次序给定两个后果 每个人决定偏好的后果淘汰其中不被偏好的后果 根据安排重复配对淘汰 10 孔多塞条件 如果在配对淘汰中 有某个选项一直是被偏好的 该选项应该获胜 当存在很多选项时 假设选项A在与任何其它选项的两两比较中都能胜出 那A称为孔多塞胜利者 是否能选出这一胜利者是决定一个选择或投票系统好坏的重要参数 很多常用的投票系统都不符合这一条件孔多塞悖论 当人数多于二时 团体的选择有可能导致传递性的丧失 假设有三个人甲乙丙 三个选择 每个人倾向如下 甲 A B C乙 B C A丙 C A B对每一对选项投票 A或B A胜出B或C B胜出C或A C胜出可见 对与多于两个人的团体 进行选举时 可能出现无法选择的情形 称为孔多塞悖论 孔多塞条件和孔多塞胜利者 孔多塞例子 499agents 3agents 498agents ABC BCB CAA WhatistheCondorcetwinner 11 Condorcetexample 499agents 3agents 498agents ABC BCB CAA WhatistheCondorcetwinner B 孔多塞例子 12 Condorcetexample 499agents 3agents 498agents ABC BCB CAA WhatistheCondorcetwinner BWhatwouldwinunderpluralityvoting 孔多塞例子 13 Condorcetexample 499agents 3agents 498agents ABC BCB CAA WhatistheCondorcetwinner BWhatwouldwinunderpluralityvoting A 孔多塞例子 14 Condorcetexample 499agents 3agents 498agents ABC BCB CAA WhatistheCondorcetwinner BWhatwouldwinunderpluralityvoting AWhatwouldwinunderpluralitywithelimination 孔多塞例子 15 Condorcetexample 499agents 3agents 498agents ABC BCB CAA WhatistheCondorcetwinner BWhatwouldwinunderpluralityvoting AWhatwouldwinunderpluralitywithelimination C 孔多塞例子 16 SensitivitytoLosingCandidate 35agents 33agents 32agents ABC CAB BCA Whatcandidatewinsunderpluralityvoting 对去掉候选项的敏感性 17 对去掉候选项的敏感性 35agents 33agents 32agents ABC CAB BCA Whatcandidatewinsunderpluralityvoting A 18 SensitivitytoLosingCandidate 35agents 33agents 32agents ABC CAB BCA Whatcandidatewinsunderpluralityvoting AWhatcandidatewinsunderBordavoting 对去掉候选项的敏感性 19 SensitivitytoLosingCandidate 35agents 33agents 32agents ABC CAB BCA Whatcandidatewinsunderpluralityvoting AWhatcandidatewinsunderBordavoting A 对去掉候选项的敏感性 20 SensitivitytoLosingCandidate 35agents 33agents 32agents ABC CAB BCA Whatcandidatewinsunderpluralityvoting AWhatcandidatewinsunderBordavoting ANowconsiderdroppingC NowwhathappensunderbothBordaandplurality 对去掉候选项的敏感性 21 SensitivitytoLosingCandidate 35agents 33agents 32agents ABC CAB BCA Whatcandidatewinsunderpluralityvoting AWhatcandidatewinsunderBordavoting ANowconsiderdroppingC NowwhathappensunderbothBordaandplurality Bwins 对去掉候选项的敏感性 22 SensitivitytoAgendaSetter 35agents 33agents 32agents ABC CAB BCA Whowinspairwiseelimination withtheorderingA B C 对配置议程的敏感性 23 SensitivitytoAgendaSetter 35agents 33agents 32agents ABC CAB BCA Whowinspairwiseelimination withtheorderingA B C C SensitivitytoAgendaSetter 对配置议程的敏感性 24 SensitivitytoAgendaSetter 35agents 33agents 32agents ABC CAB BCA Whowinspairwiseelimination withtheorderingA B C CWhowinswiththeorderingA C B SensitivitytoAgendaSetter 对配置议程的敏感性 25 SensitivitytoAgendaSetter 35agents 33agents 32agents ABC CAB BCA Whowinspairwiseelimination withtheorderingA B C CWhowinswiththeorderingA C B B SensitivitytoAgendaSetter 对配置议程的敏感性 26 SensitivitytoAgendaSetter 35agents 33agents 32agents ABC CAB BCA Whowinspairwiseelimination withtheorderingA B C CWhowinswiththeorderingA C B BWhowinswiththeorderingB C A SensitivitytoAgendaSetter 对配置议程的敏感性 27 SensitivitytoAgendaSetter 35agents 33agents 32agents ABC CAB BCA Whowinspairwiseelimination withtheorderingA B C CWhowinswiththeorderingA C B BWhowinswiththeorderingB C A A SensitivitytoAgendaSetter 对配置议程的敏感性 28 AnotherPairwiseEliminationProblem 1agent 1agent 1agent BAC DBA CDB ACD WhowinsunderpairwiseeliminationwiththeorderingA B C D SensitivitytoAgendaSetter 对配置议程的敏感性 29 另外一个配对淘汰的问题 1agent 1agent 1agent BAC DBA CDB ACD WhowinsunderpairwiseeliminationwiththeorderingA B C D D 30 AnotherPairwiseEliminationProblem 1agent 1agent 1agent BAC DBA CDB ACD WhowinsunderpairwiseeliminationwiththeorderingA B C D D Whatistheproblemwiththis 另外一个配对淘汰的问题 31 AnotherPairwiseEliminationProblem 1agent 1agent 1agent BAC DBA CDB ACD WhowinsunderpairwiseeliminationwiththeorderingA B C D D Whatistheproblemwiththis alloftheagentspreferBtoD theselectedcandidateisPareto dominated 另外一个配对淘汰的问题 32 33 内容安排 MAS的社会选择投票与孔多塞悖论社会选择函数与阿罗不可能定理MAS机制设计机制设计简介显示原理VCG分布式机制设计 34 社会选择函数的形式模型 模型的基本设置结果的集合对其有偏好的agnet集合当前我们不考虑动机incentive的问题假设知道agent的偏好或agent真实的宣告其偏好目标 一个社会选择函数 从每个人的偏好映射到一个特定的结果 并被执行如何选择这样满足要求性质的函数 35 定义 社会选择函数和社会福利函数 Socialwelfarefunction 常用符号 36 是结果的有限集合 是O上所可能严格偏好排序的结合 为便于说明 我们采用严格排序 我们将表明即使偏好是严格排序的 也无法找到可欲的社会福利函数 社会福利函数的输入 agent的偏好排序 是由社会福利函数W所选择的偏好排序 偏好的排序回顾 37 38 帕累托有效性 39 当所有的agent统一两个后果的排序时 社会福利函数必须选择同样的排序 40 无关选项的独立性 两个备选方案的社会偏好应该只和agent给予它们的排序有关 或取决于这两个备选方案的个人偏好组合 41 独裁 不存在某个agent的偏好总是决定社会排序 如果不能满足这个性质 我们称W是独裁的 阿罗不可能定理 定理 42 阿罗的结论是 根本不存在一种能保证效率 尊重个人偏好 并且不依赖程序 agenda 的多数规则的投票方案 简单地说 阿罗的不可能定理意味着 在通常情况下 当社会所有成员的偏好为已知时 不可能通过一定的方法从个人偏好次序得出社会偏好次序 不可能通过一定的程序准确地表达社会全体成员的个人偏好或者达到合意的公共决策 这个结果令人震动 一个社会不可能有完全的每个个人的自由 否则将导致独裁 一个社会也不可能实现完全的自由经济 否则将导致垄断 人们对社会的认识达到一个新的高度 因此阿罗的不可能定理一经问世便对当时的政治哲学和福利经济学产生了巨大的冲击 甚至招来了上百篇文章对他的定理的驳斥 李特尔 萨缪尔森试图以与福利经济学不相干的论点来驳倒阿罗的不可能定理 但又遭到肯普 黄有光和帕克斯的反驳 他们甚至建立了在给定个人次序情况下的不可能性结果 事实上 阿罗的不可能性定理经受住了所有技术上的批评 其基本理论从来没有受到重大挑战 可以说是无懈可击的 于是阿罗不可能定理似乎成为规范经济学发展的一个不可逾越的障碍 43 社会选择函数 阿罗福利函数的要求太高 对所有的结果排序转而考虑社会选择函数 只要求选择最好的结果这需要我们重新定义帕累托有效性 IIA等概念 44 不可能选择被占优的结果 弱帕累托有效性 45 单调性 只要在某个偏好截面下 结果o被选择 那么在该偏好截面下当它的支持增强时也被选择 46 C是非独裁的 如果不在一个agentj 使得C总是选择agentj的偏好排序的最前面的选择 和直观相反 社会选择函数并不比社会福利函数简单 48 另外一个不可能定理 But Isn tPluralityMonotonic Pluralitysatis esweakPEandND soitmustnotbemonotonic Considerthefollowingpreferences 3agents 2agents 2agents abc bcb caa Pluralitychoosesa 49 SocialChoiceFunctionsBut Isn tPluralityMonotonic Pluralitysatis esweakPEandND soitmustnotbemonotonic Considerthefollowingpreferences 3agents 2agents 2agents abc bcb caa Pluralitychoosesa Increasesupportforabymovingctothebottom 3agents 2agents 2agents abb bca cac Nowpluralitychoosesb KevinLeyton Brown SocialChoiceFunctions Slide6 50 51 内容安排 MAS的社会选择投票与孔多塞悖论社会选择函数与阿罗不可能定理MAS机制设计机制设计简介显示原理VCG分布式机制设计 CentralizedMechanismDesignProblemDescription例子 房屋粉刷PaintingtheHouse NameAliceBobCarolineDonaldEmily Wantshousepainted YesNoYesYesYes NameAliceBobCarolineDonaldEmily Type i WantPaintDontNeedPaintWantPaintWantPaintWantPaint vi Paint i 100101010 vi NoPaint i 00000 房屋粉刷 NameAliceBobCarolineDonaldEmily Type i WantPaintDontNeedPaintWantPaintWantPaintWantPaint vi Paint i 100101010 vi NoPaint i 00000 Trythis EveryonevotesY N IfmajorityvotesYthenpainthouse Allpay1 5ofcost 4each 房屋粉刷 NameAliceBobCarolineDonaldEmily Type i WantPaintDontNeedPaintWantPaintWantPaintWantPaint vi Paint i 100101010 vi NoPaint i 00000 Trythis EveryonevotesY N IfmajorityvotesYthenpainthouse Allpay1 5ofcost 4each Bobmustpayforapaintjobhedidn twant 房屋粉刷 NameAliceBobCarolineDonaldEmily Type i WantPaintDontNeedPaintWantPaintWantPaintWantPaint vi Paint i 100101010 vi NoPaint i 00000 Trythis EveryonevotesY N SplitcostamongthosewhovotedY 房屋粉刷 NameAliceBobCarolineDonaldEmily Type i WantPaintDontNeedPaintWantPaintWantPaintWantPaint vi Paint i 100101010 vi NoPaint i 00000 Trythis EveryonevotesY N SplitcostamongthosewhovotedY ThereisanincentiveforallbutBobtolie 房屋粉刷 将社会选择环境扩展到一个新的环境中 其中不能指望agent披露期真实的偏好 不能改变agent的偏好或类型空间 不能改变结果 这样 设计者必须指定 Agent的行动集 尽管他们可能被环境所限制 到结果的映射 agent根据结果获得效用 机制设计 机制的定义 我们的任务 问题是选择一个机制 使得理性agent按照需要的方式行动 特别是最大化机制设计者的效用或目标函数 在贝叶斯博弈的意义上 每个agent有私有信息 经常的 我们感兴趣的是agent的行动空间等同于其类型空间 一个行动可以被解释为agent类型的宣告 各种看待这种问题的等价方式 执行优化任务 在某些输入信息未知的情况下 从最大化某些性能的可能贝叶斯博弈中选出一个贝叶斯博弈 设计一个博弈实现特定的均衡社会选择函数 假设设计者不知道agent的偏好和agent可能说谎 策略的执行 机制执行的定义 占优策略均衡的 占优策略执行 贝叶斯执行 直接显示机制 激励相容或诚实执行 这使得我们可以将注意力集中在实话实说对每个人都是一项最优策略的机制 Groves ClarkePaymentsforHousePainting vi o j i vj NameAlice 10 vi o 20 54 Bob 0 0 0 CarolineDonaldEmily 10 10 10 204204204 5 5 5 Assumingalltellthetruth Groves ClarkePaymentsforHousePainting Name vi o vi o j i vj Alice 10 204 5 5 15 20 Bob 0 0 0 0 20 20 CarolineDonaldEmily 10 10 10 204204204 5 5