（计算机软件与理论专业论文）多agent英式序贯拍卖排序策略研究.pdf

郑州大学硕士学位论文 摘要 拍卖作为多a g e n t 技术的重要应用，近年来受到广泛关注。不过由于组合 拍卖效率较高，很多学者的研究都基于组合拍卖协议，但因为组合拍卖问题属于 n p c o m p l e t e 问题，致使它很少有现实的应用。2 0 0 5 年，s s f a t i m a 等人开始 用多a g e n t 技术研究序贯拍卖，他们在j i c g o e r e e 等提出的同时具有市场价值和 个人价值的单“标的”拍卖模型的基础上建模，推导出基于多a g e n t 技术的序贯 t 拍卖最优排序策略。因为他们采用了非关联价值拍卖模型，最优策略只能从预测 尚未拍卖“标的”的价值着手推导，顾及不到已经拍卖的“标的”对竞买者的影 响，得出了一些与现实不符的结论。 序贯拍卖研究的重点和难点是关联价值模型，为了使理论与实际更加接近， 本文同时考虑了已经拍卖的和未拍卖的“标的”，深入分析了两“标的”拍卖时 的不同拍卖排序策略，证明最优策略并不总是符合s s f a t i m a 等提出的理论， 特别是当被拍卖的两“标的”具有互补性时。 进而需要重新设定最优排序策略的标准，通过分析，我们发现拍卖n 个“标 的”时影响拍卖者收入的主要因素是所有拍卖“标的”的总收入增量，在此基础 上，提出了算法o a s a ，从所有可能的n ! 种排序方案中找出拍卖者收入最高的拍 卖序列。 最后在a g l e t 平台上构建了一个英式序贯拍卖模拟系统，用两“标的”拍卖 最优策略不确定性试验，证明在拍卖的两“标的”具有互补性时，拍卖最优策略 不符合s s f a t i m a 等人提出的理论，进而验证了算法o a s a 的可行性和有效性。 关键词：多a g e n t 系统电子商务序贯拍卖 郑州大学硕士学位论文 a b s t r a c t a u c t i o n sa l en o w b e i n gw i d e l ys t u d i e da sam e a n so fb u y i n g s e l l i n gr e s o u r c e si n m u l t i - a g e n ts y s t e m s e x i s t i n gw o r ks t u d i e da u c t i o n sm o s t l yb a s e do nc o m b i n a t o r i a l a u c t i o n s ，a n dt h em o s to b v i o u sp r o b l e mt h a tb i d so nc o m b i n a t i o n so fi t e m si m p o s ei s i n s e l e c t i n g t h ew i n n i n gs e to fb i d s c a l lt h i st h ec o m b i n a t o r i a la u c t i o n p r o b l e m ( c a p ) c a pc a nb ef o r m u l a t e da sa nn p - c o m p l e t ep r o g r a m ，s ot h e r ea r en o t l a r g e s ta p p l i c a t i o nd o m a i n sf o rc o m b i n a t o r i a la u c t i o n s s s f a t i m ae ta 1 b u i l tu pa m u l t i o b j e c t s a u c t i o nm o d e lo nt h eb a s i so ft h em o d e lp u tf o r w a r db yj k g o e r e ea n d t o f f e r m a n , c o n s i d e r i n gc o m m o nv a l u ea n dp r i v a t ev a l u ea tt h es a m et i m e ；t h e nt h e y s t u d i e dt h eo p t i m u ma u c t i o na g e n d a , w h i c hi sb a s e do nt h ea u c t i o n st h a ta r ey e tt ob e c o n d u c t e d i nm a n yr e a l w o r l dc a s e sb i d d e r sc o n s i d e rb o t ha u c t i o n sy e tt ob ec o n d u c t e da n d h a v eb e e nc o n d u c t e d g i v e nt h i s ，w ea n a l y z et w oo b j e c t ss e q u e n t i a le n g l i s h a u c t i o n s ， s h o wt h a to p t i m a la g e n d am a yb ee i t h e rb y i n c r e a s i n go r d e ro rd e c r e a s i n go r d e ro ft h e d i s p e r s i o n o ft h eo r d e rs t a t i s t i c so ft h es u r p l u s e s w h e nt w o o b j e c t s a r e c o m p l e m e n t a r y , o p t i m u ma u c t i o na g e n d ai sn o ta c c o r d i n gt os s f a t i m ae t f s t h e o r y i no r d e rt od e t e r m i n eo p t i m u ma u c t i o n a g e n d a ，w ep u tf o r w a r do a s a a r i t h m e t i c ，w h i c hi sb a s e d0 1 1a u c t i o n e e r st o t a lr e v e n u e t h i sa r i t h m e t i cc a nr a p i d l y g e to p t i m a la g e n d af r o mn ! s c h e m e s a tl a s t , w ec o n s t r u c t e das i m u l a t e d s e q u e n t i a le n g l i s ha u c t i o ns y s t e m ；a n dm a d e t w oe x p e f m e n t s ，o n ed i s p l a y st h a ti tm a yb et h eo p t i m a la g e n d ae i t h e rb yi n c r e a s i n g o r d e ro rd e c r e a s i n go r d e ro ft h ed i s p e r s i o no ft h eo r d e rs t a t i s t i c so ft h es u r p l u s e s ，t h e o t h e rv a l i d a t e st h a to a s aa r i t h m e t i ci sf e a s i b l ea n de f f e c t i v e k e y w o r d ：m u l t i - a g e n ts y s t e m s ，e l e c t r o n i cc o m m e r c e ，s e q u e n t i a la u c t i o n s 郑州大学硕士学位论文 1 1 引言 第一章绪论 在市场经济中，拍卖以其特有的公开性和竞争性已经成为销售或购买商品 的一种重要方式，是电子商务不可分割的一部分，但目前网上拍卖的自动化程度 不高【“2 】；因此成为应用多a g e n t 技术的一个很有潜力的领域。在多a g e n t 系 统中，拍卖是分配物品、服务、任务和资源的一项主要机制。并且实践中得到更 广泛应用的是多物品拍卖，序贯拍卖作为多物品拍卖的一种，正成为活跃的研究 领域1 3 j 。 目前，基于a g e n t 的序贯拍卖的研究或者专注于“标的”的市场价值或者 专注于“标的”的个人价值，但事实上它们作为“标的”的两个内在属性是不可 分割的l 钔。j i c g o e r e e 等人 5 ( 2 0 0 3 ) 提出了同时考虑市场价值和个人价值的单 “标的”拍卖模型并分析了其性质；s s f a t i m a 等人 4 ，6 ，7 】( 2 0 0 5 ) 以此模型 为基础初步研究了最优拍卖排序策略。 本文在s s f a t i m a 等人【4 ，6 ，7 】( 2 0 0 5 ) 的基础上继续深入研究，重新探 讨了基于市场价值和个人价值的英式序贯拍卖最优排序策略，并且在a g t e t 平台 上生成多a g e n t 拍卖模拟系统，验证本文分析结果的正确性和算法的有效性。 1 1 1 问题的提出 以网络为载体的商务形式将成为未来信息社会商务活动的主要模式 8 1 ，根据 s c h m i d 9 】( 1 9 9 7 ) 对电子商务交易阶段的划分，在线市场交易分为四个阶段： 信息阶段、协商( 谈判) 阶段、清算( 结算) 阶段以及售后支持阶段。相对而言， 协商作为电子商务过程的一个关键环节，却是目前各类电子商务应用技术研究中 相对薄弱的环节。拍卖由于其过程相对简单，容易实现自动化，局中人之间不需 要多的信息交流m1 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 之间可以是合 作或对抗的关系。采用a g e n t 部分或完全代替人同其它拍卖参与方( a g e n t 或人) 进行协商，主要目的是减少拍卖费用，提高拍卖效率，优化拍卖过程【1 2 1 。当前 的多a g e n t 系统分为两类：一种是预先设计好程序，按照此程序进行拍卖。另一 种是a g e n t 具有机器学习能力。前者须包含完整的可以应对任何一种拍卖过程中 可能出现情况的策略集；后者可以利用人工智能在谈判过程中进行学习【1 3 】。然 而拍卖过程复杂，简单的战略在复杂的拍卖过程中容易陷入困境。因此，为了适 应电子商务的发展，对基于多a g e n t 的拍卖进行深入研究有重要意义。 本文深入研究了基于市场价值和个人价值的英式序贯拍卖排序策略，假设 拍卖者不但考虑每个”标的”具有市场价值和个人价值，允许每个竞买者不受限 制地参加每次拍卖，而且认为竞买者关注”标的”之间的关系。从而增加了拍卖 的智能化程度提高了拍卖的效率。 本章主要提出问题，介绍研究背景和研究的目的，并着重按拍卖，网上拍 卖，多a g e n t 拍卖的发展顺序对国内外的研究进行分析，总结出多a g e n t 拍卖研 究中所需要解决的问题。在本章的最后提炼出研究的总体思路和研究的主要内 容，并对论文的结构进行了安排。 1 1 2 研究背景 从1 9 9 1 年出现至今，电子商务的发展日益迅猛，根据美国f o r e s t e r r c s e r c h 公司的调查，2 0 0 2 年通过i n m e t 进行的商业活动总值将高达3 0 0 0 亿美元。2 0 0 4 年全球电子商务的交易总额将达到6 9 亿美元。它不仅改变或增加产品的传播和 销售途径，而且重新定义买方和卖方之间的关系，必将会在未来的经济发展中发 挥巨大的作用。 网上拍卖作为电子商务的一个重要组成部分，目前，其交易额正在迅猛增 长，在常见的电子市场交易中，商家大多是通过w e b 页面向消费者提供一个购 物场所，实现简单的商品描述、搜索以及拍卖等环节，消费者通常需要逐个网站 的浏览、比较来选择所需的商品并参与拍卖。这些环节都需要在线操作，并且必 须进行大量的网上数据传输。这通常会浪费消费者大量的时间和精力，而且对于 2 郑州大学硕士学位论文 目前有限的网络宽带来说也是一个沉重的负担1 1 4 l ，因此需要改变传统的电子拍 卖模式，以提高交易的效率、增加交易的智能化程度。 a g e n t 技术的出现，为智能电子商务的发展提供了新的契机，目前许多著名 的大学、实验室或其他研究组织对于基于多a g e n t 的电子商务都表现出了浓厚的 兴趣，并进行了大量的理论研究。 本论文在面向电子拍卖的决策支持系统和基于序贯博弈的多a g e n t 集成式 自动谈判系统研究的基础上，立足于未来电子商务的发展，对网上拍卖进行深入 探索。 1 1 3 研究的意义 我们主要在s s f a t i m a 等人【4 ，6 ，7 】( 2 0 0 5 ) 的成果上继续研究，重新探 讨了基于市场价值和个人价值的英式序贯拍卖最优排序策略，以进一步推动电子 商务的深入发展。 首先，本文的研究将有助于推动电子商务向更深层次发展，当今世界信息 技术和网络通讯技术的飞速发展，使得现代电子商务活动呈现出不断增长的供货 能力、不断增长的客户需求以及不断增长的全球竞争三大特征。电子商务使传统 的基于纸介质的数据和资料的处理、传递和存储等作业方式被电子方式所取代。 电子商务发展的高级阶段就是交易前、交易中、交易后三个阶段皆实现电子化与 自动化处理。本论文结合实际商务过程的需要和多a g e n t 拍卖的优势，研究了英 式序贯拍卖最优排序策略，有助于在学术界开展相关研究，从而进一步完善电子 商务交易中阶段的自动化处理功能，实现企业之间的动态合作，推动电子商务向 更深层次发展。 其次，本文的研究有助于丰富和完善网上拍卖领域的拍卖研究，拍卖是一 种历史悠久的市场交易方式，m c a f e 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 去找它感兴趣的拍卖a g e n t ，并在它的组织下参加 竟标。我们认为如果拍卖a g e n t 控制得当，这个模式就可以有效的防止目前网上 拍卖中“阻击”的产生。并且大大降低了网上数据传输量，减少了网络宽带的负 担。 最后，本论文的研究有助于提高拍卖者的收益，多数通过网络拍卖物品的 人不是资深的拍卖人员，如果采用基于多a g e n t 技术的电子拍卖模型，就能自动 结合竞买者的购买行为，优化竞买者的拍卖策略，整个拍卖过程可以在竞买者提 交请求后由a g e n t 自动生成不同阶段的最优拍卖排序策略，实现了智能化和自动 化，使得竞买者免于进行繁琐地搜索、浏览、比较、选择和拍卖等环节，节省竞 买者的时间和精力，这充分体现电子商务高效、快捷的优势，极大的降低交易成 本和拍卖者人为失误的影响，增加拍卖者的收入。 1 2 国内外研究现状及分析 随着电子商务在商务活动中地位的巩固，越来越多的学者进入这个研究领 域。多a g e n t 拍卖作为未来电子商务的一种形式，是从传统拍卖和目前的网上拍 卖发展来的。它们是一脉相承的。 4 郑州大学硕士学位论文 1 2 1 拍卖与网上拍卖 拍卖这种交易方式有着悠久的历史，但作为经济学分枝，拍卖理论只是在 最近二十年才得到蓬勃的发展。直到1 9 9 6 年现代拍卖理论的奠基人v i c k r e y 才 获得了诺贝尔经济学奖。有记载的拍卖理论研究是从上世纪的五六十年代开始 的。v i c k r e y 1 5 1 ( 1 9 6 1 ) 提出了正式的拍卖模型，并得到了著名的“收益等价原 理”。v i c k r e y 的模型是个人价值( p r i v a t ev a l u e ) 模型。不久之后，w i l s o n 提出 了市场价值模型( c o m m o nv a l u e ) 。对于各种拍卖的研究出现在各种管理学的杂 志中。到了八十年代，拍卖理论的研究出现了新的重要进展。r e l i e y 和 s a m u e l s o n 1 6 1 ( 1 9 8 1 ) ，m y e r s o n t t 7 l ( 1 9 8 1 ) 同时证明了更加一般的“收益等价 原理”：在任何两个不同个人价值拍卖模型中，如果物品总是由评价最高的人得 到，并且评价最低的人在两个模型的收益是一样的，那么这两种拍卖产生相同的 预期收益。而且，m y e r s o n 1 7 】( 1 9 8 1 ) 也证明了一般的最优拍卖机制的设计要 满足的条件。m i l g r o m 和w e b e r 1 8 1 ( 1 9 8 2 ) 提出了“a f f i l i a t e dv a l u e ”模型，统 一了个人价值和市场价值模型，为拍卖理论的研究提供了新的框架。 收益等价原理成为拍卖理论发展的基准，之后的理论进展在于放松等价原 理的假设条件，分析拍卖的机制设计对收益有重要的影响，最后得出没有普遍最 优的拍卖方式。收益等价成立的条件有：( 1 ) 参与者风险中性。不论是拍卖者 ( a u c t i o n e e r ) ，还是竞买者( b i d d e r ) 都是风险中性。( 2 ) 只有一件物品拍卖。( 3 ) 不同竞买者对”标的”的评价是独立的私有评价，不受其他人评价的影响。( 4 ) 竟买者之间不存在合谋和勾结。( 5 ) 竞买者之间是对称的，他们的评价有相同的 分布，对于拍卖的结构有相同的信息。随着理论的进展，拍卖理论的研究突破了 单一物品拍卖研究的限制，开始讨论多单位产品同时拍卖的问题。并且由早期的 关注各种拍卖形式的收益问题，逐渐转移到讨论最优效率的拍卖的问题：即拍卖 的结果是对物品评价最高的竞买者获得”标的”。这反映了在政府主持的拍卖中 效率问题是考虑的关键，是理论和实践结合的显著标志【1 9 t 孙2 1 毖2 3 1 。 网上拍卖是近几年伴随着互联网的发展而产生的一种新型的商品交易方 式。网上拍卖就是利用互联网在网上公开欲出售的商品或服务的一些信息，通过 竞争投标的方式将它出售给出价最高的竞买者。它的实质是以竞争价格为核心， 5 郑州大学硕士学位论文 建立买卖双方的交流与互动的机制，共同确定价格和数量，从而达到均衡的一种 市场经济过程。应该说网上拍卖的理论内核是传统的拍卖理论，但是由于电子商 务环境有许多有别于传统拍卖的特点，所以在传统拍卖理论的研究内容基础上， 网上拍卖理论有着自己独特的研究热点问题。网上拍卖与传统拍卖的不同之处就 构成了网上拍卖理论自己的独特的研究内容【弘蕊2 6 , 扒矧。例如：进入和参与方 式不同、结束方式不同、“y a n k e e 拍卖 2 9 1 ”、最后时刻投标( l a s t m i n u t eb i d d i n g ) 策科雏3 1 1 、网上采购。 一般来讲，网上拍卖采用理论研究和实验研究两种方法。在理论研究方面， 由于网上拍卖是继承传统拍卖理论的衣钵，其理论内核就是拍卖理论。所以网上 拍卖的理论研究方法大多与传统的拍卖理论类似，都是在一系列假设约束的条件 下( 这里基准点模型需要根据网上拍卖的特点修正) 采用经济博弈理论的方法研 究网上拍卖的特定问题。还有一些学者是利用互联网丰富的数据资源，对网上拍 卖进行实验统计研究，他们主要是利用一些人工智能的方法，用统计分析的手段 来挖掘网上拍卖中特性问题的数理特性。实验研究方法本文不做过多介绍，本文 主要根据网上拍卖的特点结合多a g e n t 技术进行分析。 1 2 2 多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 的拍卖交易中阶段的智能化，近年来，各国学者结合网 上拍卖的新特点，重点研究了多属性拍卖强弘3 量雏3 7 1 ，组合拍卖【3 8 3 9 辄4 1 1 ， 序贯拍卖1 4 2 1 。 b i c h l e r 将多属性拍卖定义为：拍卖者与竞标者交易时考虑到多个属性的一 种拍卖模式，即双方在价格以外其他属性上进行多重谈判的拍卖模式【4 3 “4 5 1 。 他将多属性效用理论应用于多属性拍卖，利用多属性效用评价函数来准确表达用 户的属性偏好。根据多属性效用理论，拍卖的理想情况是选择可以达到最高期望 效用的投标。在利用多属性效用理论工具建立模型的同时，考虑了采购方对采购 商品各个属性的权重。相对于传统的单一价格属性的拍卖，多属性拍卖具有更广 6 郑州大学硕士学位论文 泛的应用性。近年来面向电子商务的多属性拍卖机制作为一种解决一对多协商问 题的有效方式引起了广泛地关注。但这仍只是复杂的个人价值模型，未能考虑“标 的”的市场价值。 与传统的拍卖方式相比，组合拍卖在分配多种商品时效率更高。从当前组 合拍卖的应用情况可以看到，对于物品之间有互补影响的市场，组合拍卖是一种 非常可行的拍卖方式。它允许竞买者对感兴趣的组合提交投标，使得拍卖者能够 根据竞买者的投标，将“标的”划分为合理的组合，按照最大化拍卖者收入的目 标分配这些标的组。由于分配的结果是基于竞买者的组合投标，所以基本满足竞 买者的需要：对于竞买者没有动机去转售( 或再需求) ，也就降低了产生套利的 可能l 删。随着计算能力的不断增强，组合拍卖越来越得到人们的重视。需要注 意的是，所有设计的最优化组合程序均建立在数学规划公式的基础上，拍卖者在 组合拍卖中希望的最佳分配方案，即组合拍卖问题，属于n p c o m p l e t e 问题。所 以组合拍卖总体来说是一个计算上很复杂的一种拍卖形式。并且组合拍卖因为其 复杂性而不常被使用。对于组合拍卖的研究，研究者通常作如下努力问题：忽略 某些问题，让竞买者去推测他们将来是否将赢得项目；对于物品增加一个转售市 场，希望可以帮助产生经济上可取的组合；在多轮并行拍卖中出售多个项目，希 望前一轮的反馈信息可以提供竟买者在下一轮的竞标策略；通过规定一个、两个 或多个拍卖者可以组队的机制，使他们的投标结合起来，希望他们能找到最佳投 标途径1 4 ”。 序贯拍卖在资源分配上变得越来越重要【4 2 1 ，但已有的研究多是经济学家对 序贯拍卖中存在的现象的解释。文献【4 8 j 从模型上证明了序贯拍卖的信息收益 ( i n f o r m a t i o nb e n e f i t s ) 的影响，在第一阶段之后竞买者就可以从拍卖中获取信 息，为下一阶段的拍卖估价做参考。文献1 4 9 l 根据最优拍卖机制设计的思想，在 序贯拍卖中引入保留价，对于每一阶段竞买者的报价达不到保留价的“标的”留 待下一阶段拍卖；对于有足够多的竞买者的情况下，拍卖者的多阶段均衡保留价 将达到一次性静态最优拍卖的保留价。文献【饥5 1 1 根据“标的”的供给状态讨论 了在序贯拍卖中拍卖价格依赖于供给，不确定性供给将导致“标的”最优价值的 降低；同时对于确定供应减少的信息将会促进拍卖价格的上升，这是竞买者在参 与拍卖“干中学”的能力不断提高，竞买者对“标的”个人价值信息地掌握对拍 7 郑州大学硕士学位论文 卖价格有消极的影响。因此在文献1 5 2 l 的研究中得到不公布“标的”数量和拍卖 阶段数时，拍卖结果对拍卖者是有利的。随着网上“标的”的丰富，这样的有意 隐藏“标的”信息不利于拍卖的发展。在文献【5 3 划中，作者对多“标的”( 同质) 序贯拍卖作了一个总结，通过价格趋势的理论分析得出在同质“标的”拍卖过程 中预期拍卖价格保持不变。但是经验研究显示，序贯拍卖价格可能上升也可能是 下降：文献【5 5 】在酒的序贯拍卖中发现价格趋势是下降的；文献1 5 6 在房地产拍卖 中也发现存在这种规律。但是也有不少经验研究显示序贯拍卖价格存在上升的趋 势：文献旧在以色歹l j 电视电缆工程分段拍卖中得到了价格上升趋势。另外，文 献【5 8 】在木材的序贯拍卖中一样得到了拍卖价格即可能上升也可能下降。以上研 究或是只考虑“标的”的市场价值或是只考虑“标的”的个人价值，事实上，对 一个“标的”来说两者缺一不可1 5 9 。j k g o e r e e 等人1 5 1 ( 2 0 0 3 ) 提出了同时具有 市场价值和个人价值的单“标的”拍卖模型，并对其性质进行分析。经济学家对 序贯拍卖的经济现象已经做了深入透彻的分析，为网上拍卖的交易中阶段智能化 提供了坚实的理论基础。s s f a t i m a 等人【4 ，6 ，7 】( 2 0 0 5 ) 研究了基于多a g e n t 技术的序贯拍卖最优拍卖顺序策略，认为按竞买者收益顺序统计离散度递减拍卖 “标的”拍卖者收益最大。他们为序贯拍卖的智能化研究提供了一个方向，但因 对拍卖模型限制过多，有待进一步深入。 1 3 研究目标和内容 1 3 1 研究目标 本论文旨在研究基于多a g e n t 技术的序贯拍卖，通过对序贯拍卖拍卖者拍 卖顺序机理的深入分析，结合多a g e n t 的优势，设计合理的最优排序算法，实现 买卖双方的双赢拍卖，提高资源的分配效率，实现交易过程的自动化、智能化。 推动电子商务向更深层次发展。 1 3 2 研究内容 对于多a g e n t 序贯拍卖排序策略的研究，关键是建模要与现实相符。本文 郑州大学硕士学位论文 在s s f a t i m a 等人【4 ，6 ，7 】( 2 0 0 5 ) 的基础上继续深入研究，重新生成更贴近 现实的英式序贯拍卖模型，然后分析基于市场价值和个人价值的英式序贯拍卖最 优排序策略，最后用a o e t 生成多a g e n t 拍卖模拟系统，验证本文分析结果的正 确性和算法的有效性。本着由易到难的原则先研究两“标的”排序策略，后研究 多“标的”排序策略，并给出了多“标的”最优排序策略的算法o a s a 。 1 4 本文的结构安排 本文按照提出问题，分析问题，解决问题的思路，全文共分六章。第1 章 介绍研究背景，分析国内外的研究现状，提出多a g e n t 序贯拍卖排序策略这一研 究课题；第2 章分析问题，对基于市场价值和个人价值的多a g e n t 序贯英式拍卖 进行论述，并介绍涉及的相关理论；第3 章、第4 章解决问题，按先两“标的” 后多“标的”的顺序，分别从竟拍者、拍卖者的角度，研究了多a g e n t 英式序贯 拍卖中竞买者竞买策略，买受者的利润，拍卖者的拍卖排序策略，拍卖者的收入， 并给出拍卖者最优拍卖策略；第5 章在上述工作的基础上，应用i b m 的a g l e t 平台来构建了一个基于a g e n t 的网上英式序贯拍卖模拟系统，用试验验证前两章 的分析。第6 章总结全文并展望未来。 9 郑州大学硕士学位论文 第二章相关理论综述 2 1 市场机制与拍卖 市场机制是解决有限资源分配的有效机制，拍卖具有为难以确定价格的商 品找到一个合理价位的特性【砷一1 1 ，因而是一种重要的市场机制。 2 1 1 市场机制 对市场中的协商来说，通常都只有两方参加卖方和买方。但由于市场 的不同，每一方的个体个数也都不相同，针对不同的情况所采用的协商方法也不 尽相同。经济环境中有不同的经济个体在一个市场中交互。市场规定了经济个体 在其中可以采取的动作，根据市场规则，市场系统中各经济个体动作的组合产生 经济结果。如果市场中的每个经济个体拥有有限资源，并且每个经济个体都对其 它资源有自己特殊的偏好，这可看作是一个资源再分派问题。资源分派问题是经 济学中的核心问题。市场机制是一种将经济个体的动作和信息映射到资源分派解 决方法的一种协议。 市场机制能够让市场中每一种资源被赋予一个价格。价格是一个非负实数， 代表资源在市场中的交换价值。经济个体根据资源价格做理性决定来竞争资源。 经济学中有关于市场结构和与之相关的价格决定机制的大量理论。表2 - 1 给出了 一个微观经济形态学的市场结构表，如表所示的市场结构是按照卖、买方双方参 与市场的个体数目来划分。 表2 1 市场结构表 买方 爪 多个 卖方 一小 一对一协商正向拍卖 多个 反向拍卖 双向拍卖 在上表中，我们看到拍卖机制是市场结构形成的主要机制。传统狭义的“拍 卖”概念等同于这里的正向拍卖。广义的拍卖定义为：拍卖是通过一系列明确的 1 0 郑州大学硕士学位论文 规则与买者或者卖者竞价所决定的价格来决定资源配置的一种市场机制；即在确 定的时间和地点，通过一定的组织机构，以公开或密封竞价的形式，将特定物品 或财产权利转让给最高或最低应价者的买卖方式。下面对拍卖做详细的介绍。 2 1 2 拍卖 拍卖这种特殊的交易方式作为市场价格机制的重要组成部分。它具有其它 买卖形式不可替代的功能，除了揭示信息、发现价格这一基本功能外，还可以减 少代理成本；稳定市场价格，防止欺行霸市；加速商品流转，减少资金沉淀；有 利于配合司法仲裁( 如抵押或破产处理) ；获得更多的市场信息。 这里对表2 1 中涉及的几种拍卖方式作一介绍。 正向拍卖( f o r w a r d a u c t i o n ) 为一个卖方多个买方的拍卖形式，卖方将选 择出价最高的买方作为物品或财产权利转让者。该拍卖多用于稀缺资源竞买或抵 押、破产、过剩资产处理中，它能帮助卖方在拍卖竞价中去发现资源真实价格和 稀缺程度，避免交易的主观随意性，更直接地反映市场需求，最终实现商品的最 大价值。 反向拍卖( r e v e r s e a u c t i o n s ) 也称为招标。是一个买方多个卖方的拍卖形 式，买方将选择报价最低的卖方作为物资或服务供应方。该拍卖多用于企业或政 府采购物资和服务招标，是电子商务中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 ) ，是有多个买家和 多个卖家同时向拍卖员递交竞标价格和竞标数量的拍卖形式。拍卖员把卖家的要 约( 从一个低价开始上升) 和买家的要约( 从一个高价开始下降) 进行匹配，直 到要约提出的所有出售数量都卖给了买家。该拍卖方式多用于股票、期货等金融 商品交易以及供应链的形成。 一个典型的拍卖主要包招四个要素，参与者、“标的”、收益函数和出价策 略。参与者包括竞买者、委托人和拍卖者。“标的”可以分为单“标的”和多“标 的”，单“标的”拍卖中的“标的”是指单个不可分的；多“标的”拍卖中的多 个“标的”有同质和不同质之分。收益函数涉及到有关“标的”移交时在经济上 郑州大学硕士学位论文 支付的一些判定，例如胜者确定规则，最终受让价格和买受人，“标的”有无保 留价格，以及其它的参与成本。出价策略是指竞买者如何估价和出价。 传统的拍卖可以分成如下的四类： 1 ) 增价拍卖也称英式拍卖。在该拍卖中，竟价者叫一个比前一个出价更 高的价格，直到没有人出更高的价格为止。英式拍卖是开放式拍卖或开放出价 ( o p e nc r y ) 的拍卖。英式拍卖在有些情况下会有拍卖起价或保留价格。如果没 有人出价高于保留价格，那么拍卖就终止，这样就不会因为出价过低给卖方造成 损失。 2 ) 减价拍卖也称为荷兰式拍卖，这种方式起源于荷兰人拍卖果蔬和鲜花 时所使用的方法。荷兰式拍卖的拍卖者从一个高价开始降价，一直降到有竞买者 愿意接受为止。在大多数的荷兰式拍卖中，卖方提供大量的同样物品供出售。荷 兰式拍卖常常要用一个钟表，价格随着表的走动而下降，第一个叫停的人就成了 “标的”的买受者，他可以按这个价格购买他所需要量的商品，如果“标的”还 有剩余，拍卖将继续进行，直到所有的“标的”都被买走。 3 ) 第一价格密封拍卖密封竞价拍卖是与上面两种开放式拍卖相对的拍卖 方式，竞买者以密封的方式递交自己的出价。出价是保密的，只有竟价者和拍卖 者知道出价的具体数值，出价最高的人获得“标的”。 4 ) 第二价格密封拍卖又称为v i c k r e y 拍卖，是在密封竞价拍卖中，卖方将 “标的”以拍卖中第二高的竞价将“标的”卖给胜者( 出价最高的竞买者) 。在 这样的拍卖中，竞买者将按照自己的心理价位诚实出价。经济学家v i c k r e y 因为 对这类拍卖的研究而获得了1 9 9 6 年的诺贝尔经济学奖。 上述的是四种基本的拍卖方式。除了这些外，还可以按照“标的”属性的 多少，是否对“标的”设置保留价，同一种“标的”的数量是否大于1 ，是否允 许对“标的”进行组合竞标等对拍卖种类进行划分。下面对这儿种情况的拍卖作 简单介绍。 多属性拍卖是一种特殊的拍卖方式。它发生在一个买方面对多个卖方的市 场上，卖方各自的商品具有替代性，买方不仅仅对商品的价格有要求，而且还对 商品的其它属性有自己的偏好，最终买方根据综合考虑所有属性的总效用函数得 到最优解。买方可以构造一个效用函数，将价格和各种其它属性综合考虑，针对 1 2 郑州大学硕士学位论文 每一种商品建立一种虚拟的效用货币，以最大化买方效用的方式得到拍卖的解。 设置保留价在一种拍卖中，关于“标的”，还有是否设置保留价( r e s e r v e p r i c e ) 之分，有保留价的拍卖是指在拍卖前，拍卖者先行确定“标的”的保留价 ( 也叫底价) ，在拍卖时，凡竞买者所出的最高竞价达不到保留价则拍卖不能成 交。无保留价拍卖，是指在拍卖前，拍卖者并不先行确定“标的”的保留价，在 拍卖时只要产生最高应价，拍卖即可成交。 竞买者和拍卖者是一对矛盾统一体。对于竞买者来讲，他在拍卖中的主要 任务就是通过在拍卖过程中不断的调整自己的竞标策略使自己的利润最大化( 买 方剩余最大化) ；而对于拍卖者来讲，他希望通过对拍卖协议的设计，找出对自 己最有利的规则( 协议) ，从而使自己的收入最大化( 卖方剩余最大化) 。对于一 个拍卖模型的设计者而言，他希望社会剩余( 买方剩余+ 卖方剩余) 最大化，即 拍卖的双方达到纳什均衡状态，从而达到帕雷托最优。这种状态的出现恰好是拍 卖双方同时追求最优化的最终结果。拍卖模型的设计者研究的出发点应该开始于 对竞买者最优竞标策略的分析，找出拍卖者的最优期望收入，在这种均衡状态下 的拍卖就是一个理想的拍卖模型。也就是说，最优拍卖机制设计问题，很好的将 拍卖双方结合在一起，在充分分析拍卖双方所面临的问题的基础上，达到了社会 资源的最优化配置。英式拍卖能够满足拍卖者的最优期望收益，因此，本文首先 基于这种拍卖协议进行研究。 2 1 3 多“标的”拍卖 到目前为止我们只考虑了单“标的”的拍卖，在实践中更多地观察到的是 多“标的”拍卖。近年来，各国政府越来越多地通过拍卖市场实施国有企业的私 有化、重塑竞争性基础设施产业( 电信、电力、天然气、交通等) 、配置公共稀 缺资源以及增加财政收入渠道，私人部门也更多地通过拍卖转让资产所有权或者 采购原材料。这些应用领域往往涉及到多个同质或者类似的拍卖“标的”。因此， 多“标的”拍卖机制的设计问题日益受到关注，并正成为拍卖理论中最为活跃的 研究领域【3 | o 多“标的”拍卖可以采用组合拍卖或序贯拍卖。 组合拍卖组合拍卖是一种竞价者可以对多个“标的”的组合进行竞价的拍 卖方式。它适用于买方对商品价值衡量呈现非加性的情况。相比传统拍卖方式， 郑州大学硕士学位论文 组合拍卖在分配多件商品时效率更高。组合拍卖经常出现在电力市场、举债经营、 带宽拍卖【6 2 l 、汽车服务市场【硎、污染权拍卖、飞机起落场所脚i 拍卖等等。 定义需要拍卖的商品集合为m 。 定义珂个竞买者，第i 个竟买者的心理价格函数为y ，对商品集合s m 的 函数n v , ( s 1 为竞买者对商品组合s 的心理价格，既是竞买者f 愿惫为商品组合s 出的最高价格。 心理价格函数满足下面两个特性： e 岱) s 仃) ，如果s c _ m ，没有一件商品具有负的价格； e ( 一0 ，竞价人没有得到任何商品的情况下不会支付金钱。 适合组合拍卖的商品交换情况至少将具备下面两种特性的一种： 互补性( c o m p l e m e n t a r y ) ：对某些竞买者i ，存在集合只tc _ m & sn t 一妒， 使得u u r 卜e ) + u p ) ； 替代性( s u b s t i t u t a b l e ) ：对某些竟买者f ，存在集合s ，r m & s n t 一妒， 使得h 岱u r ) h ) + h 仃) 。 互补性是表达商品之间的相互依赖的特性，如对购买土地的买家来说。如 果他想建造一个大面积商场，相邻的两块土地对他来说肯定比隔开的两块同样大 小的土地价值更多。 替代性是指买方面对着可以近似替代的商品，只需要其中一样，如汽车制 造商面对不同的配件提供商制造的同样规格商品的时候，每样只需要从中间选出 一件就可以了。 与传统的拍卖方式相比，组合拍卖在分配多种商品时效率更高。在这方面 的研究，目前已经出现大量的研究成果。t a k a y u k il t o 等人对有多个专家和业余 爱好者参加的组合拍卖协议进行了研究，其中的专家只具有一种技能睁1 。a n t o n l i k h o d e d o v 和t u o m a ss a n d h o l m 研究了提高组合拍卖收入的方法。类似的研究 还有很多。但他们都没有考虑竞胜标问题，都是对组合拍卖协议的改进，当拍卖 “标的”和购买者过多时很难在实际中实现。b e n o i th u d s o n 和t u o m a s 1 4 郑州大学硕士学位论文 s a n d h o l m 提出了增加式偏爱启发的组合拍卖方式f 6 6 j ，这种方法有效地提高了决 定竞胜标的效率，但还是指数时间的。这是因为由于组合拍卖具有互补性和可替 代性的优点，竟买者虽然可以更好的表达自己的偏爱，但是为了表达他们的偏爱， 必须对所有的组合投标。例如，将k 个“标的”卖给n 个竞买者，“标的”的组 合方式一共有2 k 一1 种，每个竞买者都要对所有的组合方式表达他们的偏爱，那 么拍卖者一共要向竞买者发出n ( 2 k 一1 ) 次询问l 删。 序贯拍卖人们并不是一开始面对多“标的”拍卖就采用了组合拍卖的方式。 最开始人们采用经典的拍卖方式一件件顺序拍卖商品，这就是序贯拍卖。决定拍 卖的胜利者十分简单，从每一件商品拍卖中选出叫价最高的竞买者就可以了。 用序贯拍卖的方式拍卖多件相同的“标的”，则每件“标的”的期望价格相 等，不取决于拍卖的先后顺序，并且期望收入等价定理仍然成立。但是当“标的” 不相同，在关联价值模型中，或者当竞买者之间是非对称时，上述结论不一定成 立【“鳓叫。 因此竞买者叫价就出现了一个十分困难的问题，当竞买者对“标的”的组 合有特殊的偏好，对每一件“标的”竞价的时候，竞买者必须考虑在以后的拍卖 中，他能否得到他想要的其它商品。他是否能在以后的拍卖中得到他想要的商品 又决定于其它竞买者在以后的拍卖中如何竞价，但同样其它竞买者也要考虑他之 外的竞买者在现在和以后可能的竞价方式。这样相互的考虑需要大量的计算。在 当时没有计算机支持的情况下，是不可想象的。 并且有人提出，由于传统拍卖中竞标者不可能完全知道对方的信息，所以 这样的前视得到的结果也就无法保证其准确性。虽然为了解决顺序拍卖前视的困 难，提出的并行拍卖的机制( 所有商品同时进行拍卖) m 可以消除信息的不确 定性，竞买者可以知道其它人是如何竟价的，但大多数竞买者都等待着别的竞买 者先叫价，所以竞价可能永远不会开始。一个理性的a g e n t 无法判断什么是最合 理的动作1 7 0 】。 前视结果无法保证准确性这一论断直到j k g o e r e e 等人【5 1 ( 2 0 0 3 ) 提出了 同时考虑市场价值和个人价值的单“标的”拍卖模型才得以解决。他们分析出拍 卖者对”标的”的信息公布的越多，拍卖者的收益越高。这就给了拍卖者公布“标 郑州大学硕士学位论文 的”信息的原动力，竟买者可以据此分析“标的”的个人价值，这里唯一不确定 的是“标的”的市场价值，但市场价值是有规律可寻的通过适当的概率分布可以 科学的计算出来。 通过上面的分析，可以得出：市场价值和个人价值模型解决了前视结果不 准确的问题；多a g e n t 技术在网上拍卖的应用，解决了这种计