第七章 达成一致 达成一致的能力是自治的智能Agent的基本能力，具体是指协商和辩论的能力。

Presentation on theme: "第七章 达成一致 达成一致的能力是自治的智能Agent的基本能力，具体是指协商和辩论的能力。"— Presentation transcript:

1 第七章 达成一致 达成一致的能力是自治的智能Agent的基本能力，具体是指协商和辩论的能力。
第七章 达成一致 达成一致的能力是自治的智能Agent的基本能力，具体是指协商和辩论的能力。 协商不是在真空中发生的，它们受一种特定的机制或协议支配。 可以对协议进行设计使得任何特定的协商过程都具有特定的所希望特性。——机制设计 给定一个特定的协议，如何设计个体Agent协商时可以使用的特定策略，从而使得其个体自身的利益最大化。——一定机制下的协商策略

2 机制设计（一） 不同的协商协议有着不同的性质，具体有： 保证成功——如果最终能确保达成一致，则协议保证成功。
最大社会利益——如果保证任何输出都能使参加协商的各方效用的总和最大，则协议的社会利益最大。 Pareto效率——如果不存在其他的协商结局使至少一个Agent更好而没有使其他Agent更差，则称这个协商结局具有Pareto效率。

3 机制设计（二） 个体理性——如果遵守一个协议（按规则游戏）能保证协商参加者的最大利益，则称这个协议是具有个体理性的。
稳定性——如果一个协议使所有的Agent都有按照特定方式行动的动机，则这个协议是稳定的，如Nash平衡。 简洁性——一个简洁的协议对于协商的参加者来说能显而易见地作出合适的策略。 分布性——应该使Agent之间的通信最少。

4 拍　　　卖 　　作为一种商品交易机制,在市场经济中应用十分广泛,巨额的经济活动都是通过拍卖的方式进行。经常被拍卖的物品包括古董、珠宝、精美的艺术品、住房、旧车等有形资产,也包括一些无形资产,比如,土地使用权、油田和矿藏的开发权、森林的砍伐权,甚至一些特别电话号码、汽车号码的使用权等。美国财政部和加拿大中央银行还经常采用拍卖的方式销售政府债券,香港政府每年都要公开拍卖大批量的土地给发展商开发使用。

5 拍 卖 Ebay的流行，原因之一就是拍卖是极为简单的交互情形，这使拍卖成为Agent达成一致，另外，拍卖也为自动Agent提供了用来分配物品、任务和资源的有力工具。 拍卖物品是否有公开（公共）或者收藏价值会影响拍卖协议和Agent使用的策略的因素。（包括个人认为的价值和他人认为的价值） 拍卖中的几个问题：第一，谁能得到卖方竞标的物品；第二，参加拍卖的Agent是否互相了解；第三，叫价的机制。

6 拍 卖 问：谁能得到卖方竞标的物品？ 答：第一价格拍卖和第二价格拍卖。前者指出价最高的Agent获得这个物品，而后者是指物品分配给开价最高的Agent，但是这个Agent只需要支付第二高的出价金额。 问：参加拍卖的Agent是否互相了解？ 答：如果每个Agent可以看到所有其他Agent的出价，则称拍卖是公开叫价，如果Agent不知道其他Agent的出价，这种拍卖称为秘密叫价拍卖。 问：叫价的机制是什么？ 答：一轮拍卖、加价拍卖、降价拍卖

7 英国拍卖 中央台黄金时间广告 是最常见的拍卖，在Sothebys拍卖行举行 第一价格、公开叫价、加价拍卖，具体含义？
此类拍卖中Agent采用的优势策略是相继以略高于当前最高叫价的价格叫价，直到叫价达到他们当前的估价，然后撤标。 有意思的现象:中标者的悲哀

8 荷兰拍卖 是一种公开叫价、递减式拍卖，具体含义是什么? 它同样容易出现中标者的悲哀； 一般该类拍卖没有优势策略。

9 第一价格密封叫价拍卖 一轮拍卖； 遇到的最简单的拍卖形式； 物品分配给叫价最高的Agent； 此类拍卖中，Agent应该如何出价？

10 Vickrey拍卖 对拍卖机制作出开创性研究的Vickery获得了1996年诺贝尔经济学奖 最不寻常也最不直观的一种拍卖；
是第二价格密封叫价拍卖； 为什么会需要这种拍卖？——因为其能给出真正的优势策略：在有收藏价值的这类拍卖中，买方的优势策略就是以真实的估价叫价。 该类拍卖使得反社会行为成为可能。 对拍卖机制作出开创性研究的Vickery获得了1996年诺贝尔经济学奖 文献：二级密封拍卖机制的理论分析，林融、张义祯

11 其他拍卖机制 M+1价拍卖：要拍卖M个单位的同一种物品，M个出高价者中标，每个中标者购买一个单位，但统一按照未中标者中出的最高价M+1价付款。 分级拍卖：按拍卖成交的次数可分为单级拍卖和分级拍卖。在某些情况下，有必要先进行子拍卖， 子拍卖的胜者进入下一级拍卖。 ……

12 期望收益 卖方希望有一个拍卖协议能最大化其收益，而不关心Agent是否给出了真正有效的策略。这种情况下卖方该如何作出选择？
对于风险中立的买方，上述四种拍卖卖方可以获得同样的收益； 对于不愿冒险的买方，荷兰拍卖和第一价格密封叫价卖方可以获得更高的收益； 对于不愿冒险的卖方，用Vickrey拍卖和英国拍卖会做得更好。

13 说谎、串通和反投机 讨论：上述四种拍卖中对说谎、串通的免疫力如何？有没有好的办法防止这些恶意的行为？
反投机是买方为了获得关于拍卖物品的真正价值信息或者关于其他买方的估价信息所参与的过程。 反投机能切实减少Agent对拍卖物品的真正价值或者其他买方出价的不确定性。 反投机往往需要消耗时间和金钱。

14 串　　通 串通出价是非法的, 如果串通行为很明显,卖方会调整相应的拍卖机制,卖方可以提高保留价,或者采用隐蔽保留价制度,或者其他的一些方式来破坏串通。 串通出价的最大困难还在于,参与者可能会改变他的策略。因此,串通小团体必须设计一种激励相容、自愿参与, 并且有效的串通机制,即,没有人离开该小团体,也没有人背叛小团体。 　　比如说,在第一价格拍卖中,所有竞标者约定好,每个人标价等于卖方的保留价,其中任何一个人赢得物品,然后支付给其他投标者一些补偿。但任何人都有可能标价比保留价高一点点,从而自己赢得物品,而不给其他人任何补偿。

15

16 网上拍卖的安全性 公平性：指竞买者地位一样，系统设计无偏向性，有办法解决争议和违约。 不可否认性：竞买者出价后不能否认其出价。
不可伪造性：竞买者的出价不能被伪造。 可证实性：可公开证明最终的中标者的合法性。 时限性：规定的结束时间前，任何参与者都无法打开竞价者的出价。 出价保密性：指除成交价暴露外，竞买者的出价在拍卖过程中和拍卖完成后保密，即使是未中标者的出价。 竞买者匿名：竞买者的个人身份在拍卖过程中和拍卖完成后保密。

17 网上拍卖安全性相关技术 盲签字和公平盲签字技术　盲签字是指签字人所签字的信息在不暴露信息的所有者的情况下可被验证的一种签字技术.盲签字技术在保证匿名性方面有着重要作用,这种技术在诸如电子现金系统、电子选举系统、股票交易系统、公路和地铁收费系统等电子商务中已经得到了广泛应用 。 群签字和群盲签字技术　一个群签字方案允许群中成员代表该群体对信息进行匿名签字,有一个可信赖的第三方能够在发生争议时给出签字人的身份.自从Chaum等提出群签字之后,已研究出很多群签字方案,但大部分效率不高,且要求群公钥和群签字的规模随群成员的规模线性增加.最近JanCamenischand M.Stadler给出了两个不依赖于成员个数的群签字方案,这个群签字方案还可以用来建立群签字共享方案. 群盲签字技术是把群签字技术和盲签字技术结合起来的一种签字方案。

18 网上拍卖安全性相关技术 零知识证明　该理论首先由Goldwasse,Micali和Racko等提出,它是一种交互式概率证明方法,示证者(Prover)能使验证者(Verifier)相信他确实掌握某种信息而不暴露该信息.特别地,在零知识证明后,验证者无法单独使第三方相信示证者掌握该信息。 不可否认协议　该协议能够使通信双方交换信息,而在交换后双方无法抵赖.每一个参与者在通信的同时都收集有证据,这些证据将来能够在法庭上证明对方确实发送或接受了某种信息.该协议要求具有“证据正确”这一特性,即证据足以满足持有者的要求.在一些情况下,协议也要求具有公平性,即一方获得证据的同时另一方也一定获得了证据 。 最优公平交换协议　该协议允许两个互不信赖的实体以一种公平的方式交换信息,在协议执行后,要么双方都得到了对方的信息,要么都没有得到对方的信息.被交换的信息的形式可以是一个文件,也可以是一个签字,还可以为别的形式.最优公平交换协议假定离线可信赖第三方(TTP)的存在,但TTP仅在出现有争议的情况下才出现 。

19 协 商 拍卖是Agent分配物品时非常有用的技术，然而在很多情况下，当Agent需要就共同关心的问题达成一致时，达成一致需要更多的技术，协商就是这些技术的总称。 Rosenschein 和Zlotkin（1994年）引入了不同领域的协商的区别，区分了面向任务领域的协商和面向价值领域的协商。

20 协商的一般技术 协商框架有四个不同的部分： 一个协商集合，表示Agent可能提出建议的空间； 一个协议，定义Agent提出的合法的建议，它是先验的协商历史的函数； 一组策略，每个Agent一个策略，决定了Agent将会提出什么建议； 一条规则，决定什么时候达成交易以及这个一致的交易是什么。 总之，协商同场进行多轮，每个Agent每一轮都给出建议。Agent给出的建议由其策略决定、必须来自协商集合中、并且必须是合法，是依协议来定义的，如果根据所定的一致规则达成了一致，则带有一致交易的协商结束。

21 协商复杂化的方面 协商包含多重指标，并且这些属性可能互相关联。 多重指标会导致可能的交易空间成指数增加； 协商对象本身有时十分复杂；
参与协商过程的Agent的个数以及这些Agent之间的交互方式也会影响协商的复杂性。 一对一协商 多对一协商 多对多协商 由于这些原因，自动协商过程的多数努力集中在比较简单的情形，主要是单一指标、对称、一对一协商

22 面向任务领域的协商 面向任务领域（TOD）协商是一个三元组<T, Ag, c> T是所有可能任务的（有限）集合
Ag={1,……,n}是参与协商的Agent的（有限）集合 是一个函数，定义了执行每个T的子集的费用，执行任何任务集合的费用是一个正的实数 费用函数必须满足两个约束：必须单调；不做任何事情的费用是0

23 面向任务领域的协商 初始的时候两个Agent分别执行任务 交易 表示Agent1承诺执行任务 Agent2承诺执行任务
交易对于Agenti的效用： 冲突交易：表示Agent不能达成一致情况下必须执行最初分配的任务。表示成

24 优势交易 优势于，记作： 弱优势于，记作：

25 优势交易方面的几点结论 如果没有任何其他交易优势于某个交易，则称这个交易是pareto最优。
如果一个交易不是pareto最优，至少有一个Agent的收益会有所改进，而不会有任何其他Agent遭受损失。 如果交易弱优势于冲突交易，交易称为是个体理性的。如果一个交易不是个体理性的，则至少有一个Agent仅仅通过执行最初分配的任务就可以做得更好。

26 协商策略 1、单调让步协议 协商进行多轮 在第一轮协商中，两个Agent同时从协商集合中提出一项交易。 如果两个Agent提出的交易分别为
使得或者有 或者有 ，则达成一致 如果两个Agent的建议相等或者都超过了其他Agent的建议，则随机选择其中一个建议。 如果不能达成一致，则协商继续进行另一轮，同时提出建议。在第u+1轮，不允许Agent提出比第u轮建议对其他Agent更差的建议。 如果在某一轮u>0，没有Agent做出让步，则协商以冲突交易结束。

27 Zeuthen策略（一） 协商的参与者在使用单调让步协议的时候应该或者如何工作，主要要考虑三个问题： Agent的第一个建议应该是什么？
在给定的一轮协商中，谁应该让步？ 如果一个Agent让步，它应该让步多少？

28 Zeuthen策略（二） 该策略指出：在协商第t轮让步的Agent应是risk较小的 Agent的第一个建议应该是它最希望的交易。
而让步多少只要作出足够的让步即可。 而关于谁应该让步则可以引入冲突风险的概念。直观上，如果一个Agent当前建议的效用与冲突交易的效用差别小，则它更愿意冒冲突的风险。相反，如果一个Agent当前的建议与冲突交易的差别大，则冲突时，这个Agent会遭受更大的损失，因此它更不愿冒冲突风险——更愿意让步。 该策略指出：在协商第t轮让步的Agent应是risk较小的

29 欺骗问题 当Agent相遇时出现不诚实的情况时，会破坏协商进程，这些欺骗行为包括：
虚假任务：假装已经被分配了一个任务，而实际上并没有分配这个任务； 隐瞒任务：在协商过程中为了某些利益隐瞒自己的一些任务。

30 协商集合 Ａ Ｂ Ｃ Ｄ Ｅ Agent j的效用 Agent i的效用 对j冲突交易的效用 对i冲突交易的效用 冲突交易
Ａ Ｂ Ｃ Ｄ Ｅ Agent j的效用 Agent i的效用 对j冲突交易的效用 对i冲突交易的效用 冲突交易 B到C之间的线上的交易是Pareto最优的，因此属于协商集合 这个圆限定了所有可能的交易的空间

31 课堂讨论 选择你熟悉的现实世界中协商的例子（例如购买二手车或房子）。对于这些协商，确定什么代表一个交易，这个交易是单一属性的还是多属性的？它是不是面向任务的协商？是两个Agent还是n个Agent?在这样的领域中什么表示让步？当协商时，使用了特殊的协议吗？规则是什么？ 讨论“单调让步协议和Zeuthen策略”这一协商机制具有哪些性质？（如简洁性、稳定性方面等）