多主体系统中的协商 多主体系统 基础与应用 中山大学逻辑与认知研究所

第9章多主体系统中的协商 1 中山大学逻辑与认知研究所 本次课程主要参考资料 Vidal FundamentalsofMultiagentSystem 第六章Wooldridge 多agent系统引论 第七章其他 蒙特和塞拉 博弈论与经济学 第五章 3 主要内容 简介讨价还价问题单调让步协议作为分布搜索的协商Ad hoc协商策略任务分配问题复杂交易基于论辩的协商协商网络 4 为何要协商 Negotiation 协商是多个agent试图达到一致或达成交易的过程 Agent利益是不同的或者是互相冲突的 需要协调 协商也是将分布式的 冲突的知识进行汇聚的方式 解决合作博弈问题或更复杂问题的方法例如 产品设计 NASAmissions 5 Anynegotiationsettingwillhavefourcomponents Anegotiationset possibleproposalsthatagentscanmakeAprotocolStrategies oneforeachagent whichareprivateArulethatdetermineswhenadealhasbeenstruckandwhattheagreementdealisNegotiationusuallyproceedsinaseriesofrounds witheveryagentmakingaproposalateveryround Negotiation 6 一种特殊协商 讨价还价问题 Bargaining 问题是找到一个协议f引导agent获得最好的收益 讨价还价 Bargaining 也称为议价或谈判 主要是指参与人 也称为局中人 双方通过协商方式解决利益的分配问题 称讨价还价时主要强调其动作或过程 称谈判时则强调其状态或结果 许多现实的交易和协调问题也可通过讨价还价理论来模拟 7 两种解决思路 公理化解决概念战略解决概念公理化方法是我们能够给出形式化的定义 因为我们相信它满足了所有重要的要求 因此称之为我们最需要的解决概念 策略方法是研究协商问题讨价还价过程的方法 它把协商问题描述成为多对策过程 策略方法经常把协商过程描述成为以Nash平衡理性假定为对策规则的非合作对策的多步移动 讨价还价问题 Bargaining 8 公理化方法 帕累托最优 帕累托前沿 一个交易是帕累托最优的 如果不存在其他交易使得agent对其的偏好超过 即不存在 使得下式成立 9 公理化方法 续 一个协商协议是独立于效用单位的 如果给定U 它选择并且给定 它选择这里 对称性 一个协商协议是对称的 如果只要效用函数保持不变 其解决保持不变 而不管哪个agent有哪个效用函数个体理性 交易是个体理性的 如果 如果 则 10 公理化方法 续 无关选项的独立性 这意味着删除失败的交易 对结果没有影响 只有删除获胜的交易才会改变协议选择的交易 11 协商的几种可能解决方案 平等主义 变化 平等主义的社会福利解决 12 平等主义解决方案 13 功利主义解决方案 14 NASH讨价还价解 15 纳什合作解设想两个人 A和B 之间要就总价值等于V的分配问题讨价还价 如果他们之间能够达成协议 V按照协议规定分配 否则 A得到d1 B得到d2 d1 d2 被称为 威胁点 或非合作状态 是不能达成协议时的最好选择 其中d1 d2 V且S V d1 d2是合作带来的剩余 分配规则 x表示A得到的价值 y表示B得到的价值 假定A和B分别从合作剩余S中得到h和k的份额 那么 x d1 h V d1 d2 x d1 h V d1 d2 y d2 k V d1 d2 y d2 k V d1 d2 y d2 x d1 k h讨价还价的唯一结果是最大化如下函数的解 max x d1 h y d2 k 称为纳什福利函数 或max x d1 y d2 NASH讨价还价解 纳什证明 如果满足下列条件1 帕累托效率 最后达成的协议应该是帕累托最优的 也就是说 不应该有没有被分配的剩余 2 不改变个人风险决策 3 如果原来可行的选择没有被选择 去掉这些 无关 选择并不会影响讨价还价的结果 那么 讨价还价的唯一结果是最大化如下函数的解 max x d1 y d2 称为纳什福利函数 练习 验证NASH讨价还价均衡解满足前述性质 NASH讨价还价解 17 a b 对最后的分配具有决定性的意义 可以理解为 谈判砝码 或 谈判力 bargainingpower h和k是合作剩余的分配比例 称为谈判耐力 bargainingstrength 如果两个人是对称的 则h k 0 5 谈判砝码对达成什么样的分配协议具有决定性的意义 决定结果的是相对砝码 d2 d1 如果A的砝码d1不变 B增加自己的砝码d2就可以使得自己在谈判中占优势 例 劳资谈判学生毕业时找工作有多少个offers NASH讨价还价解 18 NASH讨价还价解 19 讨价还价扩展 N人NASH讨价还价解最后通牒博弈 Ultimatumgame 20 21 22 23 讨价还价博弈的分析 注意到既然每个agent的效用都随着时间的基站而减少 因此最好的交易是在第一步中的得到 这意味着每个agent必须提出一个其他agent接受的交易 特别的 agenti必须提出一个交易否则如果交易提供的收益较小 agentj会拒绝交易 如果较大则浪费了 同理有 24 25 讨价还价模型的理解与启示 1 贴现因子贴现因子在数值上可以理解为贴现率 就是1个份额经过一段时间后所等同的现在份额 这个贴现因子不同于金融学或者财务学的贴现率之处在于 它是由参与人的 耐心 程度所决定的 耐心 实质上是讲参与人的心理和经济承受能力 不同的参与人在谈判中的心理承受能力可能各不相同 心理承受能力强的可能最终会获得更多的便宜 同样 如果有比其他参与人更强的经济承受能力 也会占得更多的便宜 2 先动优势 与 后动优势 在讨价还价的谈判中 先出价的一方和后出价的一方有着各自的优势 即所谓的 先动优势 和 后动优势 这两种优势的发挥取决于前面提到的耐心优势 先动优势 通过模型可清楚地看出来 为方便起见 假定 1 2 当 X 1 1 0 5 即参与人1的份额总是大于参与人2的份额 始终处于有利的位置 也就是说 在双方都没有足够耐心的情况下 先出价的总是处于有利位置 然而 在双方都有足够耐心的情况下 即当 1 2 1时 后出价的一方占据了有利位置 这是因为 参与人最后出价时 他将拒绝任何自己不能得到整个份额的出价 一直等到博弈的最后阶段得到整个份额为止 这种 后动优势 只是在理论上有意义 因为现实中的参与人都不可能有足够的耐心 3 尽快接受 原则由于贴现因子的作用 参与人在本期所得的份额X和下期所得同样份额的X在价值上是不相等的 下期的x经过贴现只能等于本期的 X 要小于本期的X 因此 参与人均应尽快接受对方合理的报价 否则 即使在下期谈判中获得相同甚至更多的份额也町能小于本期的份额 讨价还价的其他因素谈判成本不同 讨价还价的锄强助弱性质 外部机会成本不同 把其他人引入谈判中可以获得交易的所有剩余 不理性 的策略 把谈判引向失败的边缘可以让人相信你的威胁 也就是你会做有违自己利益的事情 谈判面临的最大问题是信息不完全 谈判的过程实际上是信息揭示和窥探的过程 砍价公司由于信息不对称 谈判的结果并不总是帕累托最优的 事实上 许多帕累托改善没有被利用 谈判中的社会规范程序规范 出价顺序 例如谈恋爱总是男的先追求女的 一旦接受不可翻悔时限授权限制底价 28 单调让步协议 29 30 31 32 33 34 ZeuthenStrategy 35 36 既然可以通过多步到达某个特定均衡 何不直接跳到最后的协议 37 Agent协商的过程可以视为一个分布式优化的过程 通过协商 agent搜索一个特定解 从一个初始交易出发 每一步协商都移到另外一个更好的交易 38 选定一组特定的策略 并互相检验进行协商 基本的协商模型是带贴现因子的轮流出价模型 如 39 40 邮递员问题 假设agent随意匹配并协商交换一个任务 不是所有的交易都是互相连通的 41 任务分配例子 两个节点如果有边相连的话 表示可以通过一步协商到达 42 一种方法是通过支付转移来帮助agent找到更接近功利主义的交易 支付 43 44 45 46 47 48 支付转移将一个交易可以转换为无穷个交易爬上法的局限 转移支付可以可以帮助达到功利主义解 49 能否达到功利主义解取决于成本函数的形式 在成本可加函数形式下可以获得 可加成本函数易于分析 50 成本可加函数的支付转移 引入支付转移后 可以达到功利主义解 新产生的交易用平行线表示 51 灵活的交易语言OCSM 允许所有可能组合的任务转移引入了更多的复杂性 52 53 如果没有t2 nash讨价还价解是 i的收益为1 如果加入任务t2 i的收益为2 54 Contract 契约 杠杆承诺协议 55 试探性契约 56 57 58 模拟退火算法 采用一个中介 59 60 61 62 63 64 Argumentation 7 65 ArgumentationistheprocessofattemptingtoconvinceothersofsomethingGilbert 1994 identified4modesofargument Logicalmode IfyouacceptthatAandthatAimpliesB thenyoumustacceptthatB Emotionalmode Howwouldyoufeelifithappened