基于不妥协度的Bayes学习协商机制
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于不妥协度的Bayes学习协商机制范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：如何高效地使用Agent学习机制进行在线协商，已经成为经济学家和计算机学者共同研讨的一个主要方向。，为了当协商进入僵持状态时参与协商的买卖双方能确定是否进行妥协，从而使协商继续进行下去，本文在限时条件下的多议题协商中和贝叶斯学习的基础上提出了基于不妥协度的协商策略。实验表明在协商过程中进行学习可以提高对方私有信息的预测精确度，缩短了协商时间，提高了协商效率。
关键词：多Agent协商；不妥协度；贝叶斯学习；在线学习
中图分类号：TP301.6文献标识码：A文章编号：1009-3044(2008)27-2012-02
bayesian Learning Negotiation Mechanism Based on Un-compromising Degree
WANG Juan,WANG Pu
(Department of Computer Science， Henan Administrative Institute of Politics and Law, Zhengzhou450002, China)
Abstract: How to solve the Agent negotiation online learning problem quickly and high-efficently has been a mainstream in both economics and computer science domain. Negotiation strategies based on un-compromising degree is presented on the basis of Bayes learning and in time-limited multi-issues among multi-Agents.The experimental results show that negotiation based on online learning should imporve predictive precision of opponent’s private information, sequentially shorten negotiation time and advance negotiation efficiency.
Key words: multi-agent negotiation;un-compromising degree;Bayes learning;online learning
1 引言
在当前的电子商务应用中，使用Agent系统代替交易方进行谈判和协商成为了一种新的发展方向，它在工业和商业领域的应用范围也在逐步扩大[1]。
在这些系统中，Agent拥有自己的目标或意图，可以自己决定执行动作的目的、时间以及在什么环境下主动自发地做出适当的决策，控制自身的行为。每个Agent都是独立的个体，它们彼此之间并不能仅仅通过简单的指令形式直接控制对方的行为，而只能通过相互之间主动或者被动的信息交换，在一定程度上影响协商环境中其他Agent的行为选择和决策结果[2]。
Iyad Rahwan[3]等人对协商作了以下说明：协商是一组Agent的一种交互形式，这些Agent具有相互冲突的利益但又希望能够合作，在稀缺资源被分散分配的基础上，努力达成双方都能接受的协议。典型的协商决策行为包括评估对方提出的提议、生成新的提议、冲突解决等等[4]。
2 基于不妥协度的协商策略
从本质上讲，协商过程是一个双方不断妥协、放宽限制的过程，参与者都希望用最小的代价获得最大的效用[5]。在协商进行过程中，可能要经过多次的“讨价还价”才能达成最终的协定。
在协商过程中，协商各方都不愿过早暴露自己的私有信息，包括他们的偏好、保留值、协商时限、出价策略等，因而通常双方Agent都具有不完全信息。协商对手的提议是用来了解对手私有信息、效用函数，并更新己方策略的重要信息来源。因此，协商Agent具有在线学习能力是十分重要的。
在每一轮协商中，每一个Agent都会为了最大化自己的利益而讨价还价。当协商进入僵持状态时，参与协商的买卖双方需要确定是否进行妥协，从而使协商继续进行下去。
如果一个Agent已经做出了一定的妥协，它不再妥协产生的损失会相对小一些，因此它会冒着产生冲突的危险而选择不妥协；相反，如果一个Agent从未做出过妥协，它不再妥协就会造成比较大的损失，它更情愿避免产生冲突而做出妥协。这里用不妥协度来衡量Agent是否应该做出妥协，如果Agent的不妥协度比较小，它将选择妥协，反之它将选择不妥协。
定义1（议题向量）V ：一个向量集合，?坌ai∈G，?坌t，0≤t≤k，其中k表示协商中的交互次数， V(ai,t,Xi)=表示Agent个体ai第t次提出的议题向量，向量中元素v(ai,t,xm)表示议题xm的值。
定义2（不妥协度）一个Agent在第k轮协商中的不妥协度NCik可以用下式表达：
其中：Hkaa表示Agent a在以自己的理想价格为成交价格时的收益；Hkab表示Agent a妥协时的收益； Hka表示Agent a不妥协时获得的收益。
在每一轮协商中，每一个Agent都要计算自己的不妥协度NCik，并估算协商对手的不妥协度。对于Agent a来说，如果NCak>NCbk，则Agent a不妥协产生的损失比Agent b不妥协产生的损失小，因此Agent a会采取不妥协的策略。通常Agent a在第k轮协商中选择妥协后，则在下一轮（第k+1轮）协商中应使：
这是因为Agent a选择妥协时，其妥协的目的是使Agent a在下一步不再妥协，而要Agent b在下一步选择妥协，即：NCak+1>NCbK+1，所以在Agent a采取妥协之后应使，才具有实际意义。
3 Bayes学习协商机制
在协商的开始阶段，每一个Agent都拥有对手的信念，它可以由Agent进行假设，也可以是以往交易的历史信息。在每一轮协商中，当一个Agent收到协商对手的协商提议时，它分析这个提议，通过Bayes学习获取协商对手信息来修正对协商对手的信念，然后根据协商对手现在的信念提出下一轮的协商提议或接受对方的协商提议。即使协商初始阶段Agent关于协商对手的信念不准确，在经过若干轮修正之后，Agent关于对手的信念会变得相对准确。
Bayes学习协商机制贯穿于整个协商过程中。Bayes学习机制的引入，使协商过程不至于在一些无关紧要的冲突点终止，而且尽管为获取对手信念付出一定代价，但双方的这种努力能在一定程度上能促使协商取得成功，保证了模型的收敛性。
4 协商算法
从Agent a的角度出发的基于Bayes学习的协商算法描述如下：
1）k=1，设置关于Agent b的信念，它包括Agent b的效用函数、保留值以及出价概率等；
2）Agent a按照协商策略给出提议vaxi，同时Agent a也会收到Agent b的提议vbxi ；
3）Agent a对b的提议vbxi进行评估，如果对方提议能满足自己的期望，转步骤6；否则对Agent b的提议进行Bayes学习，更新对Agent b的信念。
4）如果k=kmax，转步骤7，否则k++；
5）计算Agent a是否决定妥协，同时提出新的提议va'xi，Agent a也会收到Agent b的提议vb'xi，转步骤3；
6）Agent a向Agent b发出同意接受提议，协商成功，协商结束。
7）协商次数超过最大允许协商次数，协商失败，协商结束。
5 实验结果
为了简化整个讨论，限定整个协商议题只有一个――任务执行的价格，即对手的保留价格。协商双方的保留价格是买卖双方对商品的价值或成本的估计值，在协商之前就已经确定，并在整个协商过程中保持恒定。协商开始时参与者对最后成交价进行预测并根据该预测确定协商策略函数。
我们从买方Agent a的观点出发进行了实验。由于在Agent协商过程中可能涉及到的商品种类繁多，价格也千差万别，且用户通过MAS系统协商某一种商品的可能性也不固定，它随着用户具体应用的变化而变化。所以实验中我们从电子商务网站随机选取某一时段的几种商品数据，整理成规范的格式后作为算法的输入数据。
Agent a向Agent b购买商品一件，该商品在市场上的单价一般为900元，成交价格大都介于700元和1200元之间。
假定Agent a的保留价为1100元，理想价格为700元；Agent b的保留价为800元，理想价格为1100元。用线形函数作为Agent a和Agent b的效用函数：u=ax+b 。
假定Agent b的保留价格概率如表1所示：
表1 Agent b的保留价格概率表
■
实验结果如下：
■
图1协商中双方出价轨迹图 图2Agent a关于其对手的保留值信念变化图
从图1可以看出，Agent a和Agent b一直在朝着达成协议的方向前进，并收敛于某一个接受协商提议的协商点；从图2可以看出Agent a对协商对手的保留价信念在经过一定次数的协商之后逐渐稳定下来，在协商过程中能比较精
确的预测出对方的保留价，反映了Bayes学习机制的特点。
6 结束语
Agent通过学习协调自身的行为，可以使协商双方在不降低整体效用的前提下交互次数尽量减少，缩短了协商时间，提高了协商效率。为了实现利益最大化和避免协商僵局，本文在贝叶斯学习的基础上提出了基于不妥协度的协商策略，使得在每一轮协商中
每一个Agent都会尽量最大化自己的利益，且协商过程不至于在一些无关紧要的冲突点终止。实验已说明具有学习机制的协商Agent可以提高对对方私有信息的预测精确度，从而缩短协商时间，提高协商效率，并在一定程度上保证了模型的收敛性。
参考文献：
[1] P. Fatatin,C. Sierra and N.R. Jennings, Using Similarity Criteria to Make Negotiation Trade-Offs,Proceeding Fourth International Conference on Multi-Agent Systems,IEEE Computer Soc,pages 89-95, 2000.
[2] S.Fatima and M.Wooldridge and N.R. Jennings, Multi-issue negotiation under time constraints. In Proceedings of the First International Joint Conference on Autonomous Agents and Multi-Agent Systems, Bologna, Italy, 2002 pp. 46-65.
[3] Rosenschein J S,Zlotkin.Rules of Encounter. Design Conventions for Automated Negotiation Among Computers.Cambridge MA:MIT Press, 1994.
[4] Xudong Luo,N.R. Jennings and Nigel Shadbolt,A Fuzzy Constraint Based Knowledge Model for Bilateral, Multi-Issue Negotiations in Competitive Environments, Artificial Intelligence,To appera,2003.
[5] Alessio Lonmuscio,Michael Wooldridge, and Nicholas Jennings. A classification scheme for negotiation in electronic commerce. International Journal of Group Decision and Negotiation, 2003, 12(1):31-56.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”