（计算机应用技术专业论文）基于agent的多单位组合拍卖研究.pdf

中文摘要 基于a g e n t 的多单位组合拍卖研究 学科专业：计算机应用技术研究方向：人工智能 指导老师：张自力教授研究生：柏寰( 2 0 0 2 4 8 1 ) 中文摘要 在进行多a g e n t 系统中具有互补性或可替换性关系的多个资源与任务分派 时，人们通常选择使用组合拍卖村t n 来完成这样的分派工作。由于组合拍卖的竞 价方式能够更好表达竞价a g e n t 对资源或任务之间互补性与替代性等关系的偏 好，能够使得对多个资源与任务的分派工作高效率、高效用地进行，因此该拍卖 方式在众多资源与任务分派领域有着巨大的应用潜力，吸引了大量经济学、计算 机科学、系统工程学等领域学者对其进行研究。但组合拍卖中的胜者确定问题却 是一个n p 完全问题，而设置保留价的多单位组合拍卖中胜者确定问题是一个更 复杂的计算问题。据我们所知，设置保留价的多单位组合拍卖中胜者确定问题少 有学者对其问津。 本文讨论了在多单位组合拍卖机制中能够通过设置保留价，来防范该拍卖中 由于竞价a g e n t 共谋与竞标竞争不充分给拍卖a g e n t 带来的收益损失。同时，对 在设置了保留价后的多单位组合拍卖中如何选择胜出竞标来提升拍卖a g e n t 的 利润收益进行了研究。并基于s a i i d h o l m 的研究成果，提出了解决设置保留价的 多单位组合拍卖胜者确定问题的算法m u c a i 冲，该算法中有效的启发函数 设计让算法在解决胜者确定问题时效率得以提高。实验结果表明，在考虑资源保 留价的多单位组合拍卖中，拍卖a g e n t 能够利用m u c a r p 算法在一定问题规模 内快速地找到胜者确定问题的最优解，并使得拍卖a g e n t 利润收益得到提升。该 研究为在多a g e n t 系统、网格计算、电子商务等领域运用设置保留价的多单位组 合拍卖机制进行资源与任务分派提供了可能。 关锺女头多a g e n t 系统；资源与任务分派；电子商务：协商；拍卖；组合拍 卖；多单位组合拍卖；保留价；胜者确定问题 英文摘要 r e s e a r c ho fm u l t i - u n i tc o m b i n a t o r i a l a u c t i o n sb a s e do n a g e n t m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y d 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 ：z h a n g z i l ia u t h o r ：b a ih u a n ( 2 0 0 2 4 81 ) a b s t r a c t c o m b i n a t o r i a l a u c t i o n sc a l lb eu s e dt or e a c he f f i e i e n t r e s o u r c ea n dt a s k a l l o c a t i o n si n m u l t i a g e n ts y s t e m s w h e r et h ei t e m sa r e c o m p l e m e n t a r y o r s u b s t i t u t a b l e d u et ot h ew e l l e x p r e s s i o n o f c o m p l e m e n t a r y o rs u b s t i t u t a b l e ， c o m b i n a t o r i a la u c t i o nh a sa t t r a c t e dm a n ya t t e n t i o n so fr e s e a r c h e r sf r o me c o n o m i c s ， c o m p u t e ra n dc a g i n e e r i n gs c i e n c e d e t e r m i n i n g t h ew i n n e r si nc o m b i n a t o r i a la u c t i o n i sn p c o m p l e t ep r o b l e m ，a n dt h ew i n n e rd e t e r m i n a t i o ni nm u l t i u n i tc o m b i n a t o r i a l a u c t i o n sw i t hr e s e r v ep r i c e si sam o r ei n t r a c t a b l eo n e t oo u r k n o w l e d g e ，t h er e s e a r c h i n t om u l t i - u n i tc o m b i n a t o r i a la u c t i o n sw i t hr e s e r v ep r i c e sc o n s i d e r e di sm o r eo rl e s s i g n o r e d w eh a v ed i s c u s s e dh o wt oa v o i di n c o m el o s i n gb yu s i n gr e s e r v ep r i c e si n m u l t i - u n i tc o m b i n a t o r i a la u c t i o n s ，w h i c hi sd u et ot h ec o l l u s i o na n di n s u f f i c i e n t c o m p e t i t i o ni nt h ea u c t i o n s a n dw e r e s e a r c hi n t oh o wt oi n c r e a s ep r o f i t si n c o m eb y u s i n gr e s e r v ep r i c e s 。an e wa l g o r i t h mf o rm u l t i - u n i tc o m b i n a t o r i a la u c t i o n sw i t h r e s e r v e p r i c e si sp r o p o s e d ，w h i c h i sb a s e do ns a n d h o l m sw o r k a ne f f i c i e n th e u r i s t i c f u n c t i o ni sd e v e l o p e df o rt h en e w a l g o r i t h m e x p e r i m e n t sh a v e b e e nc o n d u c t e d t h e e x p e r i m e n t a l r e s u l t ss h o wt h a ta u c t i o n e e r a g e n t c a l lf i n dt h e o p t i m a l s o l u t i o n e f f i c i e n t l y a n dc a l l i m p r o v ep r o f i t i n c o m ew i t l lo u ra l g o r i t h mi nt h em u l t i u n i t c o m b i n a t o r i a la u c t i o n sw i t hr e s e r v ep r i c e sf o rl i m i t e dp r o b l e ms c a l e s t h er e s u l to f o u rr e s e a r c hp r o v i d e st h ep o s s i b i l i t yt oc a r r yt h em u l t i u n i tc o m b i n a t o r i a la u c t i o n s w i 龟r e s e r v ep r i c e si n t oe x e c u t i o n si nr e s o u r c ea n dt a s ka l l o c a t i o nf i e l d ss u c ha s m u l t i a g e n ts y s t e m s ，e c o m m e r c e a n dg r i d c o m p u t i n g k e y w o r d s ：m u l t i - a g e n ts y s t e m s ；r e s o u r c ea n dt a s ka l l o c a t i o n ；e - c o m m e r c e ； n e g o t i a t i o n ；a u c t i o n ；c o m b i n a t o r i a la u c t i o n ；m u l t i * u n i t c o m b i n a t o r i a la u c t i o n ； r e s e r v e p r i c e ；w i n n e r d e t e r m i n a t i o n p r o b l e m 第一章引言第1 页 第一章引言 经济活动的本质是利用有限资源满足人们的无限需求，而经济机制则决定资源与任务如何 在经济活动中进行分派。市场机制是实现资源与任务分派的有效方法，而协商则是市场机制中最 重要也是最消耗时间的一个环节，拍卖机制则是协商机制中晟常见、高效的一种方式。 现今电子商务中，各种有关资源与任务分派的协商活动大多数仍然由人力来完成，人力协 商由于受到如风俗文化、自我主义和自尊等因素的影响从而存在很多缺陷，并且人力协商很难得 到协商的晟优解它难以实现需要大量计算的协商方式。 近年来，由于分布式人工智能( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ) 技术的发展，使得把由软 件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 ”。 组合拍卖是可以让竞价a g e n t 把多种“标的”捆绑在一个竞标中竟价的拍卖方式。由于组 合拍卖的竞价方式能够更好地表达竞价a g e n t 对资源或任务之间g * b 性与替代性关系的偏好，可 以使得资源与任务的分派高效率、高效用地进行，因此该拍卖方式在资源与任务分派领域有着巨 大的应用潜力。近年来，大量经济学、计算机科学、对策论等领域学者进行了组合拍卖机制的研 究与实现，但组合拍卖中更具有广泛应用意义的多单位组合拍卖机制的研究却相对较弱，该领域 存在许多亟待解决的问题。本文将针对在多单位组合拍卖中引入设置保留价的拍卖机制进行研究 与算法设计。 1 1 组合拍卖 拍卖规则的分类方法有很多。按照拍卖物品的多少，可分为单一物品拍卖和组合拍卖，传 统的拍卖方法均为单一物品拍卖。由于各种拍卖的物品之闻存在互补性和替换性，使得买方对两 个物品的评价一般不等于对这两个物品分别评价的和这使得单一拍卖难以达到拍卖的总效用最 髂一章弓i 亩颦2 蕞 臻合掐黉( c o m b i n a t o r i a la u c t i o n s ) 氆禳为箍绑拍卖( b 黼d l e a u c t i o n s ) 戚打包拍卖( p a c k a g e a u c t i o n s ) 怒巍价a g e n tw 以把多种“标的”在一个竟标中米进行捆绑党价的拍卖方式。当竞价 a g e n t 对“橼缝”靛互 性与饕代戆等关蕊帮壤爵l 蕈，缝台攘卖熊够充努袭这竟徐a g e n t 黠“拣 舶”翡偏好使得拍卖更加离散、使捷地避章予。同时，缀合拍寨中的胜者蔽定既尊重买方i 勺嘲价， 又可以使嶷方获得最大的利箍，从而使拍冀总效用最大化。 经台撼囊概裁魏蟛被藏爝在众雾经济领蠛孛。这些赣域售捂：逶谶频段拍卖【l 】，会 筝援划 【2 】，b u s i n e s st ob u s i n e s s 谈判【3 】，运输撇务【4 】，资源谢魔f 5 】。剜车调穗f 6 】 飞机场越落时 段分派【7 】，供应链的形成f 8 】，以及电予购物【9 】。这些缀济问磁的实质都是解决组含资滞如何 势濂豹褥越。 一般掰讨论的组台捆鬓如聚没肖碉确指幂，都魑指单单位缌拍安( s i n g l e u n i t c o m b i n a t o r i a la u c t i o n s ) 。在诚组合拍卖中供拍卖的“橼的”种类为多个，但每种“标的”可供 接卖豹数量却鬟舂一个。多攀接缀会拍囊搬剿( m u l t i - u n i tc o m b i n a t o r i a la u c t i o n s ) 是程撩娄孛， 除了“标的”种类可以为多个外，每种“标鹃”可供拍爨的数量述可戳夫予1 。多单位缀台拍卖 是更舆有一般意义的组合拍卖方式，单单位组台拍嶷可以糟成多单位组台拍囊的一个特例( 每种 “拣瓣”可供撼囊静数量郡等孳：1 ) 。多擎经缝台拍卖是耱瘫维畿的缀会糖寨f 4 7 】，它瓣糖在电 子商努、阐格计算与工程管理等领域有着广泛的应宿【4 4 】。 1 2 基予多a g e n t 系统鹩缀合接卖 多a g e n t 燕统技术是孟匿年来分鸯式a 互嚣能领域磷巍静热点，冀技术醚磅究与巍蠲蕊丽酌 扩大 l 露鑫越娥熬。我 f 】可以铡瓣多a g e n t 襞统技术寒窭现缀含始卖撬胄拄经济赣域中的艘港；两 酵，褒可敬鹊瓣缀台撩霎撬涮采进行多a g e n t 幕统串瓣缀食赉潦与鳃合任务在a g e n t 之闻簸瘫彀 癸派。 遴过这蹰方夏孵结台磷巍既霉戮让维套拍卖檄好避勰决窦际的经济斑翔颁域审静缀套撩源 静嚣瓣惩，叉麓捉遴雾a g e n t 系统孛缍台资源分滠罨篷会程务援戴靛研究。 1 。3 继食拍卖中的胜者确定问题 在多a g e n t 系统或经济领域都面以通过缎合拍卖机制高效地完成组合资源与任务的分派工 作。但组合捆嘉中的胜者确定问题( w i n n e rd e t e r m i n a t i o np r o b l e m ，w d p ) 却是一个n p 完垒问 第一擘葶l 喜荼3 熨 瓣【3 0 j 。鳓疵媛；l 了众多领域学者对其进行研究f 1 - 9 1c 2 9 - 5 8 】【6 2 】。 为了受瀵楚蜷浚鹗壤会鹁黉串魏黢赣确是瓣蹶，夸擎肇凌缀合籀卖串齄舞藏宠瓣瑟豹实 搠描述魏f ： 假镟桶卖a g e n t 将拍襄3 种资源：丸b ，c 。拍卖a g e n t 收刘的竞价a g e n t 报出的谢效竟价如 。f 衰； ， l abca ba cb ea b e ia g e n t l $ 1 2$ 0霉1 8s 01 3 2$ 0 $ 4 2 |a g e n t 2 $ 1 3$ 1 3$ 1 3$ 2 8$ 2 8$ 2 8$ 4 4 a g e n t 3 $ 1 3 $ 1 4 $ 0 $ 2 2 $ o$ o$ 4 5 寝i - 1缎赍拍卖竟檬数据赛锕 籀委a g e n t 将黄巍挑选氆镰耱撮徐缀合中擐礁最懑妁竟掭。然麓褥逶避驻者确定篝洼寒薅 逡胜臻竞瓣a 在该实例争，妇象掐卖a g e n t 把a 、c 分漾给a g e n t l ，b 分派焓a g e n t 3 ，将获得 最天投薤$ 4 6 。 当要按囊鲍瓷滚蠢戥势辩，可莪弱努派缨台壤嚣魏f 强： 强1 - 1 爱箨静穰踅台墅两校举嘲有两种赞谭舯) 盎隧可见，攀单位鳃含拍卖中蓬者确建离趱翦复杂健将熬喾被绍褰燮瀵数量鼹嵫妖两惫捌 上升。s a n d h o l m 惑经诞鹳了确定胜者翔鞭爵戬辩纷奔繁袄分毯离题( w e j 睁t e ds e tp a c k i n g ) ，其 分溅方寨穷攀鼗为第二粪簌特接数 3 0 1 ，假凌燕巾蘩豢串，被拍卖资源种类散为掰臻么可隧 出瑷斡觉括静类数璧上隈舞2 ”- 1 ；嚣搿缝魏竟掭分滋方囊为鹾瑰“2 ) 每o ( m 8 ) 【3 璐。 多革钽缀合掐卖中的麟者确邂问裁照然是一个更复杂的n p 完全闯题 4 7 1 。该蝴越可以蝴终 第一章引言第4 页 为带权的多分包问题( w e i g h t e d m u l t i s e tp a c k l n g ) 【4 2 ，它同样吸引了众多领域的学者对其进行 研究【3 l 】 4 2 - 4 9 5 7 。 1 4 本文研究内容及贡献 在拍卖中，如果拍卖a g e n t 能对“标的”设置保留价( r e s e r v ep r i c e ) ，那么就可以有效防 i p 拍卖中的竞价a g e n t 共谋( c o l l u s i o n ) 发生和由于竞标竞争不充分给拍卖a g e n t 带来的收益损 失，并且还可以在确定竞标胜者时通过保留价来进一步提高拍卖a g e n t 的收益 5 9 1 。在多单位组 合拍卖机制中设置保留价，同样也可以达到上述效果。但是，很少有相关学者对在多单位组合拍 卖中设置保留价的拍卖机制其进行系统研究，只在最近的一些经济文献中有所提及【4 9 】。因此。 本文将对设置保留价的多单位组合拍卖机制进行讨论并设计相府算法来解决该拍卖机制中的胜 者确定问题。 本文的研究内容为在基j 二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 u c a r p ，完成了该算法的程序实现与实验数据生成器的 殴计。实验结果表明，在考虑“标的”保留价的多单位组合拍卖中，拍卖a g e n t 能利用m u c a r p 算法能够在一定范围内快速、准确地找到胜者确定问题的最优解，使得拍卖a g e n t 的利润收益得 到最大化。该研究成果为在电子商务、网格计算与工程管理等领域广泛使用设置保留价的多单位 组合拍卖机制进行资源与任务分派提供了可能。 1 5本文的组织 论文的内容安排如下：第二章，对本论文所涉及的相关理论与研究现状作介绍；第三章， 探讨了设置保留价的多单位组合拍卖机制的实现意义，并提出解决该机制中胜者确定问题的算法 与算法设计策略分析；第四章，通过设计模拟实验数据验证了在多单位组合拍卖中进行保留价 的设置，对拍卖a g e n t 利润收益的提升性，并进行了最终的算法设计方案与其他算法设计方案的 对比分析，验证了算法的相对高效性；最后对未来研究做展望。 第二章相关理论与文献综述第5 负 第二章相关理论与文献综述 2 1市场机制与拍卖相关知识 对市场中的协商来说通常都只有两方参加卖方和买方。但由于市场的不同，每一方 的个体个数也都不相同，针对不同的情况所采用的协商方法也不尽相同。经济环境中有不同的经 济个体在一个市场中交互。市场规定了经济个体在其中可以采取的动作，根据市场规则，市场系 统中备经济个体动作的组合产生经济结果。如果市场中的每个经济个体拥有有限资源，并且每个 经济个体都对其他资源有自己特殊的偏好，这可看作是一个资源再分派问题。资源分派问题是经 济学中的核心问题。市场机制是一种将经济个体的动作和信息映射到资源分派解决方法的一种协 议。 市场机制能够让市场中每一种资源被赋予一个价格。价格是一个非负实数，代表资源在市 场中的交换价值。经济个体根据资源价格做理性决定来竞争资源。经济学中有关于市场结构和与 之相芙的价格决定机制的火超理论。表2 - l 给 _ _ j 了+ 个微观经济形态学的市场结构表，如表所示 的市场结构是按照卖、买方双方参与市场的个体数目来划分。 泌 一个多个 一个一对一协商正向拍卖 多个反向拍卖双向拍卖 表2 - 1市场结构表 在上表中，我们看到拍卖机制是市场结构形成的主要机制。传统狭义的“拍卖”概念等同 于这里的正向拍卖。这里对广义的拍卖做出定义：拍卖是通过一系列明确的规则与买者或者卖者 竞价所决定的价格来决定资源配置的一种市场机制；即在确定的时间和地点通过一定的组织机 构，以公开或密封竞价的形式，将特定物品或财产权利转让给最高或最低应价者的买卖方式。 拍卖这种特殊的交易方式作为市场价格机制的重要组成部分它具有其他买卖形式不可替 代的功能，除了揭示信息、发现价格这一基本功能外，还可以减少代理成本：稳定市场价格，防 止欺行霸市；加速商品流转，减少资金沉淀；有利于配合司法仲裁( 如抵押或破产处理) ；获得 更多的市场信息。 这里对表2 - 1 中涉及的几种拍卖方式作一介绍。 正向拍卖( f o r w a r da u c t i o n ) 为一个卖方多个买方的拍卖形式，卖方将选择出价最高的买 蘩二章相关壤谂与文歉综述豁6 炙 方徉为物翮或财产权利转让脊。该拍卖多用予稀缺资源竟买戚抵押、破产、- 溉剩资产处理巾，它 缝帮勃卖方在掏卖凳债中去发现资源真实诱格潮稀缺程度，潞兔交易鲍主躐隧意性，甏童接地发 歇市晒需求，最终实现蔼晶昀媛大侨佳。 反向拍卖( r e v e r s ea u c t i o n s ) 也称为榴标是一个炎方多个卖方的拍冀烨式，买方将选 择掇徐最低的爨方律为狲瓷或服务供应方。该拍冀多用予企l k 或鼓府袋购物资朝驻务招标，是电 子商务中b 2 b ( b u s i n e s st ob u s i n e s s ) 每b 2 g ( b u s i n e s st og o v e r n m e n t ) 黥主要燮易攘式， 谨能帮助买方降低采购成本，杜绝采购腐败现象。 双向籀卖( d o u b l ea u c t i o n s ) 也髂为交换( e x c h a n g e s ) ，是有多个擞家和多个卖家嗣时 囱拍囊员道交巍标价格秘竞标数壁静拍凄形式。拍卖员把卖家的蘩约( 飙一个低价开始t 辩) 释 辫家的要约( 从个高价开始f 降) 进行匹献+ 首到要约提出的所有出售数壤都宾给了买窳。该 撩囊方式多孀予毅禁、期货等盘融巍品交易以获供应链的形成。 一个典型的拍羹主要包括四个露索；参与辔、“标静”、裁靛醢数和i 珏价策略。参与嚣毽 艚党买人、委托入和拍卖人。“标的”可以分为单物品和多物品，单物品拍襄中的“标的”是指 孽个不可分的：雾物品拍褰中麴多个“稼的”密嗣葳和不嗣壤之势。收藏函数涉及至l 鸯美“梅的” 移交时在经济土支付的一些判定，例如股者确定规测，最终簧让债格和买受入，“标的”嵛无保 留价格，以及熟它的参与成本。出价策略是揩竞买人如何估价和出价。 传统麓拍爨冒以分残如f 熬靼粪： 1 ) 蹭价籀冀也称荚式獭卖。在该箍囊中，竟侨入哪一个眈靛一个爨价更离的价格，嵩到 没有人出更高的价格为l t 。荑式拍裳是开放戏拍卖斌开放出价( o p e nc r y ) 的拍卖。荚式拍卖在 骞些慎况下会霄拍卖起蹬残像整玲掇。魏果没鸯a 出徐瘫予保整赞掊，那么掏卖靛终止，这样裁 不会圆为哇l 价过低给卖方造成损失。 英式拍疯谢种变种叫艇武拍实，在遮种情况下，每种“标的”都育报多数量，允许党价 太指定贿娄的数量，竟赞最离鹣入褥到了俄想簧翡数量，翔浆“撂静”终了蠢後最离的人媛还舂 剩余，那么就抱剩下的“标的”给竟侨次高孵人，以此娄撵藏到所有的“栎的”酆分派竞魏止， 所有成功的竟价人都得到了他想要的数懿倪他们只需要按成功竟价人中出的最低价来付款。 2 ) 减赞糖豢凌嚣为蕊慧式接卖，选种方式超源予旖兰入拍囊栗蔬秘鳞拢孵所馊翅魏方法。 荷兰式拍卖的拍囊人从一个高价开始降债，一鲞降剥有竟价人愿意接受为斑。在犬多数的旖兰式 拍卖中，卖方撼供大摄的同样物品供出售。荷兰式拍卖常常隳用一个钟表，价格随着袭的怒动而 f 辫，第一令州捧豹入裁成了拯卖的魅剩案，镌毒骧按这巾纷猿熬买毽援嚣簧鳖静囊燕，如累“掾 的”还有剩余拍卖将继续：避e 行。点到所有的“标的”都艘鬻走。 第二章糖关理论与文献综述第7 页 3 ) 第一价格密封竟价拍卖密封竞价拍卖是与上谢两种开放式拍爨相对的拍卖方式，竞价 太渡密封瓣蠢式递交丞毫熬密徐。窭徐燕绦密熬，其鸯巍徐天帮拍卖入鳃遵窭竣豹其体数毽，窭 价最高的人获得物品。 4 ) 第二价格密封拍疯又称为v i c k r e y 拍卖，是程密封竞价拍赏中，卖方将物品以拍卖中 第二离瓣巍徐将物瑟卖绘蕤者( 窭蛰最巍豹竞徐夭) 。巍这群豹接卖中，竞徐a g e n t 将接臻自己 的心理价位诚实出价。经济学家v i c k r e y 因为对这类拍爨的研究而获得了1 9 9 6 年的诺贝尔经济 学奖。 蔓述豹照疆静基本静糖卖方式。滁了主透瓣基本糖卖方式外，述霹疆按照“标静”疆性麴 多少，是甭对“标的”设锻保留价，间一种“标的”的数撬是否大于1 是否允许对“标的”进 行组合竞标萼对拍卖种类进行划分。下蕊对这几种情况的拍卖作介绍。 多蒺壤接卖是一释特臻匏拍卖方式。它茇生在一个买方嚣霹多个囊方翡索筠，囊方各自 的商品具村替代性，买方不仅仅对商品的价格有要求。砸且还对商品的其它属性有自融的偏好， 最终买方根据综合考虑所霄属性的总效_ j 函数得到最优辫。a g e n t 可以谯买方的帮助下构造个 效瑗蘧数，将 赍捂彝备摊冀它属性综合考虑，铮簿每一瓣商燕建立一种纛羧的效焉赞誉，班最大 化买力斌用的方式得到拍藏的解。 设鬻保留价在一种拍卖中，关于“标的”还有是褥设置保留价( r e s e r v ep r i c e ) 之分。 寄镶鼙谕| ! l 巷撩卖是摇在籀粪翦，籀卖人兜雩子确定拍品静缳蟹蹬( 也朝窳徐) ，在拍卖辩，冗竞买 人所出的最高竞价达不到保留价则拍卖不能成交。无保留价拍卖，是指谯拍卖前，拍卖人并不先 行确定拍晶的保留价，在拍卖时只要产生鼹赢庶价，拍安即可成交。 多摹靛赛品撼卖蹩一种在需要一次努滠多个蘑徉鬻赫对候静抬囊形式。多蕈往囊黼拍卖豁 个竞价并不是简单的提出愿意以某种价格购买商品。而是给出一组价格数量对。卖方根据自己 的诸多因素计算出应该以多少价格给买方相应的商品数懿。 缝合籀塞是在买方瓣褒品静缡努箍壤是菲热桎凌瓣情况下产生静捅卖方式，拱：麴警买方对 两件商品一起出售时的心耀价格要大于两件商品单独出侮时候的心理价格之和则称两件商品具 有互补性( c o m p l e m e n t a r y ) ，或另一种情况下买方对瞬佧商品一起出侮丑重的心理价格耍小于薅 捧商酷单独出售时候豹心毽价格之和，镕g 称嚣徉蠢晶其祷替代性( s u b s t i t u t a b l e ) 。缀合拍卖 就是为了让熙方更自由的震达自己的购买欲望而设计的拍卖方式。买方不是每次对一件商品竞 价，丽是阐时对商品的组含竞价。组台可以有多种形式，可以用异或( x o r ) 连接或并( a n d ) 连 接懿方式表达竟赞夭对“椽的”的组合纛蒸。 第二章相芙理论与文献综述第8 页 2 2组合拍卖 2 2 。l 缝合拍卖篱介 缝合拍卖豹学术辑究始予上 鹫缎8 0 年钱，1 9 8 2 年r a s s e n t i 等与1 9 8 9 年b a n k s 等笈袭鹃论 文被认为是这领域的早期工作c 6 3 2 7 。从9 0 年代初期至中期，露关f c c 通讯频道组台拍囊机 制设计问题引发了一场空前的争论，最后由于组合拍痰在实施中的计算复杂性而被认定为无法用 于实酥应用e 2 2 j 。最近，l 年麓着计算梳软硬件技术的发震辩互联阏中毫予商务斑耀撬模秘益扩 人，使德该拍卖机制重新成为学术界离度关潍的焦点。这使得原来麓来无法用于实际应用的这一 拍卖y l m , j 不仅变得合理可行，而且具宵r 泛的应用前景。组合拍卖机制在电子商务与资源与任务 配置等领域中的应胡瓣力受弱越来越多商家瀚重视 2 2 2 6 。 遥台用缎台拍卖的方式进行分溅的资源至少具罄互 怯与替l 性两种特性的一种。簸定被 拍卖的资源集合为月，有 个竞价a g e n t ，捎i 个竞价a g e n t 对资源组合s m 的心理价格函 数为v ；。印为竟价a g e n t i 愿意为资源组合s 出豹最高价格。 踅幸 姓可l 冀彭式纯描述为：对0 i 特定的巍赞a g e n ti ，存在资漆集舍 s ，t 皇m s n 丁= 妒，使得，酸s u ， 毽s ) + 酸( r ) ； 替代性可以形式化描述为：对于特定的竞价a g e n tf ，存在资源集合 s ，7 1 量m & s n t = 使得，v f 晒u t ) a g e n t 趋定义 镥统酌掰肉对象程岸设诗方法戆疆满怒基于i n t e r n e t 魏癸毒建款静褥求，蒸挚a g e n t 韵技 术给我们带来了在分布与开放环境中运行软件系统的全新横式。在现实的分布、开放系缆中，由 于系绫结耥蜀戳动态敬交。融姥宅瓣鳃髂楚逡宣焉随髓糊交纯、爵糖出枣鬻入在萃羁辩瀚麓不弼 软锌工具和技米开发的嵩痰舞构静a g e n t 来蜜瑷现今彩a g e n t 技本塞i n t e r n e t 上童簧运矮予 信息检索和j 垃滤，研究者们精攘下一代的a g e n t 技术能够党成环境中的信息收集，以及利用自身 复杂搂理熊力帮囊蘑户鹅跤瓣题艳3 ，攫戏塌a g e n t 技术游系统审，a g e n t 莳表域各不撼舞，西 藏关予a g e n t 静定义一童惩争论的热轰辩趱。翳翦广灸接受的是j e n n i n g s 簿入捷爨鹃关予a g e n t 的定义c 1 1 ： a g e n t 楚一类霉诗舅嶷体或程謦，墩懿霹蕊癣皴辨棼鬻：境并蠡渣遮绁，班宴璇葵竣诗者释 使用者弱一蒹燃疆标。 由此定义展开，a g e n t 楚少应该镪括4 个基本特性；脯成性、自治性、面向甘标性釉适应环 绩性，a g e n t 逐可戳寄其窀榜犍，懿；移糖拣、叁遗盛缝簿。在丸z 智辍溪壤，许多研究黉更强 调a g e n t 斑是寄更多入类她特质，辩人类鹃鞲挣靛态，皴；知识霸攘念、蠹霉帮义势、诚窦帮理 性等。 第= 章相关理论与文献综述第1 4 页 2 ) 多a g e n t 系统 壤谡多a g e n t 系统( m u l t i - a g e n ts y s t e m ) ，是由多令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 系统的资源是分散的，计算和任务的执行是分布式的。a g e n t 之间的任务划分、资 源与任务分派、行为协调等工作是在遵循一定的知识规剩和管理策略的基础上，由各a g e n t 通过 相互撵用积慰嚣壤懿感知进褥粼紧秘捩策采竞痰。多a g e n t 系统霾螨敢童要挑撬是翔 鼙诖巍寿 a g e n t 在高度不确定并动态变化的环境中协调一致她工作。因此，协调( c o o r d i n a t i o n ) 与协作 ( c o o p e r a t i o n ) 是多a g e n t 系统研究的核心问题乏一。 爨蘩多a g e n t 系统豹主簧磅究努彝包糕：多a g e n t 系绫理论、多a g e n t 蛰囊、多矗g e n t 鬟 划等。县体到备个应用领域材：在i n t e r n e t 上的威用、狂经济学戏市场学中的威用、在电子商 务中的应用等。移动a g e n t 的研究燕痔a g e n t 系统瓒论的一个分支，此类a g e n t 可以自主地在网 络上扶一台圭规移动剿另一螽主撬势连续运行。这缭霹终舔境下熬盔臻疆痔( 妇电子蠢务) 提供 了许多潜在的优点。 2 3 2 多a g e n t 系统中的自动协窿 协褒( n e g o t i a t i o n ) 是一耪健使不霹意见走自一致匏滚动，宅是人类牡会一耱馁瘸懿涎莲解 决方式，小到家庭问越。大到国家事务，都可以用协商来解决。可以通过协商解决的问题通常宥 越下几个特鬣：( 1 ) 裔多个其有独立利益的寅体，玄们参与协商的嗣的是在尽可熊维护自己利益 的翦提下实瑷闷惩鲍鳃决；( 2 ) 任褒个协亵参与穷不裁独立艇决翔蘧；( 3 ) 没蠢一令孛心控铡 蜜体，协助或强迫协翔参与方达成最终协议。在网络应用迥猛发展的今天，很多商务活动将在网 上完成。商品的买卖飘方就商品的价格进彳亍讨价还价。也怒一种典跫的协商。类似于人类的