组合拍卖赢者决定问题及其应用研究

作     者：秦琴 

作者单位：湖南师范大学 

学位级别：硕士

导师姓名：唐邵玲

授予年度：2010年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：组合拍卖 赢者决定问题 NP难度 拍卖实验 

摘      要：随着电子商务的发展和拍卖多单元物品的实际需要,许多传统的拍卖理论和假设已经不再适合新的拍卖经济环境。人们开始设计并使用一些适合复杂性质物品的拍卖方式。实验表明在多物品拍卖中,当物品具有很强的协同作用(互补性或替代性)时,同时叫价拍卖优于序贯拍卖,而组合拍卖优于前两者。因此多物品拍卖中的组合拍卖在二十世纪九十年代后成为拍卖领域的研究热点。但是组合拍卖设计在应用中受到了很大的限制,原因是当销售商品数量和种类增加时,拍卖很快就变得非常复杂,确定赢者成为了一个难于计算的问题。赢者决定问题的复杂性不仅令拍卖方陷入决定的困境,还使得竞价人很难预计自己的投标结果,同时也很难判断拍卖方是否诚实地进行拍卖。因此,赢者决定问题严重地阻碍了组合拍卖理论的应用和发展。 目前,关于赢者决定问题的研究大都是计算机领域的学者对该问题进行算法的改进,而从经济和应用领域研究如何解决赢者决定问题是不多见的。本文通过系统地阐述解决赢者决定问题的理论方法,重点研究这些处理方法在相关领域的应用中的异同。在研究过程中采用理论证明、实验证明、比较分析等研究方法。 首先阐述了序贯拍卖和平行拍卖在实践应用中的缺陷,如分配结果的无效率、赢者诅咒等等,而组合拍卖可以很好地解决这些问题。其次系统地论证正向组合拍卖、逆向组合拍卖和双向组合拍卖赢者决定问题的复杂性,。接下来,文章讨论了组合拍卖赢者决定问题处理方法,并将处理方法分为三大类：赢者决定问题的简化处理(得到易处理的WDP)、赢者决定问题的算法改进和拍卖机制改进。 最后,本文着重研究组合拍卖的主要应用领域——频谱拍卖、电力能源拍卖、飞机停机位拍卖、巴士线路拍卖、货车运输拍卖和采购拍卖,并将这六大应用领域分成三类,分别是：可分物品正向拍卖、不可分物品正向拍卖和不可分物品逆向拍卖。通过拍卖理论分析,设计并实施了系列计算机模拟实验,对实验结果,运用描述性统计及推断统计分析方法比较分析了在三类组合拍卖中不同的赢者决定问题处理方法的差异。对于可分物品正向拍卖赢者决定问题的处理,拍卖方定义优化组合和竞价人提交优化组合两种方法同时使用与选择其中一种方法比较,计算时间并不会显著减少。对于不可分物品的正向拍卖和逆向拍卖赢者决定问题的处理,拍卖方定义优化组合和竞价人提交优化组合两种方法应同时使用较单独使用一种方法,均能显著地减少计算时间,并且逆向拍卖中限制搜索这一方法也会显著减少计算时间。