组合拍卖中竞胜标自动确定问题研究

《组合拍卖中竞胜标自动确定问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、（管理学博士）组合拍卖中竞胜标自动确定问题研究RESEARCHONTHEAUTOMATICWINNERDETERMINATIONPROBLEMINCOMBINATORIALAUCTIONS钱巍2012年5月国内图书分类号：C931.9学校代码：10213国际图书分类号：681.3.06密级：公开管理学博士学位论文组合拍卖中竞胜标自动确定问题研究博士研究生：钱巍导师：冯玉强教授申请学位：管理学博士学科：管理科学与工程所在单位：管理学院答辩日期：2012年5月授予学位单位：哈尔滨工业大学ClassifiedIndex:C931.9U

2、.D.C.:681.3.06DissertationfortheDoctoralDegreeinManagementRESEARCHONTHEAUTOMATICWINNERDETERMINATIONPROBLEMINCOMBINATORIALAUCTIONSCandidate：QianWeiSupervisor：Prof.FengYuqiangAcademicDegreeAppliedfor：DoctorofManagementSpeciality：ManagementScience&EngineeringAffiliation

3、：ManagementScience&EngineeringDateofDefence：May,2012Degree-Conferring-Institution：HarbinInstituteofTechnology摘要摘要组合拍卖，是允许竞标者将多个异质商品组合起来进行捆绑竞价的多物品拍卖方式。由于组合拍卖能给予竞标者极大的自由，能够激发竞标者的参与热情，并能有效地提高资源配置效率，同时增加拍卖收益和社会效益，所以，随着互联网的发展、商品交易的多样化，组合拍卖越来越引起人们的兴趣，成为网上拍卖理论和应用研究的热点问题之一。组

4、合拍卖虽然具有很强的优势，但同时它也提出了大量的问题和挑战。其中，组合拍卖区别于非组合拍卖的一个明显特征就是组合拍卖中的计算复杂性，即组合拍卖的竞胜标确定问题。竞胜标求解已经被证明是一个NPC问题，其计算复杂性与拍卖效率之间的矛盾一直是影响组合拍卖广泛应用的主要障碍。障碍在实际问题中，可以被克服、降低或者避免。虽然克服不可避免的计算困难是很重要的能力，但是，若能利用组合拍卖问题的内在特性，采用合适的方法，依托组合拍卖的优势去降低或者避免其中的计算困难，则是最佳方法，也是有效解决WDP，促进组合拍卖在实际中广泛应用的至关重要问题之

5、一。为了找到解决WDP的有效方法及全面了解WDP的研究现状，本文以“ISIWebofKnowledge”为平台，以“winnerdeterminationproblem”为关键词进行了文献搜索，对找出的删选后的101篇文献的全部摘要和部分正文进行了阅读分析，发现学者们虽然都认识到组合拍卖中实际商品的组合空间要比理论上的小得多，但是在WDP算法研究上，大多都是基于理论上如何战胜WDP的计算复杂性，而不是采用一些技巧，真正从商品实际可能出现的组合空间出发，从组合拍卖设计的优势出发，降低或者避免WDP的计算障碍。这种基于理论的要求，从

6、各种角度包括人为限定投标空间或标的结构，对WDP进行求解的方法，由于和实际问题有不可近似性，所以影响了该理论在实际中的应用。但是这些也证明了，如果能根据组合拍卖实际问题特性，采用合适的方法，是一定可以有效解决WDP的。所以本文以降低或者避免WDP计算复杂性，进行定性与定量相结合的角度出发，以自动求解WDP为目的，定性分析商品的实际特征，采用可拓学中的物元模型，对商品的基本组合特征进行形式化表示，然后以投标语言表达其内在逻辑关系为基础，建立WDP的量化模型。接着，应用量性融合-I-哈尔滨工业大学管理学博士学位论文的NP难问题的可构

7、造技术——有穷损害优先法构造WDP的求解过程，试图为WDP的解决寻找一个新的突破口，提供一个新的求解思路。首先，本文通过可拓理论，对商品及竞标人、投标行为等进行了定性分析和描述，并构建了相应的物元模型，真正表达出商品间的协同价值和竞标人偏好。根据物元模型对商品特性的描述，以具有协同价值的属性为依据，通过关联函数，构造了商品间实际可能发生的组合空间。其次，基于LGB投标语言，将定性分析得到的商品描述的物理模型转换为相应的逻辑模型，便于对WDP的定量分析及应用计算机进行存储与检索，以实现对WDP的自动求解。由于不同的投标结构对WDP

8、算法的复杂度有很大影响，而树形结构已经被证明，在限定标的组合情况下，可以在多项式时间内求得最优解。因此针对上述的商品组合情况，构建其树形拓扑结构图及相应的搜索过程。接着，应用定性与定量方法相结合的有穷损害优先法，研究WDP的不可解度，并构造了其相对可计算性，使其