（计算机软件与理论专业论文）一种多阶段相互协作的自动谈判模型及其实现.pdf

一种多阶段相互协作的臼动谈判模型及j 实现 摘要 摘要 谈判是多方展开商务合作、进行业务往来过程中一个必不可少且十分重要的 环节。自动谈判的研究吸引了来自学术界以及业界等多方面的注意力。自动谈判 的机制可以通过利用计算机的计算能力，来模拟人之问相互谈判的过程来实现。 本文针对b 2 b 、招投标等电子商务环境，提出了一种多阶段相互协作的自动 谈判模型。该模型采用了一种相互演化的谈判策略，一种复杂的谈判协议以及一 种基于博弈论的谈判方法，目标是更合理地分配最后所得到的谈判结果。本文所 做的研究试图解决在无限大且无比复杂的问题空白j 中，有效地找出对参与谈判的 各方都有利的谈判结果这一问题。本文所提出的模型，是基于一种特殊的博弈论 方法( t t p 算法) 和启发式算法，使用这个模型，能够通过一系列多阶段迭代的 过程，细化和探索可能的谈判结果。我们不仅实现了该谈判模型，而且还开发了 一款多模型驱动的开发建模平台，以便将该谈判模型应用到实际的电子商务环境 中去。在本文最后，我们还通过实验，来分析所提出的多阶段相互协作的自动谈 判模型的性能。除了进行谈判所使用的时间，另外两个关键标准总效用以及 谈判双方满意度的差值被用来衡量所提出的谈判模型的有效性。实验结果表 明，如果多阶段谈判使用更少的后代层次以及更小的种群规模，那么比起使用更 多后代层次和更多种群规模的单阶段谈判，在处理时间上更短，但所产生的谈判 结果却相差无几。 关键词：自动谈判，博弈论，基因算法，面向服务，智能代理 i n 一种多阶段相互协作的自动谈判模型厦j 实现a b s t r a c t a b s t r a c t n e g o t i a t i o ni s a l l i m p o r t a n ta s p e c t o f c o l l a b o r a t i n ga n dc o n d u c t i n g b u s i n e s s e sw h e r em u l t i p a r t yi n t e r a c t i o ni si n v o l v e d f o rt h el a s tf e wy e a r s ，a n a u t o m a t e dn e g o t i a t i o nh a sa t t r a c t e da t t e n t i o nf r o mb o t hr e s e a r c hc o m m u n i t i e s a n di n d u s t r y a na u t o m a t e dn e g o t i a t i o nm e c h a n i s mc a nb eb u i l ti nac o m p u t i n g e n v i r o n m e n tb ys i m u l a t i n gh u m a nn e g o t i a t i o np r o c e s s 1 1 l i s p a p e rp r o p o s e sam u l t i p l e - s t a g eb i l a t e r a la u t o m a t e dn e g o t i a t i o n m e c h a n i s m ，i n c l u d i n gac o - e v o l u t i o n a r yn e g o t i a t i o ns t r a t e g y , as o p h i s t i c a t e d n e g o t i a t i o np r o t o c o la n d a g a m e - t h e o r e t i cn e g o t i a t i o nm e t h o dw h i c hi su t i l i z e d “) d i s t r i b u t et h ep a y o f f s t h ep r o p o s e dm e c h a n i s mi si n t e n d e dt oa d d r e s st h es e a r c h f o rj o i n te f f i c i e n c yo fa l li n v o l v e dn e g o t i a t i n gp a r t i e si n l a r g ea n dc o m p l e x p r o b l e ms p a c e s u s i n gt h i ss t r u c t u r ei ti sp o s s i b l et or e f m ea n de x p l o r ep o t e n t i a l a g r e e m e n t st h r o u i g ha ni t e r a t e dp r o c e s s n ep r o p o s e da u t o m a t e dn e g o t i a t i o n a p p r o a c hi sb a s e do nas p e c i f i cg a m et h e o r ym e t h o da n dah e u r i s t i ca p p r o a c h w ea l s or e p o r tas e r i e so ft h ee x p e r i m e n t st h a th a v eb e e nc a r r i e do u tt oa n a l y z e t h ep e r f o r m a n c eo ft h ep r o p o s e dm u l t i s t a g eb i l a t e r a ln e g o t i a t i o nm e c h a n i s m a p a r tf r o mt h ee f f i c i e n c yo fp r o c e s s i n gt i m e ，t w ok e yc r i t e r i a , i o i n tt o t a lu t i l i t y a n dt h ed i f f e f e n c eb e t w e e nt h ea g e n t s d e g r e e so fs a t i s f a c t i o n , w e r es e l e c t e dt o m e a s u r et h ee f f e c t i v e n e s so ft h ep r o p o s e dn e g o t i a t i o nm e c h a n i s m k e y w o r d s ：a u t o m a t e dn e g o t i a t i o n ，g a m et h e o r y ，g e n e t i ca l g o r i t h m ， s e r v i c eo r i e n t e d ，a g e n t i v 论文独创性声明 本论文足我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，1 i 包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的肩发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：缈日期：兰盟5 ： 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：盎盔叁导师签名 同期 一种多阶段相互协作的自动谈判模型及】e 实现第一章绪论 1 1 研究背景与意义 第一章绪论 随着信息技术和通信技术的发展，电子商务( e l e c t r o n i cc o m m e r c e ，e c ) 已 经成为未来信息社会商务活动的主要形式。目前，商务活动的许多环节都已电子 化，如采购、销售、支付等，但谈判仍然在网下进行。电子商务网站仅能提供静 态的电子目录。商品和服务的价格等条款通常都是事先设定的，不允许修改或不 提供协商的方式。随着电子商务的发展与全球化，企业间的交易将占主导地位， 商务谈判也将愈加频繁，如何实现整个交易过程的电子化，实现异地远程商务谈 判的自动化与决策支持，已成为完善电子商务功能、推动电子商务发展所追切需 要解决的问题。 谈判是人们为了改变相互关系而交换意见，为了取得一致而相互磋商的一种 行为，也是谈判各方针对各自利害攸关的事项进行协调，并取得协议的过程。据 专家预测，未来几年智能电子商务系统将是业界关注的焦点。增加了对自动谈判 过程支持的电子商务系统，会因为其灵活性而必然极大地推动电子商务的产业化 和商品化发展，提高其市场竞争力。 目前，支持网上谈判的应用系统主要涉及谈判支持系统( n e g o t i a t i o ns u p p o r t s y s t e m s ，n s s ) 、拍卖( a u c t i o n ) 系统和自动谈判( a u t o m a t e dn e g o t i a t i o n ，a n s ) 系统【2 ，3 ，4 6 , 7 。n s s 同自动谈判系统的主要区别在于：n s s 是提供各种建模能 力、群体分析技术等方法辅助支持谈判人谈判的计算机软件，主要目的提高谈判 效果、促使谈判成功；而自动谈判系统( a n s ) 则是采用谈判软件a g e n t ( n e g o t i a t i n gs o f t w a r ea g e n t ，n s a ) 部分或完全代替人同其它谈判方( a g e n t 或 人) 谈判，主要目的是提高谈判效率、降低成本；拍卖系统可以看作是一种简单 的自动谈判系统。 谈判支持系统主要是针对网上商品或服务买卖提供谈判支持，促进交易达 成，而面向电子商务的自动谈判，则是立足于企业之间的动态合作和自动化业务 流程处理，着眼于未来电子商务的发展，因此更具有的前瞻性和研究价值。自动 谈判系统由于利用智能代理软件a g e n t 部分或完全代替人进行网上谈判，因此 能够极大地提高谈判效率，降低采购和销售成本。同时，多a g e n t 系统技术是近 年来分布式人工智能领域研讨的热点。将先进的多a g e n t 系统技术限定在一个具 体的应用领域进行研究，既可以丰富其学术价值，又能很好地解决实际问题。多 a g e n t 系统技术和电子商务领域的结合正是这样的一个尝试，在未来电子商务发 第1 页共5 1 页 一种多阶段相且协作的自动淡判模型及j t 实现 第一帝绪论 展中将具有非常重要的作用。 本文将多a g e n t 协商的理论研究，放在了电子商务的应用背景下，探讨了在 基于a g e n t 的电子商务中加入对自动谈判机制的支持这个最新热点问题，对多 a g e n t 协商理论在基于a g e n t 的电子商务中的应用研究具有指导意义。 1 2 研究内容与创新 传统商业交易需要消费者或企业与公司之间对买卖商品( 或服务) 的价格、 交货时间、质量等交易问题进行谈判【l j 。i n t e r a c t 的快速发展使得在线商店和b 2 b 电子商务迅速成为有吸引力的选择。电子商务的本质在于降低成本。为了提高效 率、缩短交易时间，需要在电子商务系统中实现对自动谈判机制的支持。 由于软件a g e n t 具有自治、分布、适应、灵活、开放、动态等特点，我们采 用基于a g e m 的方法。然后，在多a g e n t 系统研究的基础上，结合对现有系统和 方法的优缺点分析，本研究提出一种应用于电子商务多问题自动谈判的形式化模 型，该模型设计并实现了一种多阶段相互协作的自动谈判系统。 理论研究表明，具备随经验积累而自动提高性能能力的系统更具有吸引力， 将机器学习理论的研究成果运用于更多的领域，将会极大地推动机器学习在理论 方面的研究发展。如果在谈判的多a g e n t 系统中引入学习机制，使得每个a g e n t 通过学习优化自身的谈判行为和谈判策略，则能有效地提高谈判的效用，使得自 动谈判过程能够适应环境的动态变化。 在我们的自动谈判系统中，a g e n t 通过基因的方式描述各自的谈判策略、谈 判提议( o f f e r ) ，从而能够实现多阶段的不断优化的谈判机制，增强了自动谈判 的灵活性和实用性，并对动态环境下的a g e n t 强化学习研究有一定的参考价值。 本文讨论了基于a g e n t 的电子商务中的双边多问题自动谈判。谈判过程由动 态的买、卖a g e n t 执行，试图找到对双方都有利的最佳谈判结果。文章重点考虑 的是自动谈判过程中的学习优化问题，目的是使得谈判达到最优解，并且该谈判 结果必须是平衡的、稳定的。首先给出了谈判结果的评价标准，定义和分析了怎 样的谈判结果是有质量的谈判结果。其次，给出了谈判协议以及进行一个阶段谈 判流程的详细描述。在此基础上，结合博弈论和柏拉图均衡理论，提出了应用于 第一阶段谈判结果的分配算法，从而是调整后的谈判结果是稳定均衡的。然后， 在这个基础上，加入了基于基因算法的学习机制，用基因描述谈判双方各自的谈 判策略以及谈判要素，从而得出了适合于电子商务环境下的多问题多阶段相互协 作的自动谈判形式化模型。论文还在一对一的自动谈判中探讨了不同变量因子对 第2 页共5 1 页 一种多阶段相互协作的自动谈判模型及j e 实现第一章绪论 谈判性能和效用的影响，并进行了实验测试和分析。最后，本文还实现一个针对 该谈判模型的多模型驱动的建模环境，从而能够有助于将该谈判模型应用到实际 的电子商务环境中去【3 2 j 1 3 3 j 【蚓【3 5 1 。 本文的创新之处主要体现在以下几个方面： 1 将多a g e n t 系统和机器学习的理论研究较好地运用于电子商务自动谈判 的实现中，更好地体现了系统的智能性，增强了灵活性和实用性。 2 结合基因算法和启发式方法等理论，提出了自动谈判的形式化模型，使 谈判参与者具有学习更新能力。 3 采用纳什平衡和柏拉图平衡等理论对谈判结果进行评估。 4 在传统的基因算法得到初步的谈判结果的基础上，结合博弈论的原理， 设计了t r u s t e dt h i r dp a r t y 算法，对谈判结果进行重新的分配，从而充实 了简单的谈判迭代模型。 5 对谈判模型中的不同可变因子进行研究，分析了他们对于谈判性能以及 谈判效用的影响。 6 基于所提出的模型，设计并实现了一种多模型驱动的开发平台，从而可 以有助于将所提出的模型应用到真实的电子商务环境中去。 1 3 内容安排 本文提出了一种多阶段相互协作的自动谈判模型，该构架包括了一种相互演 化的谈判策略，一种复杂的谈判协议以及一种基于博弈论的谈判方法，它可以被 用来更合理地分配最后所得到的谈判结果。本文所做的研究试图解决在无限大且 无比复杂的问题空间中，有效地找出对参与谈判的各方都有利的谈判结果这一问 题。本文所提出的模型，是基于一种特殊的博弈论方法和一种启发式的算法，使 用这个模型，能够通过一系列迭代的过程，细化和探索可能的谈判结果。具体章 节安排如下： 第一章绪论整体概括了研究背景、研究内容、主要创新及整篇文章的布局。 第二章对自动谈判的现有成果进行介绍，并且讨论当前影响自动谈判效率 和有效性的三个问题：谈判质量、谈判流程以及在多要素场景中的效用函数问题。 第三章阐述博弈论、启发式算法等理论在该模型中的作用，并且详细介绍 了所提出的多阶段相互协作的自动谈判模型。 第3 页共5 1 页 一种多阶段相互协f f 的自动谈判模型及其实现 第一章绪论 第四章详细介绍了基于所提出的多阶段相互协作自动谈判模型的原型系统 实现，介绍所开发的多模型驱动开发建模平台。 第五章分析该模型中不同变量因子对谈判性能和效用的影响。 第六章对全文的工作进行了回顾并分析了本文的更多应用。 第4 页共5 1 页 一种多阶段相互协作的自动谈判模型及j e 实现第一二章自动淡判综述 第二章自动谈判综述 所谓交易中的谈判，就是一个决定交易重要因素的过程，这些因素包括：商 品价格、商品数量、交货时间、交货方式等。根据市场的不同，谈判过程和复杂 度也有所不同。在一些传统的零售市场，价格和其他一些因素都是固定下来的， 那么也就没有谈判的空问了。但是，也有很多市场，比如：股票市场、拍卖市场 或者跳蚤市场等，谈判是交易过程中最关键的部分。 同样，在电子商务交易中，谈判过程也是一个重要的组成部分。它相对于零 售市场的交易有以下优越性：首先，它顺应了网上商品日趋丰富的特点。随着网 上商品供应商的增多，很多商品难以估价，所以由市场调节的方式确定价格是最 公平合理的；第二，谈判的自动化使谈判过程不需要人员干预，加快了协商的进 程，降低了协商的成本；第三，正因为协商不需要人的特殊干预，不论商家还是 买家都更喜欢这种由市场决定价格的方式，对于商家来说，加入市场的门槛放低 了，他只需要在网上发布商品的信息，就可以参与交易；对于购买者来说，这种 交易方式意味着他有更多机会选择和买到便宜的商品；第四，由市场谈判来决定 商品的分配是一种更合理的分配方式，它使商品更容易实现它合适的价值，并被 需要它的人所拥有；第五，随着协商技术的发展，谈判对象将不再停留在价格上， 谈判对象将逐渐发展成一个价格、数量、分配方式、售后服务等多因素的综合体， 将更好的满足用户的需要。 随着i n t e m e t 的发展，越来越多的公司、企业和消费者加入到电子商务交易 中。在电子商务交易中，公司以电子化方式从消费者或者企业接受购物订单，提 供商品或服务，接收付款。通常，传统商业交易需要消费者或企业对买卖商品或 服务的价格、交货时间、质量等交易条件进行谈判。为了节省买卖双方交易中大 量的工作和时自j ，提高交易效率和降低交易成本，有必要实现电子商务交易的自 动或半自动化谈判。 因此，发展和探索自动谈判技术成为一个热点。j e n n i n g s 曾说过，自动谈判 将成为下一代电子商务应用的标志。本章中，将首先分析国内外相关领域的研究 现状，然后，将主要讨论当前影响自动谈判效率和有效性的三个问题：谈判质量、 谈判流程以及在多要素场景中的效用函数问题，他们是设计任何谈判模型之前必 须需要解决的三个问题。 2 1 自动谈判 谈判是商业贸易交往中的重要环节，随着电子商务技术的快速发展，基于 第5 页共5 1 页 一种多阶段相互协作的自动谈判模型及其实现第二章自动谈判综述 i n t e r n e t 的自动谈判已成为实际需要，现有许多相关工作从不同角度对谈判和谈 判支持系统进行了研究【3 0 j 。 从制定决策的角度看，自动谈判是由一系列决策行为构成的。自动谈判的参 与者可以有两方或更多方，他们之间交互以求达成一致，尽可能在最后的协议中 获得最大利益。典型的谈判决策行为包括评估对方提出的方案、生成新的方案、 冲突解决( 为减小参与者所提方案之间的差距而提出折中方案) 等等。 在实际的商务谈判中，买卖双方的利益是冲突的，并试图隐藏各自的私有信 息，他们之间是竞争关系；但双方可能为了达成较好的交易，并能为以后更好地 合作打基础，也会相互妥协让步，因而在一定程度上优势合作的。 2 1 1 相关概念 1 谈判战略 谈判战略就是对谈判的预计过程有整体的观念( 不同于战术阶段) ，规定需 要实现的各项目标( 可有偏重，不一定都作刻板的划分) ，并根据这些预期达到 的目标来组织行为。其过程为：谈判战略的分析。 谈判战略的抉择 谈判的准备 3 q 2 谈判战术 谈判战术又称为策略、技巧等，是谈判者为表达自己的愿望、说服对方而采 用的具体方式和方澍3 。 2 1 2 谈判质量 自动谈判的质量可以通过两种方法来进行评估：客观的评估方法和主观的评 估方法。目前，已经有许多知名的客观评估方法，能够对谈判结果进行评估。这 些客观评估方法要求参与谈判的每一方都了解各自可能接受的所有谈判结果的 效用刚。 这里涉及到两个重要的概念：柏拉图效率( p a r e t oe f f i c i e n c y ) 和均衡的概念 i j 。如果当再也找不出一种能够在提高一个谈判参与者的谈判回报同时，又不 损害另一个谈判参与者的谈判回报的方法时，那么便可以说这个谈判结果是满足 柏拉图效率的。在只有两个参与者参与的谈判场景中，客观视图可以被绘制成一 个二维坐标图，其中横轴和竖轴分别表示两个谈判参与者所能得到的谈判回报。 达到柏拉图效率的点，在图中就是那些在象限里其右侧和上方再也无法找到其他 第6 页共5 l 页 种多阶段相互协作的自动谈判模型及j e 实现第一二章自动谈判综述 交点的点。而均衡的概念，是指任何一个谈判参与者都无法提高他的回报，除非 其他谈判参与者改变他们的谈判结果。客观评估方法能够验证谈判结果是否达到 均衡的情况。在理想状况下，谈判的结果应是均衡的，且是达到柏拉图效率的。 主观评估方法对谈判结果的评估结果将不用于客观评估方法对谈判结果的 评估，如果存在信息不完全的情况。例如：谈判参与者a ，能够知道摆在他面前 的谈判选项，以及知道摆在其他谈判参与者( b ，c ) 面前的谈判选项。而 对a 的谈判回报只有a 是清楚的，但是对于b ，c ，他们是无法知道对a 的谈 判回报。在这种情况下，对参与谈判的任何一方，都无法知道所达成的谈判结果 是否是满足柏拉图效率的，并且也无法知道谈判结果是否满足客观上的均衡状 态。这样所造成的结果便是，谈判很可能将无法达到最优的谈判结果。因此，结 论便是，在不提供完整信息的情况下，如果谈判流程只允许谈判参与者之间交换 部分偏好的信息，那么很有可能最终达成的谈判结果是次优的，而不是最优的。 2 1 3 谈判流程 进行谈判的上下文环境将决定谈判参与者所能够做出的谈判选项。谈判参与 者进行通信的渠道，以及所允许的谈判协议( p r o t o c 0 1 ) 将限制谈判参与者所能 采取的谈判策略以及最终的谈判结果。在提出任何一种谈判模型之前，必须首先 定义谈判上下文环境的范围。这个定义好的上下文必须能够支持足够多的信息交 换，这样才能使谈判过程成为一个可以不断改进的过程，最终使谈判可能到达一 个最优的谈判结果i 叫。 在定义谈判上下文方面有一个关键的问题，那就是如何定义可选的谈判策 略。可以这样理解，选择谈判策略就是选择如何解决最大化个体所得和最大化群 体效益的矛盾。谈判参与者也许会做出适当的让步，从而能够提高群体的共同边 际效用。每个谈判参与者都有他们各自私有的谈判策略，来分析当前的谈判局势。 因此，假设有一种谈判上下文，它允许谈判各方提出谈判提议( o f f e r ) ，并且回 复回应谈判提议( c o u n t e ro f f e r ) ，那么，这些谈判提议和回应谈判提议就必须 在谈判的过程中生成。所以，关键问题是需要设计出一种谈判策略，能够使自动 谈判朝最优谈判结果的方向发展。 2 1 4 多要素场景中的效用函数 有些类型的自动谈判是针对一个一个单一的谈判要素的，因此，必须对每一 个单独的谈判要素使用效用函数进行计算。但是，在有些场景中，一个效用函数 必须能够计算一组独立的谈判要素。比如，在一个供应链的场景中，谈判各方经 第7 页共5 1 页 一种多阶段相互协作的自动谈判模型及】t 实现 第二章自动谈判综述 常就三个要素进行谈判：商品价格，商品质量以及交货开期。并且，与这些谈判 变量相关联的成本或者收益也会成为其他内在的相关谈判变量。类似这样的谈判 就必须在其谈判策略中考虑到所有这些可变要素。这样的话，简单的对单一要素 的谈判就无法满足这样的需求。当然，有些复杂的单一要素的谈判形式也许可以 解决这类问题。不论怎样，基于这种需求的考虑，必须在设计谈判上下文和谈判 策略时支持多要素的谈判场景，以及设计出适当的效用函数。 2 2 自动谈判的国内外研究现状 2 3 1 目前研究中所采用的理论方法 1 对策论 这个领域最主要的研究者是r o s e n s c h e i n 和z l o t k i n ，他们使用对策论工具解 决在一组没有预先植入明确合作机制的理性和自动a g e n t 之间的合作问题。在应 用对策论的谈判系统中，买卖双方a g e n t 交换提议，尽量使各自的当前总的效用 和最大。隐含的假设是每个a g e n t 能最佳计算期望的效用。a g e n t 根据自己的谈 判策略评估对方的提议。 对策论研究成果只是针对简单对策环境且只在严格的假设条件下成立。该模 型假设a g e n t 在交互过程中能够完全观测到其他a g e n t 所采取的行动，而在实际 应用中，由于环境的动态性以及动作的随机性，该假设条件通常是不成立的j j “。 本研究所提出的模型中，也引入了部分对策论的方法。但是，我们并不假设所有 a g e n t 是全知的，每个a g e n t 只能知道各自的效益矩阵( p a y o f fm a t r i x ) 、以及 其他a g e n t 的满意度( 而不是偏好) 等，除此以外，各a g e n t 不会知道其他a g e n t 的任何信息。 2 拍卖 经济学家普遍认为拍卖是解决“一对多”计价问题的最有效方法。有四种基 本的拍卖类型：英式拍卖、荷兰式拍卖、密封递价最高价拍卖、维式拍卖。i n t e m e t 上有一些在线拍卖的网站，如a u c t i o n b o t ，e b a y ，e - t r a d e ，以及y a h o o 等。理 论上，拍卖各方都可以通过数学计算来找到最佳策略，但该理论结果不是总适用 于实际操作；拍卖机制可以对具有不确定性和模糊信息的议价建模，但总带有简 化问题的假设。拍卖的谈判方式受限于某些特定类型的产品，一般只是对单问题 ( 价格) 的谈判，并且议价方式不够灵活，有的拍卖类型不能动态修改投标值【3 。 3 多属性效用理论 第8 页共5 1 页 一种多阶段相互协作的自动淡判模型及j e 实现 第一二章自动谈判综述 该理论可以用来处理多边多问题自动谈判，尤其在客户具有模糊偏好时，可 以根据客户不同的偏好来评估接收到的提议。对于线性计分函数( s c o r i n g f u n c t i o n ) ，一般能找到“最佳交易”的最优点；对非线性计分函数，求最优点的 数学分析常常很困难。该理论也可以对模糊和不确定信息的议价问题建模，但如 何构建谈判策略却没有一个较好的一般解决方案i j ”。本研究所提出的模型同样 需要解决多属性效用问题，与“多属性效用理论”不同的是，我们采用了启发式 算法来解决非线性函数的最优点问题。 4 扩展合同网协议模型 在经典合同网协议( c o n t r a c tn e tp r o t o c 0 1 ) 的方法中，契约方在表达合作意 愿后只被允许与管理者进行一次通信。通过扩展合同网协议，定义交互规则( 谈 判协议) 谁何时能做什么，来保证谈判过程的正常执行，同时也允许不断重 复的提议和反提议序列。个体a g e n t 依据谈判协议，能够表示和推理内在的和外 在的环境和交换i ，“。 5 模糊逻辑 模糊逻辑具有良好的表述不确定环境下的问题的能力。采用该理论的谈判模 型，通常使用效用理论和受限的模糊推理技术，来支持在a g e n t 具有有限领域知 识和不确定信息的情况下的多问题自动谈判。它将谈判过程看作一个重复的决策 生成过程，包括评估提议、放松偏好和限制等，期望能找到满足所有限制、偏好 和目标的谈判结果。模糊逻辑方法能够表示完全动态的谈判过程【j ”。 2 3 2 现有自动谈判系统中的机器学习方法 在自动谈判系统中引入学习机制是最近几年研究的新主题。现有自动谈判系 统中涉及到的机器学习方法有以下几种： 1 贝叶斯学习 z e n g 等人基于对自动谈判过程中a g e n t 学习的重要性的认识设计了谈判模 型b a z a a r ，这是一个基于连续决策过程的谈判模型，其目的在于支持a g e n t 在谈 判过程中的学习。b a z a a r 支持贝叶斯学习，a g e n t 能够在交互过程中对知识进行 更新，从而选择收益较大的策略。由于学习机制的引入，b a z a a r 模型中的a g e n t 较其他没有学习能力的a g e n t 具有更强的谈判能力，但b a z a a r 模型中的学习是 对静态环境下a g e n t 谈判过程的学习，由于缺少不同环境状态间的关联信息，该 模型不适于描述动态环境中的谈判问题p “。 第9 页共5 1 页 一种多阶段相互协作的自动谈判模型及，e 实现 第二章自动淡判综述 2 遗传算法 它把自动谈判过程看作一个在谈判空间( 由谈判问题和可能的解组成) 中搜 索的最优化问题，并且是一个动念的搜索过程。通过给定a g e n t 的效用函数，来 寻找最佳的谈判结果。学习过程还包括在整个谈判策略空臼j 中搜索最适当的谋略 参数。h a y n e s a n d s e n 采用一种扩展的基因编程强标汜基因编程( s t g p ) ，将 多a g e n t 的策略编码成符号表达式和一个估计准则，通过适应度函数逐步增加协 调策略的效率。采用遗传算法的一个缺点是由于a g e n t 自身行为知识以及策略过 于复杂，使得在实际应用中无法进行更有效的遗传编码；另外研究者发现由于 a g e n t 间缺乏明显的和足够的通信，采用遗传算法的多a g e n t 策略不能成功地应 用于竞争进化领域l j ”。本研究所提出的模型中选用了遗传算法作为谈判的学习 机制，与h a y n e s a n d s e n 不同的是，我们为a g e n t 提供了足够的通信，另外，还 解决了策略编码复杂的问题，从而使得该模型能够被应用到实际的电子商务场景 中。 3 强化学习 o l i v e r i a 和r o c h a 设计了一个虚拟市场，采用强化学习方法生成提议。它使 用了传统的q 学习算法，但没有考虑学习环境的动态变化。 2 3 a g e n t 在自动谈判中的应用 在自动谈判中，a g e m 技术主要有以下几种应用方式【3 1 】： 1 a u c t i o n b o t 一个通用的在线拍卖服务器。用户通过选择不同的参数来选择不同的拍 卖类型，买卖双方根据所选拍卖类型的多边分布协议来投标。在a u c t i o n b o t 的 市场中，卖主在选择了一个预留价格以后对拍卖进行初始化，然后让a u c t i o n b o t 依据拍卖协议以及参数来管理投标。1 3 1 】。 一个基于i n t e m e t 的多a g e n t 议价系统，买卖双方各维护一个软件a g e n t 进 行交易。k a s b a h 的a g e n t 没有使用任伊人工智能或机器学习的技术。在卖主创 建新的卖方a g e n t 时，他将建立几个引导参数，包括卖掉该商品的最后期限、期 望的成交价格、最低可接受的价格。k a s b a h 使用一个议价策略函数引导a g e n t 在谈判过程中议价。系统有三个基本的定价函数：线性函数，二次寒霜，立方函 数，分别代表急切的、沉着的和贪婪的议价态度j 。 第1 0 页共5 1 页 一种多阶段相互枷作的自动谈判模型及j 七实现 第三章多阶段相互协作的自动谈判模型 3 1 e t e a 1 e t e 一个多问题自动谈判系统，买卖双方a g e n t 在交易中通过谈判来合作。它支 持对多个交易问题的谈判，诸如价格、保障、送货时间、优惠政策以及其他一些 增值商业服务。t e t e a - t e t e 中的买方a g e n t 和卖方a g e n t 争辩地谈判，并使用在 产品选择和商业代理阶段生成的评估限制作为多属性效用的维度【3 1 1 。 4 e m e d i a t o r 下一代电子商务服务器，它使用增强了的m 和算法技术、对策论以及g u i 设计。e m e d i a t o r 中有两类a g e n t ：e a u t i o n h o u s e ，一个可以通过定制不同参数 来配置不同拍卖类型的拍卖屋，以及e c o m m i t t e r ，一个平衡的义务合同最优化选 择器【3 1 】。 5 a d e p t 一个针对电信服务行业的系统。a d e p t 定义了一个面向服务的谈判模型， 并在以后的工作中对其进行了改进，对a g e n t 的谈判结构增加了相对复杂的思考 机制，用于决定提议的内容，它不支持谈判过程中问题的变更【3 1 1 。 6 l i a n g 和d o o n g 的电子市场原型实验系统 主要用来研究议价是如何吸引顾客的，以及当谈判策略有效时，个体差异是 如何影响议价结果的。这个电子市场由几个小商品店组成，其中一些商品提供议 价功甜“j 。系统使用三种议价策略： 1 ) 效用递减策略。在初始出价时给出很大的折扣，以后逐步减少让步，买方 感觉到效用在逐渐减少。 效用递增策略。在初始出价时给出比较小的折扣，以后逐渐增加让步。 3 1 效用均衡策略。始终用不变的价格折扣，买方感觉到不变的效用。 第1 1 页共5 1 页 一种多阶段相互协作的自动谈判模型发其实现第三章多阶段相互协作的自动谈判模型 第三章多阶段相互协作的自动谈判模型 本章中，首先描述博弈论以及自动谈判的需求。然后，详细介绍了启发式方 法，包括贝叶斯学习( b a y e s i a nl e a r n i n g ) ，q 一学习( q - l e a r n i n g ) 和遗传算法。接 着，将提出一种特殊的博弈论算法。最后将介绍本研究所提出的自动谈判模型。 3 1 博弈论与自动谈判模型 博弈论( g a m et h e o r y ) ，又称为对策论，或者赛局理论，应用数学的一个分 支，是使用严谨的数学模型研究冲突对抗条件下最优决策问题的理论。博弈论主 要研究公式化了的激励结构( 游戏或者博弈) 问的相互作用，是研究具有斗争或 竞争性质现象的数学理论和方法，也是运筹学的一个重要学科。 博弈论1 5 , 1 1 , 1 2 能够解决自动谈判中的许多问题。在本节中，我们将简要谈论 与此相关的几个方面问题。 我们知道，博弈论是经济学的一个分支，它研究的是经济体之问的策略交互 行为【l 。经典的博弈游戏是以数学模型的形式诞生的弘u j 。而其中，纳什博弈只 处理单一要素，并且，其效用函数是公开的，属于完全信息博弈的类型。它所达 到的均衡能够满足唯一性，柏拉图效率，对称性等多种特性。在已有的自动谈判 模型中，以r u b i n s t e i n 弘u 为例，他采用了有顺序的交换谈判提议( o f f e r ) 的方式 来处理动态谈判中的单要素问题。其中，每个谈判参与者都指定了一个递减率常 量，这样就使得谈判可以尽早达成谈判协议。这种谈判模型确实能够达成均衡的 谈判结局。但是，经典的博弈论在处理多要素的谈判场景中存在着局限，更关键 的是，它不能很好地处理不完全信息的谈判场景。在这种谈判场景中，每个谈判 参与者的效用函数或者偏好是私有信息，基于数理逻辑的博弈论无法为复杂的谈 判场景提供解决方案。不过，博弈论中的相关概念倒是可以被用来研究计算实体 之间的交互行为。而且，博弈游戏的形式也有助于自动谈判的模型设计。 通常来讲，博弈论根据其所采用的假设不同而分为合作博弈和非合作博弈 1 1 1 j 。合作博弈主要强调的是团体理性、集体利益以及收入的分配；而非合作博 弈主要关注策略以及策略的执行，也就是，研究人们在利益相互影响的局势中如 何选择策略使得自己的收益最大，即策略选择问题，强调的是个人理性。 在合作博弈的情况下，参与谈判的a g e n t 通过各种协作的方法共同搜寻最大 的集体利益，然后，从所得到的一组谈判收益中做出选择，选出一个作为谈判的 结果。这种类型的谈判所关注的主要问题是集体效率和收入的分配。为了找到对 第1 2 页共5 1 页 一种多阶段相互协作的自动淡判模型及其实现第三章多阶段相互协作的自动谈判模型 集体最有益的谈判结果，参与谈判的a g e n t 会查找一组可行的谈判结果，然后选 择其中最优的作为最终的谈判结果。一旦找到并确定了对集体最有益的产出，参 与谈判的a g e n t 就必须接受。 在非合作博弈的情况下，参与谈判的a g e n t 采用各自的谈判策略进行谈判， 以达到他们的目标。这类谈判关注的是调整谈判策略，以及保证谈判结果的执行。 谈判参与者必须能够识别出对谈判结果有影响的谈判策略。每个谈判参与者是本 着最大化其个体利益而与其他参与者进行交互的。 当谈判参与者选定了一种谈判策略后，必须做到按照所商定的谈判策略执 行，即保证履行选定的谈判策略。这可以通过引入惩罚机制来保证，如此以来， 不遵守谈判协议的谈判参与者就不可能得到更大的利益。谈判参与者将十分清 楚，如果他们背叛谈判协议，他们将得到更少的收益。 此外，自动谈判模型还必须考虑到其他的因素和标准，包括： 谈判效率：系统必须能够保证，参与谈判的a g e n t 能够在最短的时间内达成 协议( 如果存在这样的协议的话) 。 有效性：如果在参与谈判的a g e n t 之间存在某种谈判结果，那么这个谈判结 果应该在谈判结束后是稳定平衡的。这将保证谈判参与者不会背叛他们的协定。 私有效用函数：效用函数被用来判断谈判提议( o f f e r ) 或者谈判回应提议 ( c o u n t e ro f f e r ) 有多好。它为参与谈判的a g e n t 提供了必要的信息，以决定谈 判提议是否可以接受它。保持该函数私有是十分重要的。 多重谈判要素：自动谈判模型应该允许参与谈判的a g e n t 表达它们想要谈判 的任意谈判要素。而多重谈判要素通常会导致非常大且复杂的搜索空间。因此， 必须设计出一种有效的搜索算法对其进行搜索。 在下一节，将简要介绍一下自动谈判中所需要的共同进化方法。 3 2 启发式算法( h e u r i s t i ca p p r o a c h e s ) 与自动谈判模型 受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方 法。对j 那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方 法，人们常常称之为启发式算法( h e u r i s t i ca l g o r i t h m ) 。优胜劣汰是大自然的普 遍规律，它主要通过选择和变异来实现。选择是优化的基本思想，变异( 多样化) 是随机搜索或非确定搜索的基本思想。“优胜劣汰”是算法搜索的核心，根据“优 胜劣汰”策略的不同，可以获得不同的启发式算法。启发式算法的主要思想来自 第1 3 页共5 1 页 一种多阶段相互协作的自动谈判模型及j e 实现第三章多阶段相互悱作的自动淡判模型 于人类经过长期对物理、生物、社会的自然现象仔细的观察和实践，以及对这些 自然现象的深刻理解，逐步向大自然学习，模仿其中的自然现象的运行机制而得 到的。现在的启发式算法也不是全部来自然的规律，也有来自人类积累的工作经 验。 在重复性的游戏或者有交换谈判提议( o f f e r ) 的谈判中，有可能采用某些 自适应的行为。这样自适应的行为通常都是基于使用启发式的算法【8 】。通过一 系列学习的过程，参与谈判的a g e n t 能够从不断重复的谈判中找到更有利的谈判 结果。参与谈判的a g e n t 应该能够利用他们的经验以提高他们的性能。学习的过 程可以和一次单一的谈判联系在一起，也可以是通过一系列不同的谈判。本研究 所采用的学习方式是和一次单一的谈判联系起来的。本研究所定义的谈判协议包 含的是从谈判提议( o f f e r ) 以及谈判回应提议( c o u n t e ro f f e r ) 中获得的信息。 启发式学习机制的优势是，它可以提供足够的适应性并且能够在信息不严格 不充分的环境中提高性能。当谈判发生在动态的环境中时，行为都是非确定的， 即即便在相同的状态下，所采取的行为都不总是导致相同的结果“。各种学习 机制的区别在于，他们采用不同的方式来处理仿真以及对谈判提议( o f f e r ) 和 谈判回应提议( c o u n t e r - o f f e r ) 的评估。在自动谈判系统中被用到的启发式算法 机制包括贝叶斯学习( b a y e s i a nl e a r n i n g ) i 2 3 1 、q 学习j 以及基因算法( g a ) 1 , 1 3 , 1 4 , 1 5 】。贝叶斯学习算法主要采取的方法是随着谈判对方对所给谈判提议 ( o f f e r ) 的回复中所传回的证据不断明显，而逐渐修改算法中的概率。q 一学习 则是一种强化学习的方式，它的思路是奖励产生好的结果的行为，惩罚带来坏结 果的行为。而g a 使用的是一个更广泛的搜寻过程，以识别出最佳的解决方案。 它将可能的( 可行的) 解决方案编码成一组基因，然后通过自然选择、交叉、变 异的过程，找到更好的解决方案。 三种机制最大的不同在于对目标函数的定义与编码。对多要素的谈判来说， 每种学习机制分别根据各自的算法特征实现编码函数，以对效用或者谈判者的信 念进行仿真。z e n g 2 3 1 的b a z a a r 谈判模型使用的是贝叶斯学习算法。在他的模型 中涉及到了多要素的问题。但是，在其贝叶斯方程中，只包含一个要素，即价格， 以此来代表参与谈判的a g e n t 的信念。换句话说，单一要素( 价格) 能够代表其 他的要素来细化模型中的概率或者信念。r o c h a 和o l i 、, a r i a1 2 4 j 使用q 学习算法 实现了一对多的多要素谈判模型。然而，他们的实现只用在一个拍卖( 投标) 方 程，并没有将其应用于多要素的谈判场景中。一般而言，在复杂的场景中( 谈判 要素多于3 个的谈判) ，这两种学习算法显得效率不高，并且有效性不足。尤其， 在定义目标函数或者将问题编码为一个简单的贝叶斯方程或q 学习方程方面， 第1 4 页共5 1 页 一种多阶段相互协作的自动淡判模型及其实现第三章多阶段相互协作的自动谈判模型 存在许多难点。而且，s e n 和s e k a r 彻p j 也证明了，基于基金算法的的分类系统 能够比q 学习算法更快地达成近最优的解决方案。他们的论点恰恰揭示了基因 算法所特有的快速收敛的优点。 基因算法( g