（系统工程专业论文）混合型多属性组合拍卖研究.pdf

摘要 摘要 多属性拍卖和组合拍卖作为多物品拍卖的两个重要研究方向，是解决各种资 源分配问题的有效机制。随着电子商务的不断发展以及政府、企业采购的日益复 杂，利用多属性拍卖和组合拍卖进行采购越来越有现实意义。多属性拍卖中的购 买者效用的确立以及组合拍卖中竞胜标问题是拍卖理论中的研究核心，这两个问 题的解决关系到拍卖机制的有效性和实用性，同时也关系到政府、企业采购机制 的建立，有着极高的现实意义和广泛的应用背景。 本文主要研究基于混合多属性拍卖和多数量组合拍卖模型，分析多属性拍卖 购买者效用和组合拍卖竞胜标问题。 本文总结了多属性拍卖的特点和适用范围，对多属性组合拍卖问题做了综 述。接着运用数学模型和仿真计算多属性拍卖两种模式m a a 和r a q 的在有两 个供应商和有多个供应商条件下的效用期望值，以说明供应商产品的效用函数对 购买者的意义。构建产品的指标体系，通过建立混合多属性决策模型对各个属性 在标的中的权重进行求解，并求出供应商产品对购买者的效用。最后在得出多属 性拍卖中购买者对各个标的的效用基础上构建多属性组合拍卖的o 1 整数规划模 型，将多属性拍卖的效用代入模型并运用改进单亲遗传算法求解竞胜标。 本文的主要贡献是：在构建产品指标体系的基础上运用混合多属性决策模型 求指标的权重得出产品的效用。同时本文构建多数量多属性组合拍卖的整数规划 模型并利用改进单亲遗传算法求解。 本文针对企业采购产品的现实意义，构建多属性组合拍卖模型，研究成果为 政府和企业的采购提供了有益的理论指导和方法支持。 关键词：多属性拍卖；组合拍卖；改进单亲遗传算法 a b s t r a c t a b s t r a c t m u l t i a t t r i b u t ea u c t i o n sa n dc o m b i n a t o r i a la u c t i o n sa r et w oi m p o r t a n tr e s e a r c h f i e l d si nm u l t i c r i t e r i aa u c t i o n sa n de f f i c i e n tm e c h a n i s m sf o rr e s o u r c ea l l o c a t i n g w i t h t h ed e v e l o p m e n to fe c o m m e r c ea n dt h ei n c r e a s i n gc o m p l e x i t yo fc o m p a n y s p r o c u r e m e n ts t r a t e g y , t h ep r o c u r e m e n t w i t ht h em u l t i a t t r i b u t ea u c t i o n sa n d c o m b i n a t o r i a la u c t i o n sw i l lh a v er e a l i s t i ci m p o r t a n c e t h ed e f i n i t i o no fc u s t o m e r s u t i l i t ya n dt h ew i n n e rd e t e r m i n a t i o na r et w oc o r ep r o b l e m si na u c t i o nt h e o r yc a u s e i t h a sad i r e c te f f e c to nt h ev a l i d i t ya n dp r a c t i c a l i t yo ft h ew h o l ea u c t i o nm e c h a n i s m ， a n dt h e ya l s oi n f l u e n c et h ee s t a b l i s h m e n to fp r o c u r e m e n tm e c h a n i s m i naw o r d ，t h e r e s e a r c ho fm u l t i a t t r i b u t ea u c t i o n sa n dc o m b i n a t o r i a la u c t i o n sp r o b l e mw i l lh a v e i m p o r t a n tt h e o r e t i c a lv a l u e sa n dw i d ep r a c t i c a la p p l i c a t i o nb a c k g r o u n d t h i sp a p e ri sb a s e do nt h er e s e a r c ho fh y b r i dm u l t i - a t t r i b u t ea u c t i o n sm o d e la n d 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 sm o d e l f i r s t l y , i ts u m m a r i z e st h ec h a r a c t e r i s t i ca n d a p p l i c a t i o ns c o p eo fm u l t i a t t r i b u t ea u c t i o n s s e c o n d l y , i tc o m p a r e st h ee x p e c t e d u t i l i t yi nr a qa n dm a a m o d e l sb ya d o p t i o no fm a t h e m a t i c a lm o d e l sa n ds i m u l a t i o n i no r d e rt os h o wt h ev a l u eo fu t i l i t yf u n c t i o n t h i r d l y , i ts e t su pa ni n d i c a t o rs y s t e m a n dc a l c u l a t e st h ew e i g h tv a l u e sa n dt h ep u r c h a s e r su t i l i t yw i 廿lt h eh y b r i d m u l t i - a t t r i b u t ed e c i s i o nm o d e l f i n a l l y , i te s t a b l i s h e sa0 - 1i n t e g e rp r o g r a m m i n gf o r m u l t i a t t r i b u t ec o m b i n a t o r i a la u c t i o n s ，a n dw i mt h ei m p r o v e dp g aa l g o r i t h m ，t h e p a p e rs o l v e st h ew i n n e rd e t e r m i n a t i o no f t h ea u c t i o n t h ef o l l o w i n gt w op o i n t sa r et h em a i nc o n t r i b u t i o n so ft h i st h e s i s f i r s t l y , i t a d o p t st h eh y b r i dm u l t i a t t r i b u t ed e c i s i o nm o d e lt o s o l v et h ew e i g h t s s e c o n d l y , i t d e s i g n s a l li m p r o v e dp g aa l g o r i t h mt os o l v et h em u l t i a t t r i b u t ec o m b i n a t o r i a l t h et h e s i ss e t su pah y b r i dm u l t i - a t t r i b u t ec o m b i n a t o r i a la u c t i o n sm o d e la n d c o u l db eu s e da sar e f e r e n c ef o rt h eg o v e r n m e n ta n de n t e r p r i s e sp r o c u r e m e n td e c i s i o n m a b s t r a c t k e yw o r d s ：m u l t i - a t t r i b u t ea u c t i o n s ；c o m b i n a t o r i a la u c t i o n s ；i m p r o v e dp g a i v 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 声明人( 签名) ：研p 知状 伊c 1 年占月c 7 日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文， 于年月日解密，解密后适用上述授权。 ( ) 2 不保密，适用上述授权。 ( 请在以上相应括号内打“ 或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人( 签名) ：研p 知。式 1 年6 月 第1 章绪论 1 1 研究背景和意义 1 1 1 研究背景 第1 章绪论 拍卖作为一种资源的有效分配方式，应用广泛且历史悠久。许多国家政府采 用拍卖的方式出售国家债券、外汇、各种油田或者矿山的开采权，同时也利用拍 卖来进行采购以及确定服务商和系统开发运营商。在我国，自1 9 8 6 年出现第一 家拍卖企业以来，拍卖经过三十多年的发展已经具有较大的规模。拍卖品的种类 也从实体物品发展到包括无形资产在内的十多个领域。 拍卖虽然有着悠久的历史，但对拍卖研究仅有几十年的时间，始于1 9 6 1 年 v i c k r e y t l 】的重要文献，v i c k r e y 在该文献勾画了研究拍卖的框架，随后拍卖研究 经历了2 0 年较为缓慢的发展过程以及8 0 年代初至今拍卖研究的快速发展的过 程。拍卖研究，一般被视为博弈论的分支之一，同时应用微观经济理论、决策理 论、统计学和随机理论等领域知识。伴随着电子商务的快速发展，拍卖已经从传 统的面对面拍卖发展到互联网上开展网上拍卖( o n l i n e a u c t i o n s ) 。尤其是在2 0 0 0 年后，越来越多的企业和政府采购行为通过网上拍卖的形式来实现，有关各种物 品采购机制以及网上拍卖的文章引起了人们的广泛关注，在涉及上述领域的同时 还涉及到信息经济学和智能代理等众多新兴领域。 然而，现拍卖理论的研究仍有局限性，主要表现在： ( 1 )拍卖研究领域中，如拍卖机制的研究，以及竞胜标确定( w i n n e r d e t e r m i n a t i o n ) 研究中多仅以价格作为考量的标准，未考虑诸如产品质量等其他 属性。拍卖较其他价格策略，比如固定价格策略，其中一个重要的优点就是基于 物品价值的不确定性。不同的人对于相同物品的价值有着不同的考虑，有的人最 看重价格，有的人看重产品的质量。而在现有拍卖的理论中，如竞胜标的确定以 价格的高低作为参考的惟一属性。而在实际拍卖中，质量、提前期等属性也关系 到产品的价值而影响拍卖。在研究多属性的拍卖理论中，也多仅仅是将质量视为 混合型多属性组合拍卖模型研究 一个与价格属性线性的属性简单考虑。 ( 2 ) 拍卖的研究多集中于单物品、同种多物品的研究领域中。异种物品拍卖， 由于其复杂性，学者多将其拍卖过程视为一件件同种物品的拍卖。然而在现实中， 对于异种物品的集合的估价，一般不等于对每个单独物品的估计之和。异种物品 的估价涉及两个基本作用：替代作用( 物品组合的价值低于单种物品的价值之和) 和互补作用( 物品组合的价值低于单种物品的价值之和) ，同时在现实中同样的 物品组合对于不同的竞标人，物品之间是替代作用还是互补作用还可能是不同 的，这就导致在研究物品的组合拍卖过程中，当物品的种类较多时，并不存在一 个多项式时间复杂度( 相对于物品种类的数量) 的算法，能够求解出最有效率的 分配结果。异种物品的组合拍卖是n p - h a r d 问题。 1 1 2 研究意义 作为一种市场经济条件下的成熟市场交易制度，拍卖对尚处于经济转型时期 的我国有很重要的现实意义。例如，企业和政府的采购已经越来越依赖于网上采 购的形式：通过网站发布采购信息，供应商竞标，采购方确定竞胜标的。 在现实采购过程中，对供应商的标的选择不能仅仅从产品的价格出发，还应 该考虑到供应商提供产品质量、产品服务等属性。同时由于拍卖物品间的替代以 及互补作用，建立产品的组合拍卖模型对于异种物品的拍卖有着更好的指导作 用。 因此，论文从实际出发，将产品的质量等属性加入到供应商产品效用的指标 体系中，并将得到的基于多属性的产品效用作为组合拍卖的评价指标，讨论了多 属性组合拍卖中竞胜标的确定，为政府和企业多物品采购行为提供理论指导。 1 2 国内外研究现状 1 2 1 拍卖基本理论 拍卖作为世界上最古老的价格发现机制之一，进入学术研究的领域却很短。 1 9 5 6 年，l a w r e n c ef r i e d m a n 2 1 提出一个求解第一价格密封投标的最有竟价策略的 2 第1 章绪论 模型；1 9 6 1 年，v i c k r e y 开创性的运用博弈论处理拍卖问题，并首次提出了拍卖 理论的基本模型一独立私人价值模型( t h ei n d e p e n d e n tp r i v a t ev a l u em o d a l ， i p v m ) 。v i c k r e y 分别研究了英式拍卖与第二密封价格拍卖、荷兰式拍卖与第一 密封价格拍卖四种不同的出价策略，针对竞买人对称的情形证明，荷式拍卖与英 式拍卖所产生的期望价格相同，即“收入等价定理 ( r e v e n u ee q u i v a l e n c e t h e o r e m ，r e t ) ，该定理是整个拍卖理论研究的起点。同时v i c k r e y 也指出荷式 拍卖中的盈利方差要小于英式拍卖，这意味风险厌恶的卖主更愿意选择前者。随 后，m y e r s o n 3 1 、r i l e y 和s a m u e l s o n 4 证明了收入等价定理，并得出最高信号的 竞买人总是赢家，以及拥有最低可行估价的竞买人的期望剩余为零；c a p e n 等【5 1 针对独立私人模型的不足提出了另一类模型，即共同价值模型( t h ec o m m o n v a l u em o d e l ，c ) ，在c v m 中，拍卖品的价值对所有投标商来说都是一样的， 其真实价值对投标商是不完信息，并且每个投标商对此做独立估计；m i l g r o m 和 w e b e r 6 】建立的“关联价值模型”( a f f i l i a t e dv a l u e ) 将独立私人模型和共同价值 模型都纳入其中并基于模型，得出了一个重要的期望收入排序关系：英式拍卖 第二价格密封拍卖第一价格密封拍卖= 荷兰式拍卖。 收入等价定理引起了卖主对各种机制的选择问题，即由于四种基本拍卖方式 产生的期望价格相同，在所有可能的拍卖机制中，卖主的选择问题。m y e r s o n 借 助于“显示原理”将最优机制的搜寻范围缩小到激励相容性直接机制上，并将最 优拍卖机制问题转化为一个双重约束下的线性规划问题：即在参与约束和激励相 容约束下求卖主的最大期望剩余。同时，m y e r s o n 以及r i l e y 和s a m u e l s o n 证明 了单物品最优拍卖机制：就是设定一个最优的保留价格，如果最高投标价超过了 保留价格，物品出售；否则拍卖人自己保留物品。但是单物品最优价格策略的结 果建立在投标者风险中性、独立是有估价并且对称的基础上，如果这些假设被更 改，那么最优价格策略也将改变；h a r s a n y 7 】研究估价的随机分布与竞价收益问 题，主张用理性的混合策略来达到保留点。 多物品拍卖相较单物品拍卖具有更高的实际意义，正成为拍卖理论中最为活 国v i c k r e y 在文中首先证明了英式拍卖与第二密封价格拍卖的期望相同以及荷兰式拍卖与第一密封价格拍 卖的期望相同。 3 混合型多属性组合拍卖模型研究 跃的研究领域。但是在多物品拍卖的情况下，最优拍卖问题异常复杂，只有在特 定的环境中取得了一些进展。m a s k i n 和r i l e y 8 】在假设所有单位同质及竞买人具 有单位需求的前提下证明了单物品拍卖中得出的许多概念和结论，例如收入等价 原理都可以推广到多物品拍卖中去，m a s k i n 和r i l e y 还将m y e r s o n 对最优拍卖机 制的分析扩展到大量同质物品拍卖的情形，他们证明，在正则性条件下，设置了 适当保留估价的标准拍卖机制对卖主而言都是最优机制。但是，若考虑竞买人可 能需要多个单位即需求曲线向下倾斜的一般情况，即便是设置了保留估价的标准 拍卖机制通常也不可能是最优的；在异质多物品拍卖的研究中，p a l f r e y 9 】分析了 一个垄断卖主在将异质物品捆绑销售和分开销售之间的偏好，并论证了卖方捆绑 销售的激励会随着竞买人数增加而下降；m c a f e e 和m c m i l l a n 1 0 】讨论了两件物品 的确定型绑定，而概率型绑定增大了对两件物品都估价较高的投标者的积极性， 从而在保证激励相容的条件时，最大化卖家的期望收益；a v e r y 和h e n d e r s h o t t 1 l 】 研究了最优拍卖中，其中一件物品竞争的加强会影响另一件物品的分配，而且这 种影响既可能是正的，也可能是负的。 国内对拍卖理论的研究多在拍卖机制的设定以及最优拍卖策略的研究上。 马俊等【1 2 】改进了英国式拍卖规则下两物品拍卖中投标商的投标决策模型， 研究了三物品拍卖中多个投标商的投标决策问题。并得出在两物品顺序拍卖中， 先拍卖高价值的物品对招标商是有利的结论；齐安甜等【1 3 】从企业角度出发，借 鉴博弈论与信息经济学中的有关原理，设计了企业并购的拍卖机制，并对该机制 下并购交易双方的报价行为进行了研究，得出了均衡状态下各局中人的最优策 略，从而对我国的企业并购实践提供一定的指导作用；乔恒等【1 4 】在收益等价性 及应用的完整框架下对四类拍卖的收益等价性问题进行了总结、研究和探讨。在 对收益等价定理进行推论和应用的基础上，确认了s i p v ( 对称、独立、私人价 值) 假设下四种拍卖期望收益与期望支付的等价性，推导了二价全支付拍卖的均 衡竞价策略。在此基础上比较并解释了s i p v 假设下四种拍卖均衡报价的排序关 系；杜黎等【1 5 】以e b a y 为背景，研究一类有代理的网上英式拍卖分析了网上拍卖 的动态进程，其中顾客逐个到达，卖方可以设置保留价也可以不设置保留价。基 此，在对顾客的到达过程与估价分布函数不作具体假设的一般情形下，证明了对 4 第1 章绪论 于个人价值独立模型，顾客到达就报价且报实价为占优战略。进而将此与文献中 关于关联价值模型下的均衡投标策略进行了比较分析，并解释了网上拍卖实践中 的一些现象。得出了个人价值独立模型及占优战略；詹文杰等【1 6 】以s m i t h 奥秘为 出发点对双向拍卖的研究进展进行评述，并从实验经济学角度研究双向拍卖机 制。范小勇等【1 7 】以组合双向拍卖分析为基础，运用整数规划的方法建立了一个 组合双向拍卖问题的一般化模型，分别对单一回合和多个回合的组合双向拍卖交 易机制进行了研究，并化简了双向拍卖组合问题；王彦等【1 8 】引入佣金提成的独 立私人价值模型及关联价值模型，研究佣金比例的大小对投标人的出价策略、卖 方和拍卖方的期望收益都有影响问题；张娥等【19 】讨论了w i n n e r 2 p a y 和a l l 2 p a y 两种不同支付方式下一类异质物品的一级价格拍卖机制的收益特性，以指导拍卖 者选择拍卖机制。这类异质物品拍卖广泛应用于网上广告位拍卖和比赛奖金分配 中，其特点是各拍卖物品价值具有相关性，投标者只投1 个标价，机制根据标价 的大小顺序进行物品分配。采用静态贝叶斯博弈分析方法，通过计算两种拍卖方 式下拍卖方期望收益，得出两种拍卖机制下拍卖方收益相等的结论；同时，证明 了投标者在w i n n e r 2 p a y 下的期望支付比a l l 2 p a y 高。从该文拍卖收益计算的特 例，还可计算得到k 件同质物品拍卖收益等于k + l 级密封拍卖的收益；罗掌华等 2 0 】分析了独立的私人估价环境下最优保留价格与竞买人数之间的关系，纠正了 最优保留价格与竞买人数无关的传统点。该文针对实际招标投标和现有有关拍卖 的文献中保留值设置方法的不足，研究了保留值的大小与投标商人数相关时的最 优保留值的设置方法，提出了在一定的假设条件下招标商的收益达到最大的定 理。 综合国内外对拍卖基本理论的研究，学者基于v i c k r e y 的理论框架以及假设 发展研究，且研究成果集中在对单物品拍卖的研究上。国外学者在研究过程中通 过改变假设扩展了拍卖的应用范围，国内学者对拍卖的研究较晚，主要集中在对 国外研究的证明和发展上。 1 2 2 多属性拍卖 1 9 9 0 年之前拍卖理论研究过程中对于单一物品的拍卖研究中仅仅考虑产品 混合型多属性组合拍卖模型研究 的价格，没有考虑产品的其他属性。然而在实际拍卖过程中，特别是采购( 反向 拍卖) 过程中，购买者往往需要考虑产品的更多属性，例如质量，提前期等属性。 故在9 0 年代，拍卖的问题已经越来越涉及多属性问题。关于多属性拍卖，b i c h i e r 等【2 1 】将其定义为：拍卖人与竞拍人交易时考虑到多个属性的一种拍卖模式，即 双方在价格以外其他属性上进行多重谈判的拍卖模式。 多属性拍卖首先要解决的是竞标者对各个属性的确定问题，通过对国内外文 献的整理，归纳以下四种基本方法：( 1 ) 直接引出竞标者的价值函数；b i c h i 一捌 在研究证券交易市场多属性拍卖，利用实证方法直接给出竞标者关于各个属性的 价值函数；( 2 ) 通过竞标者对各个属性的估价，将各个非价格属性直接转化为与 价格可以比较的值；t e i e h 等【2 3 】【2 4 】在研究过程中假设竞标者的标的直接对质量与 价格做出相同量纲的投标，黄河【2 5 1 在研究竟胜标问题前假设竞标者投标中对价 格和质量分别投标，再利用树形结构求解竞胜标问题；( 3 ) 通过拍卖者和竟标者 的交互，学习竞标者对各个属性的选择；b e i l 和w e i n 2 6 】设计了一个基于逆优化 拍卖机制支持多属性r f q 过程，他们假设收益函数和成本函数是相互独立的， 买方知道竞标者成本函数的形式，但不知道成本函数中各个参数的精确值。他们 将招标过程分为两个阶段：一阶段，信息不完全的条件下，通过多轮拍卖学习供 应商的成本函数信息；第二阶段，在信息完全的条件下，使用v i c k r e y 拍卖规则 确定供应商；( 4 ) 运用拍卖所有者特殊的拍卖途径；t e i c h 等【2 7 】利用i b m 的技术 框架通过建立在有没有存在价格折扣的不同情况下竞标者效用，探讨了竞标者的 选择。 多属性拍卖的机制设计也是多属性拍卖的重要研究方面。1 9 8 8 年，t h i e l 2 8 】 首次对多属性拍卖进行研究，指出如果卖方的偏好函数己知，多维采购问题最终 可简化为单一属性的采购问题；c h e 等【2 9 】证明了二维收入等价原理。考虑物品的 价格和数量两种属性，采用密封式拍卖，假设买方己知卖方的成本参数可能的概 率分布，并基于买方设定的评分标准给出了一种最高叫价暗标拍卖方法和一种第 二高叫价暗标拍卖方法；r o t h k o p f 和h a r s t a d 3 0 】指出单一产品，单一属性的拍卖 已经不是最具实用和普通的拍卖机制；b r a l l c o 【3 1 】改进了c h e 的多属性拍卖模型， 将成本影响加入模型中。并证明了最优效用不能通过拍卖过程来实现，以及两阶 6 第1 章绪论 段升价拍卖和两阶段拍卖执行的是最优的拍卖机制；b i c h i e r 等【3 2 】对多属性拍卖 进行了试验分析，通过随机产生若干个多属性拍卖问题，并利用单属性拍卖方法 对这些问题求解，结论是用单属性拍卖方法求解多属性拍卖问题会使效用大打折 扣。 多属性拍卖的信息机制反映了在拍卖期间以及拍卖结束时拍卖者将信息反 馈给竞标者的机制，是多属性拍卖的重要组成部分。k o p p i u s 3 3 】【3 4 1 以及k o p p i u s 和v a nh e c k 3 5 】研究了信息反馈从过去的公开出价、单轮密封投标到不提供反馈 信息给竞标者的改变。得出信息反馈的微小变化会对拍卖的结果产生显著影响； t e i c h 等【2 3 】【冽构建信息时，竞标者在投标过程中只能知道他们的标的状态是“活 跃一，“中等活跃 还是“不活跃，他们既不知道投标者的数目，也不知道当前 状态下“活跃 的标的数量。 多属性拍卖的竞胜标仍是拍卖问题中的核心，结合竞标者的属性的价值选 择，学者对竞标胜问题提出了各种解决办法。c h e 等、b r a n c o 以及b i c h i 一3 6 】通 过建立标的的效用函数并且进行比较选择竞胜标；t e i c h 等2 3 】【2 4 1 运用线性规划和 整数规划求满足质量条件的价格最小的竞标者；b e i l 和w e i n 的研究假设成本函 数和价值是可分的，并且通过学习竞标者的成本函数后进行选择竞胜标；而在特 殊的拍卖途径过程中，竞胜标的选择取决于是否存在价格歧视；国内对多属性拍 卖竞胜标选择研究较少，黄河等运用树形结构分析模型，通过比较解向量到最低 价格和最优质量的距离确定竞胜标。 通过对国内外多属性拍卖的研究，现有多属性拍卖的主要研究成果中仍存在 着较大不足。b i c h l e r 是采用线性加权平均的方法解决胜出者决定问题，但该方 法很难反映出各个决策方案的真实水平；c h e 试图应用多目标效用函数的方法解 决胜出者决定问题，但模型中对偏好独立的假设使得模型应用性差；b r a n c o 改 进了c h e 和b i c h l e r 的模型，用分配效率来描述整个拍卖的效果，但解决相应 n p h a r d 问题中采用的整数规划方法过于简化，而导致实际应用效果并不理想； b e i l 和w e i n 使用逆优化的方法学习成本函数，但是打分规则的构造过程过于复 杂，很难应用于实际。另外，在成本函数形式的制定过程中，忽略固定成本的讨 论，仅仅考虑供应商的变动成本。 7 混合型多属性组合拍卖模型研究 1 2 3 组合拍卖 组合拍卖是多物品拍卖的一种方式，主要用于不同物品间有互补影响、并且 投标人被允许在捆绑或不同物品的组合上提交投标的拍卖中。s o n g 等【3 7 】研究了 组合拍卖的例子，组合拍卖方式最早在1 9 8 2 年就被建议用于美国航空部门和市 政府拍卖飞机场的停机位，英国伦敦的运输部门也用组合竞投方式来分配巴士营 运的路线，以及货车运输公司对于运输合同的获得。 通过整理国内外的研究，组合拍卖的研究框架：组合拍卖机制在理论上包括 单一循环、第一价格密封竞标、v c g 机制、有均衡和出清价格的拍卖，和重复 的组合拍卖。组合拍卖的设计问题考虑预期问题、极限问题、以合理的速度保持 投标变动、避免和打破平局，以及控制复杂性【3 8 1 。研究涉及到四个主要方面： 竞标、分配、支付额以及策蝉3 9 1 。 组合拍卖的竞胜标问题作为组合拍卖的核心问题，它的求解决定了拍卖的结 果，它的求解效率直接决定了整个组合拍卖的有效性和实用性。可是，组合拍卖 的竟胜标确定问题是一个n p - h a r d 问题，引起了运筹学和人工智能领域学者广泛 的关注。 s a n d h o l m 删首先讨论了用穷举法的思想解决组合拍卖的竞标胜问题，他指 出该问题的可行解的精确数为：z ( m ，g ) ，其中m 表示物品总数，g 代表一种 q = i 可行方案中的物品组合个数，z ( m ，q ) 是第二类斯特林数，具有递推关系： z ( m ，g ) = q z ( m 一1 ，g ) + z ( 朋一1 ，q 一1 ) ，其中z ( m ，m ) = z ( m ，1 ) = 1 ；r o m d h o l m 【4 1 】等 运用动态规划进行求解，但动态归纳对于待拍项目数较大时无法取得最优解； a n d e r s o n 等【4 2 】将竞胜标问题归结为整数规划问题，提出了用g a r f i n k e l n e m b a u s e r 的集合分割算法求解竞胜标，在规模较大时，该方法仍有较好的表现；h o e s e l 等1 4 3 】提出用分枝定界法来求解问题，以及求解带有不等式约束的线性规划拍卖 问题。 为了避免以上各种精确算法对解空间盲目的搜索，学者运用启发式算法，在 算法设计中嵌入“智能知识 ，算法基于启发式规则进行搜索，提高了寻找最优 第1 章绪论 解的时间。s a n d h o l m 提出了最优任意时间启发式算法，通过生成树的形式来表 示问题的解空间，然后通过遍历生成树求得最优解；f u j i s h i m a 掣删提出基于市 场行情的启发式算法对问题做了两部分工作，一方面提出结构化搜索空间，一方 面构建虚拟代理对每个初始投标捆绑，并按照一定得策略对捆绑的每个商品提交 投标；p a r k 等【4 5 1 制定启发式规则给出了良好思路，给出三种标进行排列模式：( 1 ) 根据标价高低排列；( 2 ) 根据标包含的物品数量排列；( 3 ) 每个标与其他标有其 他标有物品冲突的标数；g o n e n 等【4 q 提出的分枝定界启发式算法都是针对多单位 组合拍卖竞胜标确定问题。 国内的学者对组合拍卖的研究主要集中在利用启发式算法，遗传算法求解组 合规划最优解上，陈培友，汪定伟【4 刀先是对竞胜标确定方法进行总结，归纳了 求解竞胜标的精确算法，近似算法，启发式算法和遗传算法；而后陈培友，汪定 伟运用改进型遗传算法对组合拍卖的竞胜标进行求解；黄河等【2 5 1 运用树形结 构并通过引入距离求解多属性采购组合拍卖的竞胜标；傅丽芳，冯玉强【4 9 】运用 关联规则求解竞胜标问题。 综合国内外对组合拍卖的研究来看，组合拍卖的竞胜标求解为n p - h a r d 问 题，当标的较少的时候，可以利用近似或穷举法求得解，而当物品和标的较多时， 需要通过启发式算法结合人工智能的一些算法求最优解。就趋势来说，运用遗传 算法求解组合拍卖正越来越得到关注，但是基本的遗传算法由于在寻找可行解上 的低效率，应当加上优化算子。 1 3 研究内容和方法 拍卖作为古老的价格机制，日益影响我们的生活。然而，随着经济的发展， 政府、企业等在采购中不能只考虑价格，还应当考虑供应商提供产品的质量，提 前期等属性，同时由于不同产品间可能存在互补或者替代的作用，组合拍卖也对 对政府、企业的采购有着实际意义。 综合考虑国内外对拍卖基本理论、多属性拍卖和组合拍卖的研究情况，存在 着不足：( 1 ) 学者在研究多属性拍卖理论，讨论非价格属性，多只是建立质量作 为唯一的非价格属性，在有的文章对质量属性加以细分的情况下，也仅仅是列举 o 混合型多属性组合拍卖模型研究 提前期、柔性两个属性加以讨论，并未对产品属性建立较完整的体系；( 2 ) 学者 在研究多属性拍卖理论，讨论产品效用，对质量等非价格属性以估价的方式得到 效用，然而在实际中，供应商很难直接给出质量等属性的准确估价，只能给出成 品率等定量值；( 3 ) 学者在研究组合拍卖理论时，由于解空间的复杂性，多只考 虑单物品的拍卖，多物品的组合拍卖业只是将多物品组合拍卖看作多个单物品进 行拍卖。 本文结合多属性拍卖和组合拍卖研究的不足，以以下三个部分探讨多属性组 合拍卖机制为政府和企业多物品采购行为提供理论指导： ( 1 )构建数学模型，讨论购买者在有两个供应商的条件下，两种考虑质量属 性的不同拍卖方法的效用期望差，同时利用仿真观察当参与拍卖的供应商逐渐增 多以及在质量门槛逐渐增大的情况下，两种拍卖方式的效用期望差。通过计算， 比较得出多属性拍卖中标的的效用对于购买者的价值； ( 2 )通过文献资料法构建产品的效用指标体系，考虑到指标中只含有实数值 且量纲不一样，建立多属性混合型决策求得各个指标权重，利用各指标效用值求 得标的效用值，最后给出算例； ( 3 )构建组合拍卖的整数规划模型，将多属性拍卖标的效用值代入构建多属 性组合拍卖模型，由于模型求解问题为n p h a r d 问题，利用求解背包问题的单亲 遗传算法求得最优解。 1 4 章节安排和研究逻辑框架 本文首先通过数学模型以及计算机仿真比较在已知供应商产品的质量估价， 和购买者设置质量门槛后通过价格进行竞胜标确定这两种多属性拍卖模型的效 用差值，通过比较得出在多属性拍卖中标的各指标效用的确立对采购者的价值。 由于产品的非价格属性并没有统一标准，而且难以直接对各个属性进行估价，为 准确得到产品各个指标的效用，论文采用文献资料法整理建立了产品的效用指标 体系，并且通过多属性混合决策求得各个指标权重从而得到多属性拍卖中产品的 效用值。最后，在已得到产品多属性拍卖的效用值基础上，建立多属性拍卖的整 数规划模型，由于模型的竞胜标确定是n p h a r d 问题，利用单亲遗传算法对模型 1 0 第1 章绪论 进行求解。本文的章节安排和逻辑框架如图1 - 1 ： 论述了研究的背景和意义并通过对国内 外关于拍卖基本理论、多属性拍卖和组 合拍卖研究的情况，介绍研究方法 首先介绍了多属性拍卖的特点和使用范围， 以及介绍组合拍卖和背包问题间的映射关 系，进一步验证了单亲遗传算法在组合拍卖 问题中的可行性对待研究问题做出综述 两章主要讨论多属性拍卖问题，第三章介绍 了通过数学模型以及仿真比较多属性拍卖两 种方式下用户的效用期望，通过第三章的比 较可以得出多属性拍卖中构建拍卖者效用函 数的重要性。第四章基于第三章结论的重要 性首先通过对中外研究的整理构建产品的指 标体系，然后运用混合多属性决策理论得出 各指标的权重进而得到效用值 在得到多属性拍卖物品效用的基础上，建立 组合拍卖模型。建立多物品混合多属性组合 拍卖的整数规划模型，由于模型的竟胜标确 立是n p h a r d 问题，利用单亲遗传算法求解 并对算法进行优化 对论文的研究进行总结，并指出下一步的 研究方向 图1 - 1 ：论文的研究逻辑框架 混合型多属性组合拍卖模型研究 2 1 多属性拍卖 2 1 1 拍卖的划分 第2 章多属性组合拍卖问题综述 拍卖根据拍卖物品的特点，可以划分为八种不同的类型，如图2 1 所示： 图中y 轴代表属性，x 轴代表物品，z 轴代表单位。 物品 x 多单位 图2 1 ：拍卖的维度划分 资料来源：b i c h l e rm 。l a w r e n c erd a p p l i c a t i o n so f f l e x i b l ep r i c i n gi nb u s i n e s s t o - b u s i n e s se l e c t r o n i c c o m m e r c e 明i b ms y s t e m sj o u r n a l ，2 0 0 2 ，4 2 ( 2 ) ：2 8 7 - 3 0 2 类型1 是一种单一物品、单一单位、仅针对价格的传统拍卖方式。拍卖物品 的属性和数量都是固定的，不允许进行协商； 类型2 是一种单一物品、多单位、仅针对价格的拍卖方式。与类型l 不同， 这种拍卖方式不仅可以就拍卖物品的价格，而且可以就拍卖物品的数量进行协 1 2 第2 章多属性组合拍卖问题综述 商，也称为多单位拍卖； 类型3 是组合拍卖的一种简化形式，是一种仅针对价格、固定数量、多物品 的拍卖方式。这种拍卖方式允许竞价人把多个拍卖物品看作一个标的来竞标，与 其他拍卖机理比较，组合拍卖不仅能够提高拍卖的效率，而且还能降低竞标人的 风险； 类型4 是一种简化的多属性拍卖方式，允许就包括价格在内的多种属性进行 协商，但数量是固定的，并且拍卖物品单一； 类型5 是类型3 的拓展，允许就数量进行协商，是一种广义上的组合拍卖； 类型6 是类型4 的拓展，允许就数量进行协商，是一种广义上的多属性拍卖； 类型7 是一种多属性、多物品拍卖，但数量是固定的； 类型8 是一种完全意义上的多维拍卖，允许就多属性、多物品、多单位等三 个维度进行协商。 2 1 2 多属性拍卖特性分析 多属性拍卖主要适用于以买方为中心的反向拍卖，例如企业的采购环节，但 其基本原理也同样可以应用于正向拍卖。由于当前市场的驱动力已经由产品的特 性转变为客户的需求，企业对客户关系管理的重视日益增强，这种以买方为中心 的反向拍卖也将具有更为广泛的应用性。文章主要研究多属性组合拍卖的反向形 式。拍卖者为采购方，即购买者，竞标者为供应商。 多属性拍卖的客体即拍卖中的标的物，也就是买方需求的产品或服务。企业 采购的对象可以分为三类：企业生产所必需的生产性直接原材料；维持企业生产 活动持续进行的维护修理装配等间接物料，包括备品备件、零部件等，比如润滑 油等；以维持企业运作所需的行政性日常用品：如写字桌、计算机等。通常我们 又把第一种物料称为直接生产物料( d i r e c tm a t e r i a l ) ，把后两种物料称为m r o ( m a i n t e n a n c e ，r e p l a c ea n do p e r a t i o n ) 物料，即间接物料( i n d i r e c tm a t e r i a l ) 。 对于直接生产物料，供应商相对比较固定，以长期供货合同或一定期间内稳定的 价格供货，有专门的采购部门和采购人员负责各类原材料的采购。物料价格比较 高、批次比较多、重复性大。对于m r o 物料，价格相对较低，采购周期不定， 供应商来源广泛，价格随采购批次变动可能较大，相对采购成本较高。 混合型多属性组含拍卖模型研究 2 1 3 多属性拍卖的特点和适用范围 多属性拍卖具有以下主要特点： ( 1 ) 多属性拍卖需要竞标者在提交标的时包含各个属性指标值 多属性拍卖区别于基本拍卖的本质就是多属性拍卖对产品效用从多个维度 考虑，产品属性会影响拍卖双方对产品的效用估值，所以在拍卖过程中需要竞标 者在提交标的时包含各个属性指标值，以便购买者对标的进行综合评价确定得标 者。 ( 2 ) 多属性拍卖决策过程更为复杂 多属性拍卖考虑的维度较大，且适用环境复杂。所以多属性拍卖在高度复杂 的搜索空间寻找权衡十分重要。 ( 3 ) 多属性拍卖的应用范围广泛 多属性拍卖是传统拍卖理论的拓展，允许买卖双方就质量、交货时间、颜色 等非价格属性进行协商。而传统拍卖只能就价格进行协商，相对而言具有一定的 局限性。 多属性拍卖作为特殊的拍卖方式，适用范围有一定的局限性。根据多属性拍 卖的特点和拍卖方式，多属性拍卖主要有适用以下情况： ( 1 ) 拍卖客体应该较为规范和容易定义 对多属性拍卖进行过程中的细节描述可以为广大供应商所理解。对产品的细 节描述是保证供应商做出正确报价的前提和保证，否则必然导致竞价过程中的混 乱和事后大量纠纷的产生。 ( 2 ) 供应商之间存在较强的竞争性 即有较多的供应商可以提供同类产品。多属性拍卖需要有足够供应商参与竟 价，以便发挥出其自身优势。如果供应商在市场中存在垄断性的优势，那么这种 产品也不适用于以多属性拍卖的方式采购。 ( 3 ) 采购方处于垄断性地位 多属性拍卖是一种特殊类型的拍卖。它主要应用在买方垄断的情况，例如： 政府或者大型公司采购。买方在拍卖过程中具有较强的控制力。 ( 4 )多属性拍卖适用现有采购合同中没有的产品或服务 多属性拍卖只是一种协商方式，它并不会代替传统的采购流程。它多用于采 1 4 第2 章多属性组合拍卖问题综述 购现有采购合同和采购目录中没有涉及的产品或服务，或者重新审定现有的产品 或服务合同和重新谈判的情况。 2 2 组合拍卖与背包问题的联系 背包问题( k n a p s a c kp r o b l e m s ，k p ) 是一个在运筹学领域常见的典型n p - h a r d 问题，广泛应用于生产、金融、物流等多个领域中，包括工厂生产下料问题、企 业资源分配、资金预算、投资决策、股票交割以及运输装载等等。一般提到的背 包问题是指在背包总重量限制的条件下，从多件不同价值、不同重量的物品中选 取一部分物品放入背包，使得选中物品的价值之和最大。而这里说的背包问题是 个广义上的背包问题，代指背包问题领域中各种类型的背包问题，包括多背包问 题，多维背包问题，多目标背包，无限制背