2003 IEEE/WIC International Conference on Intelligent Agent Technology (IAT'03)
On Heuristics for Solving Winner Determination Problem in Combinatorial Auctions
Halifax, Canada
October 13-October 17
ISBN: 0-7695-1931-8
The winner determiniation 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 anytime performance of the resulting heuristic search procedures.
Citation:
Masaya Mito, Satoshi Fujita, "On Heuristics for Solving Winner Determination Problem in Combinatorial Auctions," iat, pp.25, 2003 IEEE/WIC International Conference on Intelligent Agent Technology (IAT'03), 2003