论文部分内容阅读
组合拍卖是一种允许竞标者对不同商品组合进行投标的多物品拍卖机制。理论研究和实际应用都证明当商品之间存在互补性或替代性协同价值时,组合拍卖能更好地体现竟标者偏好信息,有效避免“暴露”问题,提高资源配置效率,增加社会效益。作为一种有效的商品定价和资源分配机制,组合拍卖在B2B等多物品交易商业模式中有着独特的优势,在电子商务中有着广阔的应用前景。 然而,网上组合拍卖的实现与推广还面临许多困难和挑战。众多的商品组合形式及其复杂的协同价值结构使得组合拍卖机制设计和投标策略都比其它拍卖复杂的多,其拍卖机制设计中的竞胜标确定问题(Winner Deterninating Problem—WDP)就是一个典型的NP完全问题。而网络运行环境的特点和要求使得拍卖效率与计算复杂性之间的矛盾更加突出,成为阻碍组合拍卖得到广泛应用的瓶颈问题。如何通过合理的机制设计和有效的投标决策支持降低拍卖双方所面临决策问题的复杂性和不确定性是增强组合拍卖可行性和适用性、促进网上组合拍卖的实现与应用亟待解决的重要问题。 针对上述问题,本文以协调计算复杂性与拍卖运行效率之间的内在矛盾为根本出发点,结合网络运行环境的特点和要求,通过拍卖机制及其WDP算法创新设计与投标决策支持方法研究,增强组合拍卖的可行性。 首先,进行网上交互式组合拍卖机制总体设计与分析。本文以机制设计和最优拍卖理论为基础论述了拍卖机制设计基本原则和方法,针对典型的组合拍卖VCG和AkBA各自的优点和缺陷,对信息反馈机制、投标规则等影响拍卖运行效率的关键问题进行创新设计,提出一种新的网上组合拍卖机制APICA(Ascending Price Iterative Combinatorial Auction)。APICA通过投标预处理和简单明了的价格信息反馈机制有效降低计算复杂性,并采用灵活的价格最小增幅确定方法实现对拍卖进程的动态调控,不仅有效地解决了密封投标组合拍卖中竞标者偏好获取难问题,而且避免了iBundel、AkBA等交互式组合拍卖计算复杂性大、信息反馈延迟等弊端,有效缓解了计算复杂性与运行效率间的矛盾。 其次,针对组合拍卖机制APICA中至关重要的竞胜标确定问题进行WDP算法设计与分析。WDP算法性能是影响组合拍卖运行效率的关键因素。本文根据计算复杂性理论分析了WDP问题性质和特点,针对拍卖机制APICA对WDP算法的要求,以现代优化方法及算法设计理论为基础充分论证了权值编码遗传算法的优良性,并根据WDP的特点对微观遗传策略和遗传操作进行适当的改进和重新设计,提出基于权值编码的WDP启发式算法HA-WCGA。与其他WDP算法不同,HA-WCGA采用先进的权值编码机制,具备良好的因果性和遗传性能,并采用熔合交叉和分层次变异遗传操作减少了大量计算。同时,嵌入基于WDP问题的启发式规则增强算法进化能力和求解速度,从而提高了拍卖机制APICA信息反馈速度和运行效率。 然后,根据组合拍卖机制APICA的投标规则,针对投标方所面临的复杂决策问题进行投标策略及投标决策支持方法的研究。首先以现实的网上拍卖投标行为特征为基础构建针对不同类型竞标者的投标策略;然后根据投标决策需求设计投标决策支持Agent(Bidding Support Agent),使其能够在偏好信息不完全条件下帮助竞标者完成商品价值确定、市场信息反馈及投标构造等决策支持功能,有效地降低竞标者决策问题的不确定性和复杂性。 最后,本文通过大量的计算机模拟实验充分论证了组合拍卖机制APICA的运行效率及其WDP算法HA-WCGA的良好性能。以MatLab6.5为编程语言和实验平台,分别设计并完成两个部分共8组模拟实验。第一部分通过APICA与组合拍卖VCG及AkBA的对比实验证实,APICA的拍卖收益明显高于AKBA,在竞标者偏好信息不完全条件下实现与完全信息VCG拍卖相同或非常接近的资源配置效率。进而从拍卖收益、分配效率及竞标者私有信息揭示程度等各方面充分论证了APICA的相对优越性。第二部分基于专业的WDP算法测试数据集CAST生成模拟数据,通过与其它算法的对比实验证明,HA-WCGA能够快速的求出与最优解非常接近的解,其在线、离线性能及进化能力各项指标均优于其他直接编码WDP算法,具有良好的求解质量和求解效率,能适应网上拍卖APICA对WDP算法性能的要求,提高拍卖机制APICA运行效率。 本文通过合理的拍卖机制设计和投标决策支持,有效地协调了组合拍卖运行效率与计算复杂性之间的矛盾,显著地降低了拍卖双方所面临决策问题的复杂性和不确定性,增强组合拍卖的可行性,为网上组合拍卖系统的构建与成功应用提供科学的理论支撑和实践指导。