（基础心理学专业论文）双边多议题自动协商研究.pdf

双边多议题自动协商研究 学科专业： 指导教师： 双边多议题自动协商研究 基础心理学 邱玉辉教授 研究方向：人工智能与认知 研究生：张虹( b 1 1 9 ) 内容摘要 近年来，网络的迅速发展使得信息流通更为便捷，无形中形成了电子商务的 蓬勃发展。在商务活动中，为了解决买卖双方的冲突和争议，大多数情况下都会 采用协商方式来取得共识。传统的协商通常会由买卖双方各自派遣代表面对面的 进行，这种方式势必会耗费大量的人力和物力，甚至还会受到一些人为因素的影 响，会突现一些不公平性和随机性。自动协商方式在很大程度上可以解决这些问 题。人工智能和经济学者在这方面做了大量的工作，并且也有了显著的成就，本 文的选题基于这样的背景，具有较好的理论价值和应用前景。 本文在研究过程中改变了传统的自动协商中只是关注协商结果的方式，强调 了协商本身的过程，尤其是协商过程的每一步决策都涉及到协商双方的心智状 态，通过获取对手的偏好，可以动态决定自己的协商策略，以便更好的给出下 轮提议，最终在自动协商过程中实现“双赢”。 本文的研究工作和创新点主要包括以下几个方面： 一、构建了基于a g e n t 的双边多议题自动协商模型 本文的工作是在全面研究双边多议题自动协商问题上开展的，首先给出了自 动协商的形式化定义，细分了协商议题的类型，提出了协商协议和协商流程：然 后在分析s p e e c ha c t 理论的基础上，定义了协商过程中最基本的通信原语；最后 提出了自动协商的，一种基本交互算法。 啊南帅范人学博l 学位论文 二、建讧了自动协商中买卖双方的b d i 模型 深入分析了协商过程中。参与双边多议题自动协商的买卖双方的心智状态， 分别建立了自动协商中买卖双方各自的b d i 模型，给出协商双方的心智状态的 形式化定义，并在此基础上提出了一种s e l l e r 的b d i 的修正算法，讨论了在通信 中b u y e r 的心智状态的获取方法，以及从心理学视角剖析了影响协商双方的各种 心智状态。 三、提出了基于时间的动态协商策略 详尽研究了影响协商策略的重要因素时间，提出了时间因素下的动态协 商策略。通过分析个性心理因素中动机强度随时间的变化情况，提出将协商初始 策略分成三大类，即经济性，冒险性和保守性，并分别对它们进行了函数表示； 然后讨论了各种策略相互影响下的共同效用变化隋况，得到了动态选择策略的方 法；最后，还设计了获取协商对手偏好的学习方法。 四、研究了基于模糊规则和多类型效用函数的提议生成方法 仔细分析了在协商过程中影响每一轮提议的各种要素，扩展了传统方法中的 单一效用函数，提出了更加切合实际情况的多类型效用函数，井给出了各类效用 函数的拟合方法；在分析多议题的不同权值基础上，针对每一轮协商的动态策略， 设计了获取总体目标效用和单个议题目标效用的方法：然后提出了一种基于模糊 规则的提议生成方法；最后从理论上分析和说明了自动协商系统的有效性。 基于上述研究，论文还构建了双边多议题自动协商系统( b i l a t e r a lm u l t i i s s u e n e g o t i a t i o ns y s t e m ，b m i n s ) 的人机交互实验平台，通过m a t l a b 工具进行了模拟 实验。在模拟实验中分析了各种不同效用函数和动态策略中可行解空间，效率前 缘和协商轨迹；在人机交互实验中，统计了协商成功率，协商次数，协商成交值 等情况，通过各项数据以及与其他系统的比较验汪了研究的可行性和效率。 关键词：双边多议题，自动协商，b d i 模型，动态策略，动机，模糊规则 电子商务，a g e n t i i 双边多议题自动协商研究 r e s e a r c ho nb i l a t e r a lm u l t i - i s s u eau t o m a t e dn e g o t i a t i o n r e s e a r c hd i r e c t i o n ：a r t i f i c i a li n t e l l i g e n c e s u p e r v i s o r ：p r o f q i u 琢- h u i a u t h o r ：z h a n g , h o n g 伊1 1 缈 a b s t r a c t w i t ht h er a p i dg r o w t ho fi n t e r a c t ，a u t o n o m o u ss o f t w a r ea g e n t s ，w h i c h c a r lb ev i e w e da sd e l e g a t e so fh u m a nb e i n g si nt h ec y b e r s p a c e ，h a v ed r a w s m u c ha t t e n t i o ni nr e c e n ty e a r sb e c a u s e o ft h e i rp o t e n t i a lc a p a c i t yt o r a d i c a l l yc h a n g et h ec u r r e n ts t y l eo fp r a c t i c i n ge - c o m m e r c e a g e n t b a s e d a u t o m a t e dn e g o t i a t i o nt e c h n o l o g yh a st h ep o t e n t i a lt or a d i c a l l yc h a n g et h e w a yw i t hw h i c hi n f o r m a t i o nt e c h n o l o g yw a s c o n d u c t e d i nt h i st h e s i s ，w e p r e s e n t an o v e lm o d e lf o rb i l a t e r a lm u l t i i s s u e a u t o m a t e dn e g o t i a t i o n i n s t e a do ff o c u s i n go nt h ep r e d i c t e do u t c o m e s ，o u r m e t h o de m p h a s i z e st h en e g o t i a t i o np r o c e s si t s e l f s p e c i a l l y , w ei l l u s t r a t ea s e q u e n t i a ld e c i s i o n m a k i n gn e g o t i a t i o np r o c e s s a t e a c h n e g o t i a t i o n i t e r a t i o n ，a na g e n tc h e c k st h eh i s t o r yo ft h ep r o c e s sa n du p d a t e si t sb e l i e f s a b o u ti t so p p o n e n t sa n dt h e nt r i e st om a x i m i z ei t so w ne x p e c t e dp a y o f f b a s e do ni t so w ns u b j e c t i v eb e l i e f s i i i 堕雯! ! ! ! ! 塑兰翌：! 竺些堕塞 t h em a j o rr e s e a r c hw o r ki nt h i st h e s i sc a nb ev i e w e da sf o l l o w 1 t oc o n s t r u c tab i l a t e r a lm u l t i - i s s u ea u t o m a t e dn e g o t i a t i o n s y s t e m b a s e do na g e n t i nt h i sp a r t ，w ef i r s t l yd e s c r i b et h ef o r m a l i z a t i o ns y s t e m ，f f a c t i o n i z et h e t y p e so fn e g o t i a t i o ni s s u e ，a n d d i s c u s st h e p r o t o c o l a n df l o wf o r n e g o t i a t i o n c o m m u n i c a t i o ni st h em a i n l ym e t h o di nn e g o t i a t i o n ，s oi no u r t h e s i sw ea l s op r e s e n tt h eb a s i cp r i m i t i v ef o rn e g o t i a t i o nb a s e do ns p e e c h a c tt h e o r y a tl a s t ，t h ei n t e r a c t i v ea l g o r i t h mi n n e g o t i a t i o ns y s t e mi s i n t r o d u c t e d 2 t oe s t a b l i s ht h eb d im o d e lb e t w e e ns e l l e ra n db u y e ri na u t o m a t e d n e g o t i a t i o ns y s t e m d u r i n gn e g o t i a t i o n ，t h ea g e n t sw h op a r t i c i p a t ei na u t o m a t e dn e g o t i a t i o n h a v ed i f f e r e n tm e n t a ls t a t e s ，s oh o wt oc o n s t r u c tb d is y s t e mi st h em o s t i m p o r t a n tp a r ti nn e g o t i m i o ns y s t e m i ns e c o n dp a r t ，o u rf i r s t l yd e f i n et h e b d im o d e lf o rs e l l e ra n db u y e r ，t h e ni n t r o d u c et h eb d ir e v i s e da l g o r i t h m f o rs e l l e ri nn e g o t i a t i o n a ts a m et i m e ，t h em e t h o dt oc a t c ht h em e n t a l s t a t eo f b u y e ri nn e g o t i a t i o nc o m m u n i c a t i o n i sa l s od i s c u s s e d f i n a l l y , t h e m e n t a lf a c t o rw h i c hs h o u l db ec o n s i d e r e di nn e g o t i m i o nf r o mp s y c h o l o g y v i e w p o i n ti sp r e s e n t e d 3 t op u tf o r w a r dt h ed y n a m i cs t r a t e g yb a s e do nt i m ei n n e g o t i a t i o n s y s t e m t i m ei sa ni m p o r t a n tf a c t o rf o rn e g o t i a t i o n ，o u rr e s e a r c ha l s od i s c u s s t h i sp o i n t i nt h i s t h e s i s ，w em a i n l yr e s e a r c ht h ed y n a m i cn e g o t i a t i o n s t r a t e g yb a s e do nt i m e w ef i r s t l ya n a l y z et h em o t i v a t i o ni nn e g o t i a t i o n ， 双边多议题自动协商研究 a n dd i v i d et h es t r a t e g yi n t ot h r e ek i n d s ：e c o n o m ym o t i v a t i o n ，a d v e n t u r e m o t i v a t i o na n dg u a r dm o t i v a t i o n t h e nw ei n v e s t i g a t et h ej o i n tu t i l i t yo f a b o v et h r e es t r a t e g i e s ，a n dc o n c l u d eh o wt oa d o p tt h ed y n a m i cs t r a t e g yi n n e g o t i a t i o na f t e ro b t a i nt h em e n t a lf a c t o ro fo p p o n e n t i nt h ee n d ，w ea l s o p r e s e n th o w t os t u d yt h er i v a l sp r e f e r e n c e 4 t or e s e a r c hh o wt og e to f f e ri ne a c hn e g o t i a t i o nr o u n db a s e do nf u z z y r u l e sa n dm u l t i p l eu t i l i t yf u n c t i o n s w ec a no b t a i nt h et a r g e tu t i l i t ya f t e rc o n f i r mo w nd y n a m i cn e g o t i a t i o n s t r a t e g y i nt h i sp a r t ，w em a i n l yr e s e a r c hh o w t oc a l c u l a t ed i f f e r e n tu t i l i t y f u n c t i o nf o rd i f f e r e n ci s s u ea n dh o wt oc a l c u l a t et h et a r g e tu t i l i t yi n d i f f e r e n ti s s u e sw h i c hh a v ed i f f e r e n ts i g n i f i c a n c e t h e nt h ea l g t r r 竹h mf o r p r o d u c i n ge a c hi s s u e so f f e ri sb e i n gp r e s e n t e db a s e do nf u z z yr u l e s a t l e n g t h ，t h ev a l i d i t yo fs y s t e m i sa l s od i s c u s s e df r o ma c a d e m i cp o i n t e v e n t u a l l y ，w ec o n s t r u c tt h en e g o t i a t i o np l a t f o r mb e t w e e na g e n ta n d h u m a n ，i m p l e m e n ts i m u l a t i o n a n dr e a l i s t i c e x p e r i m e n t t h r o u g ht h e f e a s i b l es o l u t i o ns p a c e ，t h ee f f e c t i v ef r o n t i e ra n dn e g o t i a t i o nt r a c k ，a n ds o o n ，w ec e r t i f i c a t et h ef e a s i b i l i t ya n de f f i c i e n c yo f o u rm e t h o d k e y w o r d ：b i l a t e r a l ，m u l t i - i s s u e ，a u t o m a t e dn e g o t i a t i o n ，b d im o d e l ， d y n a m i cs t r a t e g y , m o t i v a t i o n ，f u z z yr u l e ，e c o m m e r c e ，a g e n t v 双边多议题自动协商研究 图1 1 一个多人多议题协商例了 图2 - 1 西商中的效率前缘 图3 1 协商协议 图3 - 2 协商流程 图3 - 3 协商中通信基本形式 图目录 图4 - 1a g e n t 。的上下文信念和意图 图4 - 2b d i 模型中的个性心理因素 图5 - 1 协商问题难易度、动机强度和效率的关系 图5 - 2 线性函数( 经济性动机) 图5 - 3c o n c e d e r 函数( 冒险性动机) 图5 - 4b o u l w a r e 函数( 疑虑性动机) 图5 5 多项式函数 图5 - 6 指数函数 图5 7 经济性经济性 图5 - 8 经济性一冒险性 图5 - 9 经济性一疑虑性 图5 - 1 0 冒险性一冒险性 图5 1 1 冒险性经济性 图5 1 2 冒险性一疑虑性 图5 1 3 疑虑性一疑虑性 图5 一1 4 疑虑性一经济性 图5 - 1 5 疑虑性一冒险性 图6 - 1 各议题取值的范围 图6 - 2 反对冒险性效用函数 石 ” 引 鸵 ” ” 招 嚣 站 钞 矾 矾 矾 矾 鲥 以 酡 砬 酡 加 陀二二二二二二二二二二二二 两南帅范入学博寸学位论义 图6 - 3 倾向冒险性效用函数 图6 - 4 直线性效用函数一 图6 - 5 从倾向冒险到反对冒险性效用函数 图6 - 6 议题重要程度的模糊衡量方法 图6 7 议题取值与效用值设置 图6 - 8 效用函数拟合实例 图7 - 1 协商系统的基本构建 图7 2 协商内容设置 图7 - 3 连续议题属性设置 图7 - 4 离散议题的属性设置 图7 - 5 议题重要程度设置 图7 - 6 协商轨迹示例 图7 7 协商实例一 图7 8 协商实例二 图7 - 9 协商实例三 图7 一1 0 人机交互实验平台 2 住 m m m m 埘 m m 抛 m 瑚 胤 朋 |二|一 双边多泌题自动协商研究 表目录 表2 一l 协商的分类 表3 - 1 协商行为原语的语义 表5 - 1 针对不同类型b u y e r ，s e l l e r 所采用的策略分析， 表6 - l 基于模糊规则的连续议题提议 表6 - 2 基于模糊规则的离散议题提议 表7 - 1 人机实验的基本实验内容一 表7 2 模拟协商例子之一 表7 - 3 模拟协商例予之二 表7 4 模拟协商例子之三 表7 - 4 人机交互实验综合结果 表7 - 5 卖方满意程度调查表结果 表7 - 6 买方满意程度调查表结果 表7 7 各类协商系统的比较 2 8 钙 强 黔 踮 跖 卯 眇 y7 6 4 9 9 1 西南师范大学研究生学位论文原创性声明 秉承我校勤奋、严谨学风，本人申明所呈交的论文是在导师指导下进 行研究工作所取得的成果，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含在我校或其他教 育机构获得学位论文上的材料，- 9 我共同工作的同事对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 该申请学位论文与资料如有不实之处，本人承担一切相关轰任。 论文作者签名：塾当兰日期：芝! ! ! 垒! 旦矽茸 西南师范大学研究生学位论文版权协议书 本人完全了解西南师范大学有关保护知识产权之规定，即：研究生在 攻读学位期间所完成的论文的知识产权人单位为西南师范大学。本人保证 毕业离校后，发表攻读学位期问所完成的论文或使用这些论文中的原创性 技术成果时，署名单位为西南师范大学，或在明显位置标明，该成果是作 者在西南师范大学攻读学位期间完成的。学校有权保留并向国家有关部门 或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。学校可以公布 学位论文的全部或部分内容( 保密内容除外) ，可以采用影印、缩印或其 他手段保存论文。 论文作者签名：盗堡兰 指导教师签名：之豳垒 日期： 双边多议题自动协商酬究 第1 章前言 近年来，网络的迅速发展，使得信息流通更为便捷，网络的无穷魅力和因此汇集而来 的庞大人气，无形中形成了网络虚拟人群。在虚拟人群中，人们容易找到拥有相同兴趣 的人，彼此讨论相同话题；也提供给人们自由幻想的空间，让人可以判有箨种各样的角 色。所以有人把商业活动带入虚拟人群中，形成了电子商务的蓬勃发展。而将a g e n t 技 术用于智能电子商务的研究也形成了一个热点。在商务活动中，为了解决买卖双方的冲 突和争议，大多数情况下都会采用协商( n e g o t i a t i o n ) 方式来取得共识。早期的电子商务 网站，他的商品和服务的价格以及项目等信息都是由商家事先设定好的，一般情况下并 不允许修改或者议价。但随着电子商务的全球化、个性化和及时性的发展要求，在线交 易的行为变得越来越复杂，商务谈判也出现的十分频繁。如何通过互联网进行远端协商 ( 也可以称为谈判) 以形成谈判支持系统( w e b - b a s e dn e g o t i a t i o ns u p p o r ts y s t e m ) 成为研 究热点。 1 1 问题提出 协商( n e g o t i a t i o n ) 足人际互动模式中最复杂的一种沟通方式，然而却也是商务中最 重要的一环。协商在商务中之所以重要，是因为它决定了交易的内容。最简单的协商也 可以叫做议价( b a r g a i n i n g ) ，代表协商的议题仅仅止于价格，例如臼常生活最为常见的， 和夜市小贩杀价的过程t 或者是企业与企业彼此间针对大型合作计划的讨价还价，都_ 口j 以说是最简单的协商例子。近几年来，一个很有趣且令许多研究者关心的问题就是：协 商可以自动化吗? 答案足肯定的，事实上，这样的例子在很早以前就有了，那就是著名 的电子商务系统：e b a y 网站。在这个系统中，协商方式是一种单方向的i ；【价，就是拍卖 ( a u c t i o n ) 。也就是说，协商的一方不断出价，而另一方只有接受或不接受两种选择。 这种协商方式非常适合拍卖具有特殊性的商品，例如数量稀少的签名海报，或是古董等。 然而对于较常见的普通商品，则通常不会用拍卖的形式来协商( 除非是为了促销) ，而 会用另一种双向拍卖( c o n t i n u o u sd o u b l ea u c t i o n ) 的程序来议价。在双向拍卖的情景里， s 西南师范人学博十学位论文 小j 买方可以出价，卖方也可以出价，因此如果买方意愿不高时，卖方会尝试提出优惠 的价格来吸引买方。 以上的讨论都仅限于对价格来议价的协商，事实上，除了这种单议题协商外，还有所 谓的多议题协商( m u t l i i s s u e n e g o t i a t i o n ) 。多议题协商远比单议题协商复杂得多，举例 来说，当你和夜市小贩杀价的时候，这个小贩如果不想陷入无谓的价格竞争，它可能会 提议用送赠品来取代你的杀价。这样的协商方式是非常高明的，因为他既满足买方占便 宜的心理，也成功地隐藏了该货品的底价：而且如果该赠品在买方的心中价格颇高，则 这样的协商结果可以说是双赢的，因为卖方成功地多卖出一项商品，而买方则多得到一 项有用的赠品。以另一个情景来说，如果是公司与公司针对大型合作计划来协商时，除 了协商价格外，双方也可以引进更多的议题来创造双赢的可能性，例蓟i ，双方将各类台 作的细节都当作一项议题来讨论，则分工可以相当精细，而双方也可以评估利弊，各取 所需。 图t - 1 一个多人多议题协商例子 多议题协商可以复杂到是一个多入多议题的协商环境，如图1 - i 具有不同偏好的团 体协商企图参加一个整合的旅游行程，每一个人都希望整个行程设计越符台自己的偏好 越好，然而又想藉由整合中人的力量来进行集体议价；而从服务提供者的角度来说，每 个服务提供者皆希望越多客户越好，同时却还得兼顾整体行程设计是否可达成，还有获 6 双边多议题自动协商研究 利与否等，形成了一个复杂的多人多议题协商情境。在过去因为无法处理这样的复杂度 便出现了中间商，也就是旅行社。旅行社藉由固定的套装行程，降低协商的复杂度，让 消费者只能针对价格来协商；虽然降低了复杂度，却牺牲了弹性，无法满足所有人的要 求。如果这样的协商可以自动化，刚旅游不但可以是有趣的( 兼顾个人偏好) ，还可以 非常便宜( 最佳资源分配以及降低旅行社风险管理成本) 。 多议题协商技术主要可以分成两大类，类是协商决策支持系统( n e g o t i a t i o ns u p p o a s y s t e m ：n s s ) ，另一类则协商代理系统( n e g o t i a t i o ns 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 ，则它可以用最佳的 协商策略，且在不泄露此公式的原则下，和对方达成最佳的协定。目前有关n s a 的研究， 主要面临的问题就是如何验证策略的纳什均衡( n a s he q u i l i b r i u m ) 。所谓的纳什均衡， 指的是当协商某方采取最佳策略时，他可以预期对方必定会采用己方已知的最佳策略回 应，如此方能确保协商的结果具有一定的效用。 随着网络的快速发展，传统商业运作流程也转变全球化的电子商务运作模式。然而， 支持电子商务顺利运作的基础建设似乎还有很多困难有待解决。就交易双方之间的协商 而畜，就是一个相当棘手的问题。由于商业活动所涉及的领域，范围广泛，关系也比较 复杂，因此传统需有交易方之间，彼此推派参与协商的人员以亲自会议面谈方式，不断 缩小协商者之间彼此对各项议题的看法，已达成全体与会人员的共识。缩着全球电子商 务兴起，企业组织间的商业交易活动已经渗透到各种应用系统与资料交换标准中。传统 会议类型的协商机制已经无法满足电子商务环境中所要求的高度时效性。因此自动协商 已经逐渐成为电子商务系统的重要组成部分。 7 两南师范大学博上学位论文 近几年，随着a g e n t 技术【7 2 的发展，先进的智能技术已经开始广泛的应用于电子商 务领域【4 】。具有a g e n t 特点的智能技术可以在电予商务活动中扮演着各种角色，比如： 买方，卖方，仲裁人，资源分配人以及信息提供助手。通常认为，目前电子商务的研究 绝大部分处于第一个阶段，在这个阶段电子商务的主要特点是：服务方连接到i n t e m e t ， 主要提供商品日录浏览，交易方式选择，服务方基本信息获取，服务支持等服务。这种 情况下，电了商务系统只需要基本的i n t e r n e t 服务，而针对用户的特性进行的个性化服务 是非常少的。我们更愿意认为这个时候的电子商务系统类似于一个购物向导，网上商店。 比较成功的有购物助手( p e r s o n a l o g i c h t t p ：w w w p e r s o n a l o g i c c o r n ， f i r e f l y 【h t t p ：w w w f i r e f l y e o m ) ，随着c b b ( c o n s u m e r b u y i n gb e h a v i o r ，消费者行为模型) 的提 出，具有初步智能特性的购物a g e n t ，t e f e - g t - t 6 t e h t t p ：e e o m m e r c e m e d i a m i t e d u t e t e a t e t e ， 它可以帮助用户在商务活动中实现多个过程：产品代理，批发代理，甚至可以进行最基 本的协商活动。在第一代电子商务系统中，买卖双方关注的焦点主要在于价格因素。不 可否认，商务活动最直观，生动的因索就是价格，但是正是由于这个原阑，也会忽略其 他相对重要的因素，比如：售后服务，交货时间以及对供销双方的跟踪服务等。为了满 足人们在电子商务过程中越来越多的要求，就需要提高系统的智能化和适应性，同时就 出现了一些功能更为全面的系统，如p r i e e l i n e w w w p r i e e l i n e c o m ， h o t w i r e h t t p ：w w w h o t w i r e c o r n ，在这些网站中，用户可以根据自己的需要，设定一些 偏好( 比如：航班日期，旅馆等级，航班的中转点等) ，当然在这个过程中，我们也不 能忽略价格，可能在这种情况下，所获得的并不是一个最低的价格，但是显然可以在满 足某些需求的基础上，找到更为合意的商品。这里我们所指的合意的商品是指能够在多 个因索的平衡中，获得较为满意的最大效用，那么如何在多个因素之间找到平衡，这就 需要协商。 目前的电子商务系统中，许多研究人员提出、应用和实现了自动协商( a u t o m a t e d n e g o t i a t i o n ) 的概念 7 3 【7 4 儿7 5 】 7 6 【7 7 】【7 8 】【7 9 】。近年来，随着研究人员的不断深入，自 动协商已经可以在很大程度上帮助用户在商务活动获取更大的综合收益。它所涉及的领 双边多议题自动协商研究 域非常广泛，包括：计算机科学，人工智能，经济学，博弈论等。本文的研究t 作也是 基于这样一个具有使用价值，应用前景广泛的领域。 1 2 自动协商的研究领域 1 2 1 经济领域的自动协商 从经济学角度看，双边协商的研究主要是基于对策论( g a m e t h e o r y ) 的，因此研究方 向也可以简单的分为：非合作环境的多问题自动协商和合作环境多问题自动协商。 1 非合作环境的多问题自动协商 这个方面的研究重点是如何有效地协商中的多个问题，以及他们在现实世界中的应 用。因此，首先应该解决这样两个问题：1 什么情况采用分布式多问题自动协商，什么 情况下进行同步协商? 2 协商过程可以选择哪些不同方式? ( 1 ) 同步和异步协商的选择 一般情况下，人们往往认为时间是影响协商的重要因素，但是有的时候协商的破裂却 是因为协商方对某一个协商闯题的过于执着。c h e n 在【1 1 4 中专门针对破坏异步协商的因 素进行了详细的分析。他主要研究了协商过程中协商失败概率对于协商方法的选择，他 发现当失败概率较低时，往往喜欢选择同步协商，因为协商双方都是基于“双赢”原则 并且有足够的时间使得双方的效用达到最大；而在失败效率较高的时候，选择异步协商 的概率大。c h e n 的研究还发现当参加协商的a g e n t 都属于不同类时，选择异步的可能性 要大于选择同步协商的可能性。s e r r a n o 等人在【1 1 5 】中也进行了讨论，他们假设异步协商 过程中某个问题讨论的失败会影响整个协商过程，并且限定a g e n t 在每一轮只能针对一 个问题给出协商提议，结果发现在失败率降低到0 的时候，就会出现均衡点增多和无效 性增加，丽这种情况在同步协商中是不会发生的。 除此之外，w e i n b e r g e r 在i l l 6 , 提出了“选择性接受”的概念，他是指在协商最初，可 以由协商某一方就协商的所有问题同步提出一个提议，另方可以选择性接受其中某一 个或某一个，然后就那些还没有达成协议的问题再进行异步协商。 9 两南帅范大学博 学位论文 ( 2 ) 涛商议程的选择 从现有的研究情况看，协商议程【117 】通常分为三类：分散同时，顺序。分散议程是 指协商的多个问题分开同时协商( 可以看作1 1 个序对，每个序对代表一个问题，每次提 出的协商提议都是n 个序对) ，同时是指多个问题同时协商( 把n 个问题看作一个整体) ， 而顺序协商是指n 个问题一个接一个的顺序协商，也就是分布协商。这个方砥典型研究 是r u b i n s t e i n 和s t a h l 的议价模型 2 合作环境的协商 合作环境中的“合作”概念并不是指协商双方是完全台作的，而是指能够在信息比较完 整的情况下进行协商，所以有的研究人员也把他们称为完全信息协商。这个方面的研究 主要基于n a s h 的对策论为基础，应用大量的n a s h 公理，同时所提出的协商方法应该是 满足“p a r e t o 最优”的。这个部分将重点介绍公平协商。 公平协商是合作环境中比较有代表性的一类，“公平”的概念主要是指在协商双方之间 进行合理公平的分配。一般分为两个部分，第一步是要确定整个协商过程的收益，第二 步是在进行“公平”的收益再分配。这个方法最早是由k n a s t e r 和s e t i n h a u s 在研究拍卖过 程中提出的【1 1 8 t 他的过程非常简单，首先将所有协商中的有利因素和收益全部给赢家， 然后再在协商参与方之中进行金钱上的分配。b r a m w 和t a y l o r 在【1 1 9 】中介绍了另外一种 公平分配过程，称之为“调整胜方”，在这个过程中，各个协商问题的收益都先分配给在 第一轮提议中最占优势的那些a g e n t ，然后再通过金钱的方式交换，协调。k n a s t e r 在 1 l8 】 中指出这种方法可能效率很差，并且对其进行了改进，同时比较了这种方法与分步协商 和同步协商的效率差异。目前，公平协商的研究刚刚起步，还亟待进一步研究发展。 1 2 2 人工智能领域的自动协商 经济学对协商研究的目的是寻找最优的协商机制和平衡的协商策略。在非合作环境， 研究往往集中进行严格的协商模型化，分析改进协商对策，选择合适协商方式。安排合 理的协商议程；在合作环境，代表性的研究者n a s h 和其他人则着重于公理的研究，任何 一种协商方法都试图满足这些公理并且达到p a r e t o 最优。但不管那种情况，在现实环境 0 双边多议题自动协商研究 中的应用都是有限的。因此近几年。人工智能方面的研究逐渐增多，并且取得了不小的 成就。 人工智能研究人员在双边多问题自动协商的研究主要在于设计合理的自动协商模型 和好的协商代理机制，利用具有智能特点的a g e n t 进行多问题自动协商，尽管协商结果 不一定是最好的，但是它对于协商方法的自动化和协商的应用带来了巨大的影响。目前 主要的研究工作，是从协商框架，协商权衡机制和协商空间搜索方法三个方面进行分析 的。 1 协商框架 协商框架是设计协商a g e n t 的基础工作，它的重要性不言而喻，目前的主要的研究有 这样的一些： 1 、f a t i m a 等人提出基于协商议程的框架 5 9 1 2 3 1 2 4 。在这个协商框架中，a g e n t 可以提出针对一个问题的协商独立提议，也可以提出有关几个协商问题的组合提议，同 样在进行决策的时候也可以独立决策或组合决策。例如：如果在协商环境中有两个提议 x l 和x 2 ，同时a g e n t 针对这两个问题也可以有分别的策略s i 和s 2 来决定反提议或者接受， 如果其中有一个提议接受了，那么协商仍将继续。这个框架也意味着其中的效用函数在 正常情况下应该是线性增加的。 2 、s y c a r a 等人是基于实例推理方法进行协商框架的研究【9 8 【9 9 儿8 8 。每一次的协商 a g e n t 都会从几个方面( 比如：协商问题，协商对手，协商背景等) 分析相似的协商实 例，从中进行学习，再确定当前的协商策略和协商框架。他们把这种协商方法主要应用 于劳工管理的协商环境中，并且将时间因素加以考虑。这种方法在有专家指导的现实环 境有着较好的应用实践。s y c a r a 等人还在此基础上提出了协商中的劝诱机制 6 5 1 ，期望通 过协商策略中的诱惑因素对于协商策略的影响，吸引另外一方更趋向于接受当前的协商 提议。 3 、l u o 等人 1 l 】研究出了一种应用于商务环境的基于模糊约束的多问题自动协商框 架。在这个框架中，协商最初由买方针对协商中的多个问题定义一个模糊约束集，并且 按照优先级从高到低依次提交给卖方；卖方在收到后，可以进行这样的选择，要么在约 p q 南师范人学博上学位论文 束范围内给出提议，要么提出要求清买方放宽约束条件；买方再根据卖方回复，选择接 受或者拒绝提议，或者放宽约束条件，还可以选择协商失败。研究者认为在这种方法下， 即使不给出a g e n t 的效用函数，也可以在a g e n t 之间达成具有较好收益的协商结果。 2 协商权衡机制 在协商过程中，协商a g e n t 常常会遇到需要权衡让步的情况，权衡的前提是希望达到 “双赢”的目标。f a r a t i n 等人在 1 0 中提出了一种基于相似度原则的权衡折衷方法。每次当 a g e n t 需要提出新的协商提议时，新的提议要尽量保持上一轮提议的效用值，可以在无 差异集合中选择新的提议，无差异集合定义如下： 捃o 。( 口) = x f p 4 ( x ) = 0 ) 其中x 表示新的协商提议，0 表示当前效用值，v 。表示效用函数，i s o 表示无差异集 合。 在选择新的协商提议时，模糊相似度方法用于选择“最相似”的提议，定义如下： t r a d e o f l ( x ，y ) = a r g m a x 。( 8 ) s i m ( z ，y ) )s i m ( x ，y ) = ：w s i m ，l x j ，y j ) s i m ，乃 = ，( 囊( ) 吃( y ，) ) 其中，y 表示协商对手的最新提议，w j 表示问题j 的权重，s i m i x i ，y j ) 表示问题j 在两 个协商提议中的相似度。h ( ) 表示启发式比较规则。通过实验分析这种方法有助于a g e n t 之间达到更为满意的共识，同时协商结果也更容易满足p a r e t o 优化条件或者接近。 3 协商空间搜索方法 除了前面介绍的模糊规则方法，许多研究者还利用计算原理提出了其他的方法。 l 、k l e i n 等人 6 1 1 基于随机搜索方法来对复杂的合同进行协商，在协商过程中引入协 调a g e n t ( m e d i a t o r ) 角色。协商过程中，协调a g e n t 产生一个提议，同时发给协商双方， 由他们决定是否接受。如果双方都接受，则协商结束；如果有任何一方反对，则协调a g e n t 选择最接近当前效用的可替换协商提议继续请求协商的意见。这个过程一直持续到没有 更好的协商提议，或者协商时间终止。在论文中。k l e i n 定义了两类协商方：一类为爬山 者，另一类为模拟退火者。爬山者在协商过程中比较简单，只要当前协调者给出的提议 1 2 双边多议题自动协商研究 好于上一次协商共识就接受，而模拟退火者的协商过程复杂些，他通过蒙特卡洛学习法 计算概率来确定是否接受当前的协商提议。通过实例，可以发现这些方法都是收敛的， 当协商双方都是模拟退火者的时候协商结果要好于协商双方都是爬山者的情况。如果在 协商过程中，一个模仿爬f j 者，一个模仿模拟退火者，则协商结果可能有利于爬山者， 而爬山者在这种情况下所获得的效益还要好于双方都是模拟退火者的情况。因此，这种 方法有点类似于囚徒困境问题。k l e i n 在研究过程中也采用了相应的方法，在协调a g e n t 的帮助下避免陷入困境。 2 、t e s a u r o 和“基于贝叶斯规则研究