On Heuristics for Solving Winner Determination Problem in Combinatorial Auctions

The winner determination problem (WDP) in combinatorial auctions is the problem of, given a finite set of combinatorial bids B, finding a feasible subset B of B with a maximum revenue. WDP is known to be equivalent to the maximum weight set packing problem, and hard to approximate by polynomial time algorithms. This paper proposes three heuristic bid ordering schemes for solving WDP; the first two schemes take into account the number of goods shared by conflicting bids, and the third one is based on a recursive application of such local heuristic functions. We conducted several experiments to evaluate the goodness of the proposed schemes. The result of experiments implies that the first two schemes are particularly effective to improve the performance of the resulting heuristic search procedures. More concretely, they are scalable compared with the conventional linear programming (LP) relaxation based schemes, and could quickly provide an optimum solution under optimization schemes such as the branch-and-bound method. In addition, they exhibit a good anytime performance competitive to the LP-based schemes, although it is sensitive to configurable parameters controlling the strength of contributions of bid conflicts to the resultant bid ordering schemes.