（计算机软件与理论专业论文）多主体系统中的协商研究及其在电子商务中的应用.pdf

一一兰圭堡墨堑! 塑坐塑塑塑业塑丝! ! ! ：! ! 王塑箜! 塑坐旦塑兰 摘要 f9 。【 6 计算机和网络技术的不断发展，使得网络上的商务行为越来越普遍，信息资 源也越来越多。相对而言，客户的时间成本成了相对稀缺的资源。因此，适应网 络和信息发展的需要，利用计算机来替代人在商务活动中的部分工作，或提供相 关的支持，成为对计算机软件系统的需求。多主体系统中的协商问题研究汇是解 决这类问题的有效途径。 协商问题的研究主要应对于两方面的需求：一、通过对环境的分析决策 支持：二、替代委托人执行决策任务自动协商。这两方面的需求都依赖于协 商策略的选择和协商过程的管理。因此，本文主要进行了以下方面的研究： 博弈论是协商研究的基础。在此基础上我们讨论了拍卖、竞价、讨价还价等 相关模型。这些模型是在电子商务中基于主体的自动协商模型的基础。 电子商务多主体系统的实现一个关键问题就是多主体协商。这早主要讨论了 协商协议的规范化描述，协商策略的表示和规划，以及协商中的建模问题。要提 高决策的有效性和决策制度的效率，模型管理的研究是必要的。通过提出一种模 型管理框架，确定决策模型在协商中的角色，来完成有效的管理。 最后，基于智能主体的虚拟市场是应用本文协商研究理论的实际应用。 关键词：多主体系统，自动协商，博奔论，电子商务，协商支持，拍卖模型 多土体系统中的叭商问题埘f 究发j c 礼l u 了商务中的心j f la b s t r a c t a b s t r a c t a st h ep o p u l a r i z i n go f i n t e r n e t ，e l e c t r o n i cm a r k e t sa r eb e c o m i n go n e o ft h em a j o r p a r a d i g m st oc a r r y o u tb u s i n e s st r a n s a c t i o n s c o m p a r e dw i t ht r a d i t i o n a lm a r k e t s e l e c t r o n i cm a r k e t sa r ei n f o r m a t i o n i n t e n s i v ew i t hm u c hl a r g e ri n f o r m a t i o nc a p a c i t y , h i g h e ri n f o r m a t i o np r o c e s s i n gs p e e d ，a n ds h o r t e ri n f o r m a t i o nl i f ec y c l e h o w e v e r ，a p e r s o nu s u a l l yh a sr a t h e rl i m i t e dc a p a b i l i t yt op r o c e s si n f o r m a t i o nw i t hr e l a t i v e l yi o w s p e e da n dm u c h l e s sa m o u n t a sar e s u l t i th a sb e c o m en e c e s s a r yt o d a yt oe n h a n c eo r s u b s t i t u t e p e o p l e sc a p a b i l i t y i nt h ew h o l ec o m m e r c i a l p r o c e s s n e g o t i a t i o n i n m u l t i a g e n ts y s t e mp r o v i d e sa n e f f e c t i v ea p p r o a c ht ot h i sg o a l t h e r ea r et w om a i nr e q u i r e sf o rt h er e s e a r c ho fn e g o t i a t i o n o n ei st op r o v i d e d e c i s i o n s u p p o r tb yt h ea n a l y s i so fe n v i r o m n e n t a n o t h e ri st or e a l i z ea u t o m a t e d n e g o t i a t i o ns u b s t i t u t i n gt h er o l eo fc u s t o m e r sd e c i s i o n f o rb o t ho f t h e s ea r eb a s eo n t h es e l e c t i o no f n e g o t i a t i o ns t r a t e g i e sa n d t h em a n a g e m e n to ft h en e g o t i a t i o np r o c e s s ， t h i sp a p e ri sd i s c u s s e da sf o l l o w i n g g a m et h e o r yi st h eb a s i so fn e g o t i a t i o n b a s e do nt h er e s e a r c ho fg a m et h e o r y ， w ed i s c u s st h em o d e lo f b a r g a i n i n g ，w h i c hh e l p u st ob u i l dt h ea g e n t - b a s e da u t o m a t e d n e g o t i a t i o nm o d e l i ne c o m m e r c e a g e n t m e d i a t e de l e c t r o n i cc o m m e r c ea p p l i c a t i o nm u s t o v e r c o m et h em u l t i a g e n t n e g o t i a t i o n w eo f f e r t h ef o r r n a l d e s c r i p t i o n o fn e g o t i a t i o n p r o t o c o l ，n e g o t i a t i o n s t r a t e g i e s a n dt h ed e c i s i o nm o d e lf o rn e g o t i a t i o n f o re n h a n c et h ee f f i c i e n c y o f d e c i s i o n ，i t i sn e c e s s a r yt op r o v i d es u p p o r tt ot h em a n a g e m e n to ft h en e g o t i a t i o n m o d e lw e p r o p o s ea m o d e lm a n a g e m e n tf r a m e w o r kf o rt h ef l e x i b l ec o n f i g u r a t i o ni n n e g o t i a t i o n m u l t i a g e n tn e g o t i a t i o n d i s c u s s e di nt h i sr e s e a r c h c a nb e a p p l i e d t o m a n y d y n a m i c a n dd i s t r i b u t e da p p l i c a t i o nf i e l d si n c l u d i n ga g e n t b a s e dv i r t u a lm a r k e t k e y w o r d s ：m u l t i a g e n t s y s t e m ，a u t o m a t e dn e g o t i a t i o n ，g a m e t h e o r y e c o m m e r c e ，n e g o t i a t i o ns u p p o r t ，b a r g a i n i n gm o d e l 尸 本人声明所呈交的论文是我个人在导师指导卜进行的研究1 # 4 - 及l l x7 t 7 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文t l t 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示j 7 谢意。 作者签名：王洎日期：3 口0 2 s 2 d 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交沦文的复印仲，允 论文被查阅和借阅：并可以公布论文的全部或部分内容，町以采川影印、 缩印或其它复制手段保存该论文。 作者签名：殳均 导师签名：虹拯d ) - r - 2 1 1 引言 第一章概述 计算机技术和网络技术的发展，已经不再只是研究领域的热点。随着电子商 务的出现和快速发展，越来越多的应用系统在企业内部( i n t r a n e t ) ，企业f n j ( b 2 b ， b u s i n e s st ob u s i n e s s ) ，企业与消费者矧( b 2 c ，b u s i n e s st oc u s t o m e r ) ，甚至于人 与人之间( i n t e r n e t ) 得到广泛的使用。现在，这些应用系统所面临的，更紧迫需 要解决的问题是怎么进一步有效的替代人的工作( a 1 ，a r t i f i c i a li n t e l l i g e n c e ) ， 以及如何配合和辅助人的工作( d s ，d e c i s i o ns u p p o r t ) 。本文在研究和分析博弈 论( g a m e t h e o r y ) 和人工智能理论和方法的基础上，在以多主体系统( m u l t i a g e n t s y s t e m ，m a s ) 环境m a g e 平台上，构建了了在电子商务环境虚拟市场 ( v i r t u a lm a r k e t ) ，实现计算机和网络对电子化商业行为的支持。通过多主体系 统和协商模型管理承载用户协商的全过程的支持服务，利用协商博弈理论促进用 户在谈判中实现利益最大化。本文提出的协商模型管理框架拓展了以往计算机对 电子商务中自动协商和协商支持的范围，同时也是多主体系统的个应用。 本章首先介绍本文研究的应用基础电子商务的基本概念，其次对多主体系统 的演进进行了概要的介绍。然后介绍了囡际上现有的多主体应用系统，并就它们 的特性进行了比较和分析。最后给出了本文的主要研究目标和内容。 1 2 电子商务 电子商务e l e c t r o n i cc o m m e r c e ，简称e c 。通常，电子商务的定义分狭义和 广义两类：狭义的定义是指各种交易行为必须通过网络来进行，即所有的交易必 须在网络和计算机上完成；而广义的定义则是指通过网络的电子化方式来进行的 所有商业行为，即通过计算机和网络，结合各种通信技术来完成各种交易行为。 然而现在的电子商务的概念涵盖了更丰富的内容：企业内的e r p ，c r m ，以 及传统的商业活动和行为( 物流，支付手段) 。从贸易活动的角度分析，电 子商务可以在多个环节实现，由此也可以将电子商务分为两个层次，较低层次的 电子商务如电子商情、电子贸易、电子合同等；最完整的也是最高级的电予商务 应浚是利用i n t e r n e t 能够进行全部的贸易活动即在网l 将信息流、商流、资金 流和部分的物流完整地实现，也就是况，你可以从寻找客户丌始， 直到洽谈、 订货、在线付( 收) 款、丌据电子发票以至到电子报关、电子纳税等通过i n t e r n e t 气呵成。 多土体系统中的协商问题圳宄发l l n - i u 了晒务中的心用 删 l 论丈 电子商务的特性在于资源共享和互动沟通的模式的改变，因此电子商务有它 独特的价值。现代社会中有许多惊人的成本消耗在本来可以用计算机取代的工作 上，包括行政和人事的工作。而绝大多数企业中，最有价值的部分在于资源以及 人员之间的互动沟通，引入电子商务正是因为它可以提供即时的互动沟通和准确 而快捷的资源管理和共享。同时网络的特性使得企业突破地域和时间的限制，大 大降低交易成本，市场价值成倍增长，消费者拥有更大的自主权，企业也得到了 更大的利益。因此即使在网络泡沫破灭的日子罩，人们依旧把振兴的希望寄托在 电子商务上。 1 2 1 电子商务分类 电子商务的应用非常广泛，包括货物电子贸易和服务、在线数据传递、电子 资金划拨、电子证券交易、电子货运单证、商业拍卖、合作设计和工程、在线资 料、公共产品获得、以及其它一些服务( 如信息服务、金融和法律服务) 。从不 同的角度，可以对电子商务进行不同的分类。 从目前世界所流行的电子商务模式来看，电子商务的发展大致分为：b 2 b 、 b 2 c 、c 2 c 、b 2 g ： ( 一)企业与企业之间( b 2 b ) 利用网络和相关技术从事商业活动，并通过上下游企业之间的整合，增加竞 争力。这就是通常所讲的e x t r a n e t ( 对应于企业内部的i n t r a n e t ) 。e x t r a n e t 是企 业与企业之间，为了整合资源，增加上下游企业的联系，减少信息交互成本，所 构建的网络。 这种模式被认为是中国特别是中国网上交易最容易实现的模式，主要原因在 于一方面在进入w t o 之后，政府放松对进出口商品的控制之后，这种模式可以 避开传统的落后经销系统，使中国的企业和国外的企业连接起来，加快企业的国 际化步伐；另外一方面，企业对企业的交易，在信用度恢复的情况下，支付的方 式也相对容易解决。此外，还有些便利条件包括企业问的交易数量大，金额高， 物流成本小；在配送方面已经有比较成熟的渠道；在购买方式、支付手段上也已 经非常成熟；同时由于是企业对企业的交易，不存在个人消费观念的障碍。而 b 2 b 在中国实现的难题主要在于企业间的信用。 ( 二) 企业与个人之f 刮( b 2 c ) ： 这是一种企业对消费者的经营模式，企业通过便利的购物渠道，向消费者提 供定制的产品与服务。这就是众所周知的互联网( i n t e m e t ) 。现在不仅仅可以通 过互联网购物，还可以根据个人不同的需求提供定制的产品和个性化的服务。 在早期多数的网站罩，包括门户网站，都采用了这种零售方式。因为，对于 门户网站而言，他们有丰富的客户群。而这些客户大多数又都是个人。b 2 c 是把 注意力转换为网站盈利的主要模式。这也证明了“眼球经济”或“注意力经济” 并非完全是泡沫。现阶段，b 2 c 的模式主要是靠网络公司任运作，不久的将来， 堡曼堕坠一 型：堡兰 那些传统的有较高信誉度、已经成为名牌的零售商贸企业也一定会参与b 2 c 的 行业中，比如北京的西单商场、翠微集团都在做这方面的努力。 这种零售的优势在于它采取了直销的方式，消除了若干中嵋j 环节，减少因为 中间环节而增加的消费品交易成本，使得消费者可以获得更优惠的价格。b 2 c 运 作的三大瓶颈包括：上网人数、网上支付和物流配送。其它还包括配送成本和个 人零售商品价值之间的比较，对商品质量的担一1 5 , ，对网上结算安全的担心等等。 ( 三) 个人与个人之f j ( c 2 c ) ： 这个模式的特点是消费者与消费者讨价还价。这种模式商业运作的最大难点 和问题在于个人信誉及信用监督的问题。因为这是一种投机性的交易形式，如果 没有很好的监督机制，多数拍卖就会演变成光打雷不下雨，等到达成致价格而 真正需要支付时购买方却销声匿迹了。因此，支持c 2 c 的电子商务网站除了建 立一个拍卖交易平台，让消费者相互去讨价还价，还需要建立第三方保证机制， 或者利用委托收款的方式代替保证机制( 雅宝网站采用的模式) ，来维持交易的 诚信。 拍卖交易平台通常完成这样的功能：以英式拍卖、集体议价、标价求购等多 种方式完成多客户类型、多交易形式、多拍卖品类型的交易过程，平台本身不直 接介入交易，只通过提供交易平台和相关服务，收取交易佣会。 同时，还可以利用a i 的技术来完成客户的竞价请求，也就是实现自动协商 过程。也就是利用计算机来完成客户的委托请求。 ( 四) 企业与政府之i n j ( b 2 g ) ： 企业对政府的电子商务模式。这种模式主要包括：一是政府通过网上服务， 为企业创造良好的电子商务空间，如网上办公、网上报税、网上报关、网上审批 等。二是政府上网采购，为企业提供大量的商机，如国家工程的竟标，如政府部 门大宗公共产品的采购等。 这种政府在网上发布信息，企业上网竞标的形式是一种透明度高的政府采购 行为，有利于减少离网采购中的“黑箱”操作。此外，b 2 g 有助于政府改进工商企 业管理模式，提高工商管理部门办事效率、促进政府机关勤政、廉政建设、维护 消费者的权益等等。 虽然电子商务模式本身不是我们讨论的重点，但是电子商务过程中，特别是 c 2 c 模式中的自动协商和协商支持过程都是论文研究的重点。我们更多的是希望 研究成果能够给电子商务的参与者提供协商过程的支持，包括协商模型的管理， 协商算法的研究，自动协商的实现等等。 1 2 2 电子商务交易的基本流程 参加交易的买卖双方在做好交易前的准备之后，通常都是根掘电子商务标准 规定丌展电子商务交易活动电子商务标准规定了f 乜子商务交易应遵循的基本程 三兰蔓丛至塑型兰旦坐堕皇坐坐些堑些! ! 尘：l 垫王塑堑主塑坐旦 竺! ：堡兰 序， 式应文本景应向式应文本背文向式应文本背研向式应文本背文向： i 客户方向供货方提出商品报价请求( r e q o t e ) ，晓明想购买的商品信息： 2 供货方向客户方回答该商品的报价( q u o t e s ) ，说明陔商品的报价信息： 3 客户方向供货方提出商品订购单( o r d e r s ) ，说明初步确定购买的商品 信息； 4 供货方向客户方对提出的商品订购单的应答( 0 r d e s p ) ，说明有无此商 品及规格型号、品种、质量等信息； 5 客户方根据应答提出是否对订购单有变更请求( 0 r d c h g ) ，说明最后确 定购买商品信息； 6 客户方向供货方提出商品运输说明( i f t m i n ) ，说明运输工具、交货地 点等信息； 7 供货方向客户方发出发货通知( b e s a d n ) ，说明运输公司、发货地点、 运输设备、包装等信息； 8 客户方向供货方发回收货通知( r e c a d v ) ，报告收货信息； 9 交易双方收发汇款通知( r e m a d v ) ，买方发出汇款通知，卖方报告收款 信息； 1 0 供货方向客户方发送电子发票( i n v o i c ) ，买方收到商品，卖方收到货 款并出具电子发票，完成全部交易。 1 3 分布式人工智能 “d a i 是a i 的一个子领域，它在多个层次上研究a i 中的并发性。一方面， 是分布式问题求解( d p s ，d i s t r i b u t e dp r o b l e ms o l v i n g ) ，它考虑怎样将一个特殊 问题求解工作分解到多个合作的、知识共享的模块或结点之问；另一方面，是多 主体系统( m a s ，m u l t i a g e n ts y s t e m ) ，在多主体系统中，主要的研究方面是一 组自治的智能主体之问智能的行为的协调。知识、规划、不同技能和自身动作的 协调是一个过程。”f b o n d & g a s s e r , 1 9 8 8 1 这是b o n d 和g a s s e r 对分布式人工智能的一段评论。这样d a i 被分解成两 个不同的领域。分布式人工智能的两个领域都要研究如何对知识、资源、控制等 进行划分，不同之处在于，在分布式问题求解中，我们常常有一个全局的概念模 型、全局的问题和全局的成功标准，而在m a s 中，我们有多个局部的概念模型、 问题和成功标准。在概念、模型、控制等方面这两种方法的视角是不一样的。分 布式问题求解的目标是要创建大粒度的协作群体，它们之问共同工作以对某一问 题进行求解。在一个纯粹的分布式问题求解系统中，问题被分解成任务，并且为 求解这些任务，需要仅为该问题设计一些专用的任务执行系统。所有的交互( 如 果有，如协作等) 策略都被集成为系统设计的整体部分。这是一种自顶向下设计 的系统，因为处理系统是为满足在顶部所给定的需求而设计的。而m a s 可看作 是自底向上的设计方法设计的系统。因为在原理上，分散自主的主体首先被定义， 然后研究怎样完成一个或几个实体的任务求解。主体之 j 可能是协作关系，也一，j 能存在着竞争、甚至是敌对的关系。 4 竺! 盟生 型堕兰 上面这种对分布式问题求解和多主体系统的区分强调了多主体系统巾各个 主体的控制上的分散性。另一种观点则认为m a s 基本等同于d a i ，分伟式问题 求解则是m a s 的子集。当m a s 满足下面三条假设时便成为分布式问题求解系 统：主体友好假设：共同目标假设；集中设计假设。这种观点实际卜将 m a s 的范围大大地扩大了。 由于m a s 更能体现人类的社会智能，具有更大的灵活性和适应性，更加适 合开放、动态的世界环境，因而更受到人们的重视。由于近年束i n t e r n e t 的迅猛 发展，m a s 的研究已不再局限于d a i 之中，甚至有人说在未来的m a s 固际会 议中，d a l 只是一个专题而已 d u r f e e e ta 1 ，1 9 9 4 1 。以前对于m a s 的研究主要是 从面向合作的视点出发考虑，现在则趋向于从单个智能主体的角度来考虑更一般 的问题，即主体应具有什么样的结构、能力才能在一个有限时帕j 约束、丌放的多 主体环境中自主地行动、决策以及与其它主体交流。关于智能主体、多主体系统 的研究己成为人工智能，甚至计算机科学的研究热点。 1 3 1 主体和多主体系统 主体以及多主体系统的研究是分布式人工智能研究的一个方向，分前i 式人上 智能( d i s t r i b u t e d a r t i f i c i a li n t e l l i g e n c e ，d a i ) 是人工智能和分布式计算的结合。分 布式人工智能研究的目标是要创建描述自然和社会系统精确的概念模型。在分布 式人工智能中，由于智能本质上不是一个独立存在的概念，而只能在团体中实现， 因此分布式人工智能研究感兴趣的主要是几个主体之间的合作、交互等方面。在 多主体系统中，主要研究一组自治的智能主体之阳j 智能行为的协调。 1 3 1 1 主体概念 目前，人们对主体的定义分歧很大。主体概念源于英语“a g e n t ”。a m e r i c a n h e r i t a g ed i c t i o n a r y 定义a g e n t 为“o n e a c t so rh a st h ep o w e ro r a u t h o r i t yt oa c t o r r e p r e s e n ta n o t h e r ”或者“m e a n sb y w h i c h s o m e t h i n g i sd o n eo rc a u s e d ；i n s t r u m e n t ”。 因此，“a g e n t ”这个词主要有三种涵义：一是指能对其行为负责的人；二是指能 够产生某种效果的，在物理、化学或生物意义上活跃的东西：三是指代理人，即 接受某人的委托并代表他行动的人。但是在d a l 研究中，不同的研究者从不f _ j 的角度对主体做出自己的解释。i n t e l l i g e n t a g e n t1 1 1 中列举了1 0 余种典型的定义。 甚至，对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 是可以互换的。相对而言，下面的软件主体的 定义也许很多m a s 研究者会接受：软件主体是“一个同其它主体和进程其处i 司 一个环境中的连续工作的自主的软件实体。” 在主体定义不能得到公认的情况下，可以通过描述：t 体的性质来刻画它。通 常认为一个主体或多或少拥有以下的部分或全部特性： ( 1 ) 自治性 j 二兰堂：i ! ! 笙! 塑坐堕塑望型型些! ! il ! ! 塑堑! 塑坐旦 ! 塑! ：堡墨 这是一个主体的基本特性，即可以控制它自身的行为。主体的自治体现在： 主体的行为应该是主动的、自发的；主体应该有它自己的目标或意图 ( i n t e n t i o n ) ；根据目标、环境等的要求，主体应该对自己的短期行为做出 计划。 ( 2 ) 交互性 即对环境的感知和影响。无论主体生存在现实的世界中( 如机器人、i n t er n e t 上的服务主体等) 还是虚拟的世界中( 如虚拟商场中的主体等) ，它们都应 该可以感知它们所处的环境，并通过行为改变环境。一个不能对环境做出反 应的物体不能被称为主体。 ( 3 ) 协作性 通常主体不是单独地存在，而是生存在一个有很多个主体的世界中。主体之 问的良好有效的协作可以大大提高整个多主体系统的性能。 ( 4 ) 可通信性 这也是一个主体的基本特性。所谓通讯，指主体之问可以进行信息交换。更 进一步，主体应该可以和人进行一定意义下的“会话”。任务的承接、多主 体的协作、协商等都以通讯为基础。 ( 5 ) 长寿性( 或时问连贯性) 传统程序由用户在需要时激活，不需要时或者运算结束后停止。主体与之不 同，它应该至少在“相当长”的时问内连续地运行。这虽然不是主体的必须 特性，但目前一般认为它是主体重要性质。 其它的特性还包括：移动性一一主体可以从一个地方移动到另一个地方而保 持其内部状态不变；推理能力一一主体可以根据其当前的知识和经验，以理性的、 可再生的方式推理或推测；规划能力一主体为了完成其目标可以综合和选择动 作的不同过程；学习和适应能力一一主体可以根据过去的经验积累知识，并且修 改其行为以适应新的环境。另外，有些学者还提出主体应该具有自适应性、个性 等特性。在实际的应用中，主体经常需要在时间和资源受到一定限制的情况下完 成一定的动作。所以，对于现实世界中的主体，除了应该具有主体的一般性质外， 还应该具有实时性。 可以通过对上面列出的一种或多种性质的组合对主体进行分类。例如，主体 可以被分为弱的和强的两类。拥有心智状态的主体被定义为强的。按照主体的问 题求解能力和思维状态，主体可以被分为反应主体( r e a c t i v ea g e n t ) 、认知主体 ( i n t e n t i o n a la g e n t ) 和社会主体。 i b m 发表的白皮书认为可以在自主性、智能性和移动性这三维构成的空删米 描述智能主体，如图1 所示。自主性反映了主体的自治和权利，可以用主体和系 统中其它实体交互的性质来衡量。最起码，主体必须异步运行：如果主体可以代 表用户，那么它拥有更多的自主性；更为自主的主体可以同其它主体进行数据、 6 生里型l _ 一业堡兰 应用和服务级别的交互。钨- r z 日匕, 。性由主体的推理和学习能力衡量。最低级的智能性 表现在主体是有偏好的，而有学习和适应能力的主体是最为智能的。主体的移动 性表现为主体在网络上的漫游能力。具有移动性的主体一般叫做移动主体。 图1 智能主体的臼土性、智能性和移动性构成的空问( 源白：g i l b e r te ta 1 1 9 9 5 ) 1 3 1 2 多主体系统 多主体系统( m a s ，m u l t i a g e n ts y s t e m ) 是一组松散耦合的问题求解单元， 它们共同解决那些超越它们自身能力的问题 1 3 1 。更具体一些，多主体系统是由 一组彼此间存在着协调、协作或竞争关系的主体组成的系统，多主体系统试图用 主体来模拟人的理性行为，通过描述主体之间理性交互而不是事先给定的算法来 刻画一个系统。多主体系统涉及很多的交叉学科，包括人工智能、分布式计算、 自然语言处理、社会科学、组织科学、经济学和哲学等。自9 0 年代以来，m a s 就已成为计算机科学和人工智能领域研究的热点。同时对多主体系统的研究趋向 于从单个智能主体的角度来考虑更一般的问题，即主体应具有什么样的结构、能 力才能在一个有限时间约束、开放的多主体环境中自主的行动、决策以及与其他 主体交流。 多主体系统是当今非常活跃的研究领域。多主体系统试图用主体来模拟人的 理性行为，使其更加符合人和人类社会本身的情况。研究人员将很多社会学、经 济学、管理科学中的理论和方法引入到多主体系统的研究中，并取得了良好的效 果。 多主体系统关心的是一组已存在的自主主体的全局性行为，并以此来求解给 定的问题。可以将一个多主体系统看成是一个由问题求解器构成的松散耦合网 络，这些问题求解器由于能力或知识的不足，而与其它问题求解器一起工作以便 求解整个问题。这些具有自主性的问题求解器就是所谓的主体。在多主体系统t h 每个主体对全局的认识是片面的，系统中既没有全局的控制者，也没有集中的数 据，主体j 、日j 的计算行为是异步的。和分布式问题求解( d p s ) 相比，多主体系统 解决问题过程是从下而上的求解过程，因此主体问的协作、协调、和协商是多主 体系统所面临的最大困难和挑战。 j 三苎竺至堡壁曼竺型堕业型! 丝! ! 生! ! ! 塑箜! 塑坐旦 ! 坐! 垦墨 在多主体系统中，单个主体可能由于所掌握的信息不够完整，也可能由于能 力或资源不够的缘故，无法独立完成某项任务，这时主体必须与其他主体进行协 作，主体之问在能力上、资源上相互支持，以最终实现系统目标。 目前关于多主体系统的研究主要集中在如下几方面：主体和多主体的理论、 主体的体系结构和组织、主体语言、主体之间的协作和协调、通信和交互技术、 多主体学习以及多主体系统应用等。关于多主体系统的应用已经有人做了许多工 作甚至应用于一些大型、复杂的系统。例如机场管理、自动驾驶、高级机器人 系统、分布式电力管理、信息检索等。 1 3 1 3 多主体系统中的协商 当采用面向主体的计算范型，自然会需要面对多主体的问题；如描述那些非 集中的分布问题，不同地点的控制问题，多概念或竞争问题。更多的时候，主体 是需要和其他主体交互的，既要完成它们各自的目标，也需要处理在公共环境中 所具备的依赖关系【l o 1 4 4 1 ，这些交互都不同于简单的信息交互，都需要通过特 定的动作完成协作( 完成共同的目标) 和协调( 用一致的行为规范安排行动的顺 序，资源的使用) 。要求实时管理主体之间的依赖关系，最基本的最有用的 机制协商( 主体之间在一些问题上达到互相都能够接受的协议) ，协商是协 作和协调( 机机，人机) 的基础，不论主体是自私的还是合作的。这一 点是至关重要的，因为主体是自主的。当主体需要影响其他熟人的时候，它必须 确认熟人能够按照预定的方式工作。要达到这样的目的必须能够提出计划，交易 条件，给予必要的让步，有达成最后协议的意愿。简而言之，就是需要协商。 多主体之间的协商是多个主体为就某些事件达成互相能够接受的协议而进 行的一种通信过程。在多主体系统中，协商的含意有多种理解。一种认为子问题 和资源的指派是协商。另一种则认为主体之间一对一直接协商。所有协商活动的 目的是在一组独立工作的主体问构建协作，主体也有自己的目标。协商协议提供 可能的协商形式的基本规则、协商过程和通信基础。协商策略取决于具体的主体。 尽管主体开发者可以提供不同程度的协商能力，但是一定要保证协议与策略相匹 配，即选择的策略要在可用的协议中能执行。 从单个主体看，协商的目的是改善自己的状态，在不影响自己情况下支持其 它主体，或者对其它主体请求帮助。主体必须进行折衷，维护整个系统的能力。 在这种意义上，协商交互的形式可以分成倍增长类： ( 1 )对称协作。 协商产生的结果，对每个主体都比它们原来达到的好。其它主体对主体本身 的影响是积极的。 ( 2 )对称折衷。 主体宁可自己独立达到它们的目标。 果。但是不能忽略其它j i 体的存在， 协商意味着参加者之间的折衷，降低效 只能采取折衷，i l ：参加者都能接受协商 竺塑 盟笙墨 的结果。 ( 3 ) 非对称协作折衷。 即对协商的一个主体协作的影响是积极的，而对另一个主体必须进行折衷。 ( 4 ) 冲突。 由于主体的目标彼此冲突，不能达到可接受的解。在得到结果前协商必须终 止。 协商在很多领域的重要性，协商理论还包括了很多情况，涉及很多学科( 社 会学，人工智能，博弈论) 。概括起来，自动协商理论涉及以下三个主要的领域： ( 1 】详细的分类) ：协商协议、协商对象、决策支持模型。而这三方面的重要性 取决于协商本身和环境的不同。对协商问题的研究涉及很多领域，如社会福利理 论，社会心理学，经济学，市场学，组织理论，运筹学和分布式人工智能。而以 往的分布式人工智能研究中主要有基于博弈论的协商，启发式的协商，让步策略 的协商，基于辩论的协商等等。 1 4 虚拟市场应用背景 主体技术快速发展的一个主要原因是i n t e r n e t 和w e b 的广泛的普及和增加。 主体技术在i n t e r n e t 上的主要应用有信息处理和电子商务中的谈判等。智能主体 可以根据用户的兴趣对w e b 上的信息进行检索、分析、过滤和分类，解决i n t e r n e t 带来的信息超载，使人们从纷繁的信息海洋中解放出来。将主体技术应用到电子 商务系统中，主要有以下功能：买方主体可以帮助客户选择商品、选择卖方以及 与卖方协商价格等；卖方主体可以帮助商家提供商品信息、选择买方以及与买方 协商价格等。主体作为买卖双方的中介，充分体现了它在自主性、个性化和长寿 性方面的优势。 电子商务是多主体系统的一个重要的应用领域。一个开放的电子商务系统 中，在由不同单位设计的交易的各方之间，进行互操作需要有共同的本体，通信 语言和交互协议。面向主体的技术在这方面有一定的优势。采用主体通信语言如 k q m l 和f i p a 的多主体系统将很好地胜任在多个交易主体之间交互的任务。按 照信息经济学的理论，商务活动和市场行为可以被归结于信息市场中进行信息搜 索，并在不确定情况下做出选择的行动。这可以看作理性主体在多主体系统中按 照对策论和效用理论做出最大化自己的利益的一种实际情况。约束满足理论和信 息收集和过滤技术也方便了主体的信息获取。同样在电子商务中，通过协商贸易 的各方最终形成各方都满意交易合同。m a s 中的c n p 和各种拍卖协议可以直接 应用在电子商务中去。 1 4 1 原型系统介绍 主体技术被认为是处理电子商务中海量信息的关键技术之。作为一段个阡 9 多主体系统中的协商问题训究歧j nl ur 向务中的心用 坝i 论文 化的、能持续生存的和具有某种自主特性的特殊程序，它们能够帮助甚至替代人 来处理商务信息。在美国副总统1 9 9 9 年初签署的一份关于2 1 世纪的i t 技术的 报告中，它被列为2 1 世纪i t 领域的关键技术之一。基于智能主体的电子商务是 目前分布智能和电子商务最活跃的研究领域。包括m i t 媒体实验室、c m u 机器 人实验室在内的数家美国最著名的大学都有专门的研究小组，比较著名的原型系 统包括p e r s o n a l o g i c ，f i r e f l y ，b a r g a i nf i n d e r ，j a n g o ，k a s b a h ，a u c t i o nb o t ，以 及t t 等。 k a s b a | l 是美国m i t 大学丌发的基于多主体的电子商务系统。用户可以生成 b u y e r a g e n t 或s e l l e r a g e n t 来帮助他们进行商业交易。一个用户如果想购买( 销 售) 他的商品，则向系统申请一个主体，给出简单的策略描述。然后将它们送入 以主体为中心的市场。每个主体按照委托人所给出的约束( 最初价、最低价、最 高价、交易时间等) 进行协商。系统提供了焦急型、冷静型、节约型等三种协商 策略。这三种策略分别对应于线性函数、平方函数和指数函数三种曲线。k a s b a h 是一个单纯就价格进行协商的系统。它也存在单一因素协商的系统所共有的问 题：不利于商业交易的良性循环。 t e t e a t e t e 是美国m i t 大学另一个电子商务协商支持系统。它提供了对零售 交易形式的协商。它是针对多个因素进行协商的良性交易系统。它要求用户将自 己在每个因素上的效用函数表达给系统，系统从中寻求双赢的交易方案。 p e r s o n a l o g i c 引导用户在巨大的产品特征空间中选择出最符合他们需要的产 品。系统通过在一个给定领域中对产品特征加入约束来过滤出不符合要求的产 品。约束满足引擎返回一个满足所有的“硬”约束并按“软”约束满足度排序的 列表。 类似p e r s o n a l o g i c ( p e r s o n a l o g i c ) ，f i r e f l y ( f i r e f l y ) 也可以帮助用户选择产 品( s h a r d a n a n d & m a e s ，1 9 9 5 ) 。但是，f i r e f l y 并非基于特征进行过滤，而是通 过自动协作过滤( a u t o m a t e dc o l l a b o r a t i v ef i l t e r i n g ，a c f ) 这种商品推荐机制来 选择产品。a c f 首先比较某个购买者( 和其它购买者) 的商品选择。在找出这 个购买者的“最近邻居”( 即，有相同购物口味的用户) 后，a c f 推荐那些“邻 居”高度选择但这个购买者还没有购进的商品，从而使这个购买者可以得到意外 的发现。本质上，f i r e f l y 是用想法相近的人群的意见来推荐商品。目i j ，所推荐 的产品主要有音乐和书籍类。 a n d e r s o nc o n s u l t i n g 的b a r g a i nf i n d e r ( b f ) 是第一个进行在线价格比较的导 购主体。在给出一个商品后，b a r g a i n f i n d e r 用来自同一个浏览器的相同请求向9 个不同的厂商的站点索取价格。虽然，它只是一个功能有限的概念系统，b a r g a i n f i n d e r 对在线世界的价格比较还是提供了足够的启示。例如，它可以访问到的1 3 的在线c d 商家封锁了对它的所有的价格请求。一个根本的原因在于商家不想单 独地进行价格的比较。单独的价格比较忽略了他们在w e b 上提供的增值服务。 这样的话，顾客的购买决策也不会考虑这些因素。然而，有同样多的不出名的商 家却希望a n d e r s o nc o n s u l t i n g 把他们加入b a r g a i nf i n d e r 的价格比较列表中，这 说明了不同公司在价格比较方面的不同取向。 0 堡里塑l 一 业堡兰 j a n g o j a n g o 】可以被视为更为先进的b a r g a i nf i n d e r ( d o o r e n b o se ta l 。1 9 9 7 ) 。 j a n g o 的最初版本是为了解决公司封锁价格问题而设计的。j a n g o 中的商品请求 是源于每个消费者的w e b 浏览器而非象b a r g a i nf i n d e r 那样出自统一的中央站 点。采用j a n g o 的p l u g i n 的w e b 浏览器后，请求可以和“真f ”的顾客发出的 一模一样。这样的“主动式互操作”使消费者可以方便地挑选商品但是并未给商 家制造太多的麻烦。只要厂商提供了公共的在线分类目录，不论它们愿意与否， 这些目录都可以被主体访问。j a n g o 的运算方法很简单：一旦购买者选出一种商 品后，j a n g o 同时查询不同的厂商的站点( 地址保存在e x c i t ei n c 维护的一个地 址列表中) 的价格，结果被用户用来比较它们的出价。 a u c t i o n b o t a u c t i o n 是密歇根大学的一个通用i n t e r n e t 拍卖站点( w u r m a n e ta l ， 1 9 9 8 ) 。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 和其它拍卖站点的不同在于它给用户提供 编程接口( a p i ) 来创建自己的软件主体来自主地再a u c t i o n b o t 市场中竞标。在 f i s h m a r k e tp r o j e c t f i s h m a r k e t 】( r o d r i q u e ze ta 1 ，1 9 9 7 ) 中，用户要自己来编写他 们自己的投标策略，f i s h m a r k e t 目前并非一个实用的系统，然而它被用来举办竞 标策略比较的锦标赛( r o d r i q u e z e ta 1 1 9 9 8 ) 。 西班牙科学研究院的m a t o s 和英国伦敦大学的j e n n i n g s 利用进化计算对主体 协商进行了联合研究。他们在已获取效用函数的基础上为用户