（计算机软件与理论专业论文）组合拍卖问题及其智能优化算法的研究.pdf

组合拍卖问题及其智能优化算法的研究 计算机软件与理论 博士生：白鉴聪 指导教师：常会友 摘要 组合拍卖是解决各种资源分配问题的有效机制，随着电子商务的发展，组合 拍卖机制发展成为一种新的多方交互与决策的电子谈判模式，是当前电子商务的 一个重要应用领域。组合拍卖问题是组合拍卖理论的研究核心之，是n p 难题。 浚问题的优化与求解直接影响到整个组合拍卖机制的有效性与实用性，有着极高 的理论研究价值和广泛的应用前景。 本文主要研究基于组合标集的单数量组合拍卖问题和多数量组合拍卖问题， 目前，国内外文献对整合了组合标集的组合拍卖问题尚未见有较深入的优化求 解。为此，本文对这两种基于组合标集的组合拍卖问题进行研究，对问题的优化 求解开展了以下工作： 1 、对组合拍卖问题原型进行了研究，分析了组合拍卖问题与多维背包问题 的关系，揭示了两种基于组合标集的组合拍卖问题模型均派生于多维背 包问题模型。 2 、对基于组合标集的单数量组合拍卖问题建立了o 1 整数规划模型。分析了 单数量组合拍卖下的组合标集特性，提出多项启发式规则并设计相应的 预处理方法对问题进行优化，有效地缩减求解空间。 3 、针对单数量组合拍卖的特性，设计薪的评价策略和评价函数，更准确评 估标进入最优解的可能性。提出单亲算子与免疫算子相结合的启发式算 法对问题进行求解，免疫算予利用评价函数将问题的特征知识引入到算 法求解中，减少了冗余搜索，提高算法搜索效率。仿真测试表明该算法 能够有效地解决大规模问题，而且表现出良好的求解性能。 4 、对基于组合标集的多数量组合拍卖问题建立了0 1 整数规划模型。分析了 多数量组合拍卖下的组合标集特性，提出多项启发式规则并设计相应的 预处理方法优化求解， 5 、针对多数量组合拍卖的特性，提出启发函数评价标的综合效益。提出了 加入优化算子的单亲遗传算法进行求解。优化算子利用启发函数分析并 改善染色体的基因组成，提高种群平均适值，引导搜索往好的方向进行。 计算结果验证了算法的有效性，算法能够适用于不同规模不同情况的多 数量拍卖，有着良好的性能。 关键间： 组合拍卖问题，智能优化算法，多维背包问题，单亲遗传算法，免疫 遗传算法 1 】 c o m b i n a t o r i a la u c t i o n sp r o b l e ma n di t si n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：b a tj i a n c o n g s u p e r v i s o r ：p r o f e s s o rc h a n gh u i y o u a b s t r a c t c o m b i n a t o r i a la u c t i o n sa r ee f f i c i e n tm e c h a n i s m sf o ra l l o c a t i n g r e s o u r c ei n c o m p l e xm a r k e t p l a c e a n dt h e yp r o v i d e af o u n d a t i o nf o rm e d i a t i o na n db r o k e r i n gi na v a r i e t yo ft a s ka n dr e s o u r c ea l l o c a t i o np r o b l e m s w i t ht h ep o p u l a r i t yo fe - b u s i n e s s c o n t i n u i n gt or i s e ，c o m b i n a t o r i a la u c t i o n sd e v e l o pa sn e ww a y sf o rf u l l ya u t o m a t e d e l e c t r o n i cn e g o t i a t i o ni n m u l t i p l ep a r t i e s ，a n db e c o m e a ni m p o r t a n ta r e ai nt h e e l e c t r o n i cc o m m e r c e c o m b i n a t o r i a la u c t i o np r o b l e m , w h i c hi sn p c o m p l e t e ，i st h e c o r ep r o b l e m si nc o m b i n a t o r i a la u c t i o n s t h eo p t i m i z a t i o na n ds o l u t i o no ft h i s p r o b l e mh a v ed i r e c te f f e c to nt h ev a l i d 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 y c a ni m p r o v et h ep r a c t i c a b i l i t yo f t h ea u c t i o n s t h er e s e a r c hf o rc o m b i n a t o r i a la u c t i o n p r o b l e mh a si 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 n s ， i n t h i sd i s s e r t a t i o n ，t h e r ea r et w oc 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 t hb i d b u n d l e s ：s i n g l e u n i tc o m b i n a t o r i a la u c t i o n sa n dm 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 u p t on o wt h e r ea t ef e wp u b l i s h e dl i t e r a t u r e si nw h i c he f f e c t i v em e t h o d sc a nb ef o u n dt o s o l v et h ec o m b i n a t o r i a la u c t i o np r o b l e m sw i t hb i db u n d l e s s ow ef o c u so nt h e s et w o p r o b l e m sw i t hb i db u n d l e s ，a n dt h ei n v o l v e dw o r k sa r ep r e s e n t e da sf o l l o w i n g ： 1 t h er e l a t i o n s h i pb e t w e e na u c t i o np r o b l e m sa n dk n a p s a c kp r o b l e m sa r ed i s c u s s e d a n di ts h o wt h a tc o m b i n a t o r i a la u c t i o np r o b l e m sc a nb ef o r m u l a t e da s m u l t i d i m e n s i o n a lk n a p s a c kp r o b l e m s t h ep r o t o t y p eo ft h e s et w oc o m b i n a t o r i a l a u c t i o n sp r o b l e mi st h em u l t i d i m e n s i o n a lk n a p s a c kp r o b l e m i i l 2az e r o o n em i x e dm a t h e m a t i c a lp r o g r a m m i n gm o d e li s c o n s t r u c t e df o r t h e s i n g l e - u n i tc o m b i n a t o r i a la u c t i o np r o b l e mw 曲b i db u n d l e s b ya n a l y z i n gt h e c h a r a c t e r so fb i db u n d l e si nt h es i n g l e u n i tc o m b i n a t o r i a la u c t i o n s ，s o m eh e u r i s t i c r u l e sa n dp r e p r o c e s s i n gm e t h o d sa r cp r e s e n t e d t h ep r e p r o c e s s i n gm e t h o d sc a l lb e a p p l i e dt of i n do u tt h en o n c o m p e t i t i v eb i d sa n dn o n c o m p e t i t i v et u p l e so f b i d s 3 a ni m m u n ep a r t h e n o - g e n e t i ca l g o r i t h m i s p r o p o s e d f o r s o l v i n g t h e 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 np r o b l e mw i t hb i db u n d l e s b a s e do nt h ep r o b l e m k n o w l e d g et h a to n l ys i n g l eu n i ti sa v a i l a b l eo f e a c hi t e m , s o m en e w h e u r i s t i c sa r e d e s i g n e df o re v a l u a t i n gb i d s a n dt h e ya r ea p p l i e d i nt h ei m m u n eo p e r a t o n s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h ma c h i e v e sg o o dp e r f o r m a n c ei nl a r g e s i z ep r o b l e m sa n dt h ei m m u n eo p e r a t o rc a l li m p r o v et h es e a r c h i n ga b i l i t ya n d i n c r e a s et h ec o n v e r g i n gs p e e dg r e a t l y 4 az e r o o l l em i x e dm a t h e m a t i c a lp r o g r a m m i n gm o d e li sc o n s t r u c t e df o rt h e 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 np r o b l e mw i t hb i db u n d l e s b ya n a l y z i n gt h e c h a r a c t e r so fb i db u n d l e si nt 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 ，s o m eh e u r i s t i c r u l e sa n dp r e p r o e e s s i n gm e t h o d sa r ep r e s e n t e d t h ep r e p r o c e s s i n gm e t h o d se a r l b e a p p l i e df o rp r u n i n gi nt h es e a r c h i n gp r o c e s s 5 c o m b i n e dw i t ha ni m p r o v e m e n to p e r a t o r , ap a r t h e n o g e n e t i ca l g o r i t h mi s p r e s e n t e df o rt 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 np r o b l e mw i t hb i db u n d l e s a c c o r d i n gt h ep r o p e r t i e so ft 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 ，n e wh e u r i s t i c s a r ed e s i g n e df o rb i d s e v a l u a t i o n b yu s i n gt h e s eh e u r i s t i c s ，t h ei m p r o v e m e n t o p e r a t o rc a l le n h a n c et h ef i t n e s so ff e a s i b l es o l u t i o n ，a n dh e l pt h ea l g o r i t h m s e a r c h i n gf a s t e r t h es i m u l a t i o na n a l y s i ss h o w st h a tt h ea l g o r i t h mi ss u i t a b l ef o r d i f f e r e n tk i n d so f p r o b l e m sa n dh a sw e l ls e a r c ha b i l i t y k e yw o r d s ： c o m b i n a t o r i a l a u c t i o n s ，i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ， m u l t i d i m e n s i o n a lk n a p s a c kp r o b l e m ，p a r t h e n o - g e n e t i ca l g o r i t h m ，i m m u n eg e n e t i c a l g o r i t h m v 巾山大学博士学位论文 组合拍卖问题及其智能优化算法的研究 1 1 问题的研究背景 1 1 1 拍卖的发展与现状 第1 章绪论 在久远的人类历史发展中，拍卖是世界上最古老的价格发现机制之一，最早 可以追溯到公元前5 0 0 年的巴比伦。拍卖的最大特点是，价格由竞争的方式决定， 不是由卖方说了算，也不是由买卖双方讨价还价来确定。在当今的经济生活中， 拍卖已成为一种解决各种资源分配问题的有效机制。在当前市场经济中，商品、 能源、服务、土地、生产能力等等均可视为某种资源( r e s o u r c e ) ，而种种资源分 配的问题广泛地存在于各个经济领域中。这些问题的解决过程往往是一个多方交 互与决燕的过程。问题能否得到很好地解决，往往取决于交互决策机制的设计是 否合理有效。拍卖j f 是一种非常有效的分配机制，它引入了竞争，揭示了拍卖物 晶对竞标者的真实价值，使得拍卖方得到更大的收益。 随着全球经济一体化发展，信息技术同新月异，拍卖作为一种历史悠久的商 晶交易方式，面临种种机遇与挑战，在新的一轮经济发展浪潮重新焕发活力，得 到广泛深入的应用： 1 、拍卖市场国际化。一方面随着全球经济一体化发展，老字号的拍卖行纷 纷开辟国际市场，将拍卖业务扩展到世界各地，例如百年老店的索斯比 拍卖行、克罩斯蒂拍卖行都进入中国拓展业务。另一方面，拍卖网站作 为新一代的网上拍卖平台，跨越了地域空间的距离限制，人们无论身处 何地，只要通过互联网就可以进入拍卖网站参与竞投，例如e b a y l l l 就是 一+ 个非常成功的网上拍卖平台。 2 、拍卖物品多样化。随着拍卖网站的出现，拍卖已成为一种简单方便的商 品交易方式，可供拍卖的物品种类只益增多。过去的拍卖物品以有形资 产为主，价值高，数量少，例如文物古蓖、珠宝首饰等。而如今的拍卖 物品可谓花样百m ，层出不穷，从f | 常生活用品剑飞机人炮，乃至无形 山天学冉土学位论文 组台拍卖廿j 题及其智能优化算法的研究 的q q 号码、网络域名等都可以参与拍卖。 3 、拍卖模式的多样化。由于拍卖物品的多样化，不同种类的物品需要不同 的拍卖模式才能取得更好的拍卖效益。例如，在电子供应链中采用反向 拍卖的模式，采购商与供应商通过电子商务平台进行网上采购与竟标， 快速有效地完成跨国电子交易。目前，微软、e b a y 等纷纷推出了反向拍 卖电子业务。 4 、拍卖实时性的变化。由于互联网技术的出现，大大了缩短了拍卖各方交 互的时问，拍卖的实时性得到极大的提高，例如在网上竞拍，标价往往 在一分钟内产生多次变化，拍卖方与竞投方都能通过网页进行实时跟踪 与投标。 5 、电子拍卖的安全性。由于网上拍卖的出现，使得任何人、任何机构都可 以成为拍卖中买家或卖家，而且拍卖过程通过网络进行，这些都给电子 安全带来很大的考验，例如拍卖各方身份真实性验证，客户资料保密， 防止恶意竞标，保证竟标的不可否认性等。 6 、拍卖规则趋于完善，拍卖立法f | 益健全。在长期的拍卖实践中，各拍卖 行总结出一系列适合于拍卖活动的规则，这些f i 益成熟的规则成为各国 拍卖立法的基础。拍卖规则、拍卖立法有助于拍卖市场的规范化，有助 于平衡拍卖当事人的权利义务，反过来又促进了拍卖业的发展。 经济学家通过四十多年的研究，发展整套系统的经济理论来理解和分析拍 哎机制的优越性。如今，拍卖机制在经济理论的指导下，在现实经济生活中得到 - f r + 泛的应用，例如，美国通讯部采用了最新设计的拍卖机制，分配提供个人通 讯服务的执照，美国财政带来2 0 0 多亿美元的收入，美国财政部每周一次对期限 为9 1 天和1 8 2 天的证券进行拍卖，以及中国政府与事业单位的采购等。拍卖问 题的研究目前已经成为微观经济学重要的组成部分，并且对该理论的研究也扩展 到应用经济学以及产业组织理论等领域。 | 1 2 拍卖理论的发展 j 1 f 戈理论进入经济学文献的时删相当晚，拍卖最早的两篇开创性论文分析发 r p 山大学博士学位论文 组合拍囊问题及其智能优化算法的研究 表于1 9 5 6 年和1 9 6 1 年。直到2 0 世纪7 0 年代末，越来越多的博弈论研究者意识 到拍卖是一种简单而又具有完备定义的信息不对称经济环境，它是分析经济主体 之间的不完全信息博弈的一个颇有价值的实例，其经验研究前景也非常诱人。与 此同时，实验经济学者对于可控拍卖实验的兴趣也不断高涨。在这一背景下，拍 卖理论逐渐被主流经济学家所接纳，并大量运用博弈论、实验以及经验检验作为 拍卖理论的研究工具。近十多年来，国际经济学界关于拍卖问题的研究文献如阿 后春笋般地涌现出来，拍卖理论也已经作为一个专门体系进入中高级微观经济学 的核心领域【2 l 。 对于标准拍卖类型，各国学者己进行了相当深入的研究，相关文献【3 1 对于传 统拍卖的机制理论、经济模型等方面已经有了相当详细的分析与说明。随着互联 网技术以及电子商务的发展，电子拍卖应用日益广泛，拍卖物品、拍卖机制以及 拍卖认证等多个拍卖元素同趋多样化、复杂化，这些都给拍卖理论研究带来了新 热点，新挑战。在众多研究方向中，组合拍卖1 4 1 是其中一个非常重要的研究领域 j 热点。 组合拍卖属于多物品拍卖的一种方式，它允许竞标者对不同物品的组合提交 投标，与传统拍卖方式相比，组合拍卖提高了拍卖的经济效率2 1 ，降低了竞标者 的风险。近年来，关于组合拍卖领域的研究文献不断涌现5 圳，使得组合拍卖在 电子商务的理论研究与实践应用中具有极高的研究价值。 1 2 选题意义与目的 无论对何种拍卖模式进行研究，最直接面临的问题就是获胜者确定问题 ( w i n n e rd e t e m a i n a t i o np r o b l e m ，w d p ) ，组合拍卖中的获胜者确定问题又可以称 为组合拍卖问题( c o m b i n a t o r i a la u c t i o n s p r o b l e m , c a p ) 。该问题的实质就是在所 有标中选择最佳分配方案以使得拍卖结果达到最优。 组合拍卖问题是组合拍卖理论的研究核心之一，也是实际拍卖模式常常遇到 的问题1 9 ，】。该问题的优化与求解直接影响到整个组合拍卖机制的有效性与实用 性。该问题的研究与解决能够为组合拍卖理论研究带来直观的影响和效用，有着 极高的理沦研究价值和广泛的应用前景。 本文研究目的是：研究组合拍卖问题的特性及其解决方法，探索将，应用于 山大学博士学位论文 组台拍卖问题及其智能优化算法的研究 实际拍卖中的可能性。通过深入研究该类问题的性质，建立完整的o 一1 整数规划 模型，设计基于特征知识的启发式规则、优化方法以及评价函数。结合智能优化 算法，针对问题特征提出智能搜索方法，设计有效的启发式算法求解问题。模拟 实际应用，设计多个仿真试验，通过大量实例运算检验算法对不同规模问题的可 行性、适用性以及运算效率。从理论和实践上探讨解决组合拍卖问题的有效途径， 为将来的进一步完善与发展提供必要的理论和技术基础。 1 。3 主要研究工作 组合拍卖问题属于一类组合优化问题，该类问题的优化与求解是一项复杂而 困难的研究工作。本文针对其中几个问题进行了比较全面深入地研究。 研究了组合拍卖机制理论。 在了解组合拍卖的市场应用情况的基础上，对组合拍卖的总体机制进行了分 析。对组合拍卖问题目前的算法理论进行了研究，了解到目前将组合拍卖问题与 组合标集整合在一起研究的工作不算很多，有着很大的研究空问，因此确定了本 丈研究的目标是基于组合标集的组合拍卖问题。 研究了相关的智能优化算法。 研究了组合拍卖问题的相关算法，了解到目前算法受问题规模影响较大，算 法性能随着规模扩大而迅速下降。在学习研究了相关智能优化算法理论后，确定 采用单亲遗传算法作为算法主体，针对具体不同问题加入不同算子对问题进行优 化求解。查阅的相关文献包括： 组合拍卖机制 组合拍卖问题的相关理论与方法 遗传算法 啦亲遗传算法 免疫规划与免疫遗传算法 智能优化算法在组合优化领域的应用 组合拍卖问题的原型分析。 研究了拍卖问题与背包问题的紧密联系：对于各种拍卖模式下的获肚者确定 # 山大学博士学位论文组台拍卖问题披其智能优化算法的研究 问题，在一定约束条件下，均可转化为相应的背包问题。由于组合拍卖属于多物 品拍卖，拍卖物品种类与背包数量相对应，因此组合拍卖问题的原型对应于多维 背包问题。 单亲遗传算法求解多维背包问题 用单亲遗传算法对多维背包进行求解，验证单亲遗传算法在该类型问题的性 能，为下一步的具体研究做准备。 基于组合标集的单数量组合拍卖问题 对每种拍卖只有一个的条件下，基于组合标集的组合拍卖问题进行了一般性 描述，提出了0 1 整数规划模型。分析组合标集的特性提出多条启发式规则，并 设计相应的预处理方法优化求解。设计了单亲算子与免疫算予相结合的启发式算 法来求解问题。针对物品单数量的特点，提出多个标评价函数并应用在免疫算子 中，使得启发式算法能够充分利用问题特征知识，提升搜索效率。最后，设计了 多种类型的测试数据模拟真实情况，通过大量实例运算检验算法的可靠性与有效 性。 基于组合标集的多数量组合拍卖问题 在每种拍卖物品数量均为多个的情况下，对基于组合标集的组合拍卖问题进 行了一般性描述，提出了o 一1 整数规划模型。结合多数量的特点，基于组合标集 特性提出了启发式规则，并设计相应的预处理方法优化求解。设计优化算子引导 求解搜索方向。采用单亲遗传算法求解该问题。 1 4 研究的技术路线 如上所述，研究工作主要如下的技术路线进行： 调研国内外组合拍卖领域的应用于发展一= )分析组合拍卖问题的研究现 状，确立具体问题研究方向一) 查阅智能优化算法的相关文献，确定优化求 解的思想与算法一) 分析问题原型并求解一) 研究并求解单数量组合拍卖 f u j 题一) 研究并求解多数量组合拍卖问题。 从研究剧题和关联模型来看，技术路线如下图1 1 ，1 - 2 ： 组合拍卖问题及其智能优化算法的研究 图1 - 1 本文问题路线 图1 - 2 本文模型路线 6 p 山大学博士学位论文 组合拍卖问题及其智能优化算法的研究 第2 章组合拍卖问题研究综述 2 i 组合拍卖的发展与研究 随着信息技术与电子商务的发展，拍卖从古老的价格发现机制发展成为一种 多方交互与决策电子谈判模式，广泛应用在各个经济领域的资源分配问题中。随 着市场经济发展，传统的拍卖机制已经不能适应经济环境的变化，多种新型的拍 卖方式应运而生，组合拍卖就是其中一种非常有效灵活的机制。 组合拍卖起源于多物品拍卖。在拍卖多件不尽相同的物品，一种实用的设计 是同时增价拍卖( s i m u a a n e o u s a s c e n d i n g a u c t i o n ，s a a i h 。s a a 拍卖中，物品 在一系列循环中被同时拍卖。在每个循环中，每个投标人可以在任何物品上提交 投标，规定用最小投标增量来提高标价，直到没有投标人愿意在任何物品上竞投 更高的标价时拍卖结束【l ”。当物品问有比较强的互补性，买方倾向于对一个或 多个物品的组合提交投标，即“组合投标”的形式，相应的拍卖形式就是组合拍 卖( c o m b i n a t o r i a la u c t i o n ，c a ) 。组台拍卖是指投标人可以对所有物品的任何组合 投标，并提出相应的价格，也可以同时对几个组合投标提出相应的价格。给定所 有投标组合及价格，拍卖人使用计算机计算出收益最大化的结果，并将该结果公 稚于众”j 。 组合拍卖与传统拍卖方式相比，竞标者通过组合表达了他们对拍卖物品的真 实需求，竞标更加灵活多变，大大提高了拍卖效率。同时与单个物品逐项拍卖不 同，竞标者不必为所需的每个物品给出较高的标价，只需对一揽予物品给出总标 价，从而降低了竞标风险。对于拍卖者来说，物品组合给予了竞标者极大的自由， 大大激励了竞标者的参与热情，从而降低了流标的风险，而且拍卖者很可能会获 得高于“1 + 1 ”的组合收益。 学术上公认的组合拍卖应用典型是r a s s e n t i 等人在1 9 8 2 年提出用组合密封 投标拍卖程序来实现机场停机位的拍卖，它允许提交航程相容单独机场降落或起 b 空位的组合，从而解决空位的分配，并且决定单独( 空位) 资源的价格。随后， g r e t h e re ta 1 ( 1 9 8 9 ) 以及m c c a b ee ta 1 ( 1 9 9 1 ) 也提出了类似的结沦。 山大学博士学位论文 组合扪妻问题厦其智能优化算法的研究 第2 章组合拍卖问题研究综述 2 1 组合拍卖的发展与研究 随着信息技术与电了商务的发展，拍卖从古老的价格发现机制发展成为种 多方交互与决策电子谈判模式，广泛应用在各个经济领域的资源分配问题中。随 着市场经济发展，传统的拍卖机制己经不能适应经济玮境的变化，多种新型的拍 卖方式应运而生，组合拍卖就是其中一种非常有效灵活的机制。 组合拍卖起源于多物品拍卖。在拍卖多件不尽相同的物品，一种实用的设计 是同时增价拍卖( s i m u l t a n e o u s a s c e n d i n g a u c t i o n ，s a a 1 1 1 。s a a 拍卖中，物品 住系列循环中被同时拍卖。存每个循环中，每个投标人可以在任何物品上提交 投标，规定用最小投杯增量来提高标价，直到没有投标人愿意在任何物品上竞投 更高的标价时拍卖结束 ”1 。当物品间有比较强的互补性，买方倾向于对个或 多个物品的组合提交投标，即“组台投标”的形式，相应的拍变形式就是组合拍 冀( c o m b i n a t o r i a l a u c t i o n ，c a ) 。组台拍卖是指投标人可以肘所有物品的任何组合 投标，并提出相应的价格，也可以同时对几个组合投标提出相应的价格。给定所 有投标组合及价格，拍卖人使用计算机训算出收益最大化的结果，并将该结果公 和于众【； 。 组合拍卖与传统拍卖方式相比，竞标者通过 h 合表达了他们对拍卖物品的真 安需求，竞标更加灵话多变，大大提高了拍囊效率。同时与单个物品逐项拍卖不 嗣，竟标者= _ l = ：必为所需的每个物品给出较高冉勺标价，只需对一揽予物品给出总标 价从而降低了竞标风险。对于拍卖者来说，物品组合给子了竟标者极大的自由， 大大激励了竞标者的参与热情，从而降低了流标的风险，而且拍卖者很可能会毅 衔高于“l _ l ”的组台收益。 学术上公认的组合拍卖应用典型是r a s s e n t i 等人在1 9 8 2 年提出用组合密封 投标拍卖 2 序来实现机场停机位的拍卖，它允许提交航程相容单独机场降落或起 b 空位的组合，从而解决空位的分配，并且决定单独( 空倚) 资源的价格1 ”。随后， g f e t h e re la lt t 9 8 9 ) 以及m c c a b ee ta 1 ( 1 9 9 1 ) 也提山了类似的结沦。 g r e t h e re ta 1 0 9 9 9 ) 以及m c c a b ee ta 1 ( 1 9 9 1 ) 也提出了娄似的结论。 山大学博士学位论文 组合拍卖问题及其智能优化算法的研究 随着计算能力的不断增强，组合拍卖越来越得到人们的重视。近年来，有关 组合拍卖的研究很多，包括r o t h k o p fe ta 1 ( 1 9 9 8 ) ，f u j i s h i m ae ta 1 ( 1 9 9 9 ) ， s a n d h o l m ( 2 0 0 0 ) ，x i ae ta 1 ( 2 0 0 4 ) 都对组合出价做过相关的研究眦1 4 ，1 5 ，1 6 ”。v r i e s 和v o h r a 在2 0 0 0 年对组合拍卖作了一个详细的调查，在他们的文献中提供了很 多组合拍卖的例子，包括广播频率权的分配( f c c ，1 9 9 4 ) ，铁路路段分配( b r e w e r ， 1 9 9 9 ) 等。需要注意的是，他们设计的最优化程序均建立在数学规划公式的基础 卜，拍卖方在组合拍卖中希望的最佳分配方案，即组合拍卖问题，属于 n p c o m p l e t e 问题。 从当前组合拍卖的应用情况可以看到，对于物品之间有互补影响的市场，组 合拍卖是一种非常可行的拍卖方式。它允许竞标者对感兴趣的组合提交投标，使 得拍卖者能够根据竞标者的投标，将标的划分为合理的组合，按照最大化拍卖人 收入的目标分配这些标的组。由于分配的结果是基于投标人的组合投标，所以基 本满足投标人的需要，对于投标人没有动机去转售( 或再需求) ，也就降低了产生 套利的可能。 对于组合拍卖应用的多个市场，它们的共同特点就是效用( 或成本) 协同增效 和标的之间的互补替代性。所谓互补性是指投标人对物晶组合的评价比分开拍 卖的评价总和更大，而替代性则反之。正是这种协同增效，使得标的问的互补性 和替代性成为组合拍卖中的重要因素。由于这种互补与替代性，使得组合拍卖在 投标策略、标的分配等方面都与一般拍卖有很大的不同，甚至复杂得多。 组合拍卖总体来说是一个计算上很复杂的一种拍卖形式。组合拍卖因为其复 杂性而不常被使用。对于组合拍卖的研究，研究者通常作如下努力问题：忽略某 些问题，让投标人去推测他们将来是否将赢得项目：对于物品增加一个转售市场， 希望可以帮助产生经济上可取的组合；在多轮并行拍卖中出售多个项目，希望前 轮的反馈信息可以提供投标人在下一轮的竞标策略；通过规定一个、两个或多 个拍卖人可以组队的机制，使他们的投标结合起来，希望他们能找到最佳投标途 径。 p 山大学博士学位论文 组合拍卖问题及其智能优化算法的研究 2 2 组合拍卖机制 研究一个拍卖机制需要考虑众多的因素，例如竞标者的风险偏好，拍卖物品 的属性，竞标者是否是对称的等等因素。这些因素的研究与分析是一项复杂的工 作。由于本文主要研究的是组台拍卖问题，因此这里主要对组合拍卖机制的通用 模型，基本流程做介绍。在下面章节中，主要介绍的单数量组合拍卖，即多个不 同物品的组合拍卖，或者说是多种物品且每种物品只有单个数量的组合拍卖。目 前对于该类组合拍卖的研究很多，也比较成熟。多种物品多数量的组合拍卖的模 型与流程可以参考前者，并加入数量限制，本文就不再重复介绍。 2 2 1 前提假设 目前研究拍卖的最基本的假设就是独立私人价值假设，包括： 所有投标人和拍卖人都是风险中立的 所有投标人是对称的，其估价服从同一概率分布； 拍卖品具有独立的私人价值。印，每个投标人仅凭其所掌握的私人信 息就可以精确地对拍卖品估价，即使知道了所有其他人的估价信息也 不会改变自己的估价； 最终支付取决于投标； 投标人之间是非合作博弈： 拍卖人不存在交易费用。 上述条件构成的模型称为基准模型，又称为私人价值模型。对拍卖机制的效 率分析一般在该框架内进行。该模型是个极限情况，与其相对应是公共价值模型 和两者之间的关联价值模型 2 ，2 2 模型设计 本文对组合拍卖一般模型描述如下： 拍卖方山拍卖代理彳。表示，拍卖过程由爿( ，控制，由爿。宣布拍卖的丌始、 9 。f 山大学博士学位论文组合拍卖问题及其智能优化算法的研究 结束以及分配方案。 共有n 个竟标者参与拍卖，由竞标代理a i ，a 2 ，a 。表示。 o 设，为拍卖物品集合，共有m 个物品，= f 扎i 2 。 设s 为所有拍卖物品组合的集合，s = i s l ，s 2 ，s 3 ， 。竞标代理对s 中的 s ，进行竞投，s i 代表某种物品组合，包含，中的任意一个或多个物品。 每个竞标代理提出标b 1 ，b ，= ( s i ，p ，) 。p ，表示对物品组合研的标价，p ，非 负且在拍卖过程单调递增。 设x 为当前一轮竞投的所有分配方案集合，在每轮竞投结束后，需要找 出使得拍卖方收益最大的分配方案勘。 2 2 3 流程描述 这里介绍的组合拍卖机制是基于连续、升价、开放式的拍卖模式0 9 , 2 0 】。拍卖 以轮次计算，具体步骤如下： l 、出价。在每一轮开始时，拍卖代理将宣布拍卖的物品以及当前物品组合的底 价，每种组合的最初底价可以设为0 。在以后的轮次中，拍卖代理将根据每 轮出价和分配的情况依据一定的规则更新各组合的底价。在拍卖前，拍卖代 理还可以增加一些限制，例如加价的最小幅度等。 2 、竞价。在每一轮拍卖中，竞标代理可以提交对单个物品或物品组合的竞价。 3 、分配。在每轮拍卖结束对，拍卖代理根据竞价情况，以一定的算法或规则确 定本轮的物品分配方案。拍卖代理不得强行拆分竞标代理提出的物品组合， 只能根据现有竞投的物品组合进行分配。 4 、结束。当满足以下其中一个条件则表明拍卖已经结束，这时拍卖代理宣布最 终的分配方案，并按竞标代理提出的标价把物品分配给相应竞标者。结束条件具 体包括： 条件一：拍卖轮次已经达到一定的次数 条件二二：在某一轮拍卖结束后，所有竞标者都对当前任务分配方案表示满意 条件三：在持续两轮的竞价中，所有竞标代理的出价都没有变化 在上述条件中，条件一是为了防止拍卖无休止进行而加入的强制终止条件， 0 中山大学博士学位论文组合拍卖问题及其智能优化算法的研究 在实际应用中，也可以以时问限制作为终止条件。当出现条件二的情形，因为所 竞标者都已经对当前的分配方案表示满意，因此所有竞标者不会在下一轮拍卖中 改变自己的物品组合与竞价。既然当前分配方案使得所有竟标者满意，也保持了 拍卖方的最大收益，因此可以结束拍卖。条件二相当于由竞标者达成共识来结束 拍卖。当出现条件三的情形，如果在第，轮和t + l 轮种所有竞标代理都提交了不 变的竞价，则第f + l 轮的底价是根据竞标者在第t 轮的竞价情况以及之前的分配 情况来确定的，在第f + 1 轮中，由于竞标代理提出的竞价没有发生变化，因此拍 卖代理计算的分配方案以及在第什2 轮中出价也不会发生变化，这使得拍卖结果 进入不变状态，因此可以结束拍卖。 2 3 组合拍卖中的组合标集 2 3 1 组合标集的设计 组合拍卖允许竟标者对物品组合进行竞投，使得竞标者自由灵活地表达自己 对物晶的偏好。但是简单的组合拍卖不一定能够为竞标者提供足够的自由度。在 组合拍卖中可能会遇到以下几种窘境： 1 ) 我想得到物品a 或口，但我不想两者都得到。在物品a 与b 同类不同质 条件下常遇到这种情形。例如两辆二手车一起参与拍卖，一辆5 人座， 价格便宜且省油，一辆8 人座，价格贵些但可以用来装货，两辆都符合 买家的心意，因此买家提出两个标但只希望其中一个中选。又例如在 次电脑设备招标中，厂商可以提供两种牌子的显示器，一种是国外的牌 予，价格较贵，一种是国产的牌子，价格便宜，为此厂商提出两个标， 不同牌子不同价钱，但只希望其中一个标中选。 2 ) 我愿意付出高价钱分别得到物品一或b ，对于同时得到a 和b ，我只愿 意付出低于爿+ b 的价钱。这种情形袁明，对于竞标者来说，物品和b 的价值是不能累加的，甚至a 与b 的物品组合会导致价值降低，但竞标 者仍然愿意同时得到a 与曰。例如竞标者对物品a 竞价1 0 ，物品曰竞价 2 0 ，但对物品组合爿+ 口竞价2 5 ，为此竞标者希望= ：个标，要不前两者中 a 芦】冉卜学位论文组合拍卖问题及其智能优化算法的研究 其一，要不只中后者。 上述介绍的情形不仅存在于组合拍卖，在其他拍卖中也可能遇到。其关键在 p 尽管组合拍卖为竞标者提供了物品之间的组合，但没有提供标与标之间组合。 竞标者每次只能提出一个标，这大大削弱了组合拍卖的灵活性。为此，p a r k s 和 s a n d h o l m 分别做了相关的研究 2 0 , 2 1 】，其中p a r k s 提出加入x o r 连接符来表达标 与标之间的互斥关系，而s a n d h o l m 提出o r 与x o r 两种连接符，使得标与标之 i h j 的关系表达更具弹性。在这些研究基础上，本章将两种标连接符统一表述为组 合标集。 组合标集，是指在每轮拍卖中，每个竞标提出的不是一个标，而是一个标集 。，爪台中的每个标都可以对一个物品组合进行标价，集合分为o r 标集与x o r 标集两种： o r 标集：集合内任意一个或多个标都可以中选 o x o r 标集；集合内至多只允许一个标中选 对于前面介绍的第一种情形，假设有拍卖物品a 、b ，若有标b l = 【0 ) ，1 0 ， b 2 = ( 回，2 0 】，两标属于同一竞标者，当竞标者只希望b i 或b 2 其中一个中选，可 以提出x o r 标集 【) ，1 0 】x o r 【( b ) ，z 0 ) ，当竞标者希望两标都可以中选，可以 提出o r 标集“口) ，1 0 】o r 【( 功，2 0 1 ) 。 对于第二种情形，类似的有标b - = 【似) ，1 0 1 ，b 2 = ( b ) ，2 0 1 ，b 3 _ 旧+ 国，3 0 】， 二个标属于同一竞标者，由于b 3 在物品上包含了b i 、b 2 ，因此竞标者可以提出 x o r 标集 【叫) ，1 0 】x o r ( 印，2 0 】x o r 口，b ) ，2 5 1 2 3 2 组合标集的扩展 根据x o r 标集的特性，竞标者可以通过x o r 标集来表达所有物品组合，例 “”有物品a b c d ，那么所有的物品组合为： “f _ ) ，1 0 】x o r 【( b ) ，2 0 】x o r 【( c ) ，3 0 】x o r 【( d ) 4 0 】x o r 【( 爿，b ) ，3 0 x o r 【( 爿 ( ) ，4 0 jx o r 【a ，d ) ，5 0 】x o r ( b ，c ) ，5 0 x o r 【( b ，| d ) ，6 0 】x o r 【( c ，d ) ，7 0 x o r 附f ，b ，q ，6 0 】x o r 似，b ，d ) ，7 0 x o r 【u ，e d ) ，8 0 x o r ( b ，c ，d ) ，9 0 】x o r ( “8 ，c ，d ) ，1 0 0 i 山大学博士学位论文组合拍卖问题及其智能优化算法的研究 上述x o r 标集是一个所有可能标的全集，任何竞标者提出的x o r 标集会是 上述x o r 标集的其中一个子集( 标价部分可能会不同) 。 在实际拍卖中，o r 标集往往可以转换为x o r 标集，例如： 0 ) ，1 0 o r ( 动，2 0 】2 一)【0 ) ，1 0 】x o r (