基于有穷损害优先法求解组合拍卖竞胜标问题研究

Solution to the Winner Determination Problem in Combinatorial Auctions By Finite Injury Priority Method

迄今为止,组合拍卖竞胜标问题并不存在一个多项式时间复杂度的算法,其计算复杂性与拍卖效率之间的矛盾一直是影响组合拍卖广泛应用的主要障碍。它是一个NP难问题,也是组合拍卖机制设计中的难题之一。而有穷损害优先方法是纯粹递归论中的一个十分重要的现代方法,特别对NP难问题求解算法的设计,对研究依复杂度决定的偏序结构的构造是一个很基本的有用工具。因此,本文提出根据组合拍卖的内在特性,将各不同的拍卖商品按照拍卖机制的要求,并结合其自身的协同价值等因素,设定一个优先序,然后采用有穷损害优先法有效有序地解决。

So far, the winner determination problem in combinatorial auctions has not had a polynomial time complexity algorithm. It is an NP-hard problem. The finite injury priority method is one of the very important modern methods in recursion theory. In particular, it is a very useful tool or designing the NP-hard problem solving algorithm according to the complexity of the of the partial order structure. So, an approximate algorithm is proposed for solving the well-known NP hard problem-the winner determination problem in combinatorial auctions.