Abstract
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.
Similar content being viewed by others
References
Chang, M.-S. and F.-H. Wang. (1992). “Efficient Algorithms for the Maximum Weight Clique and Maximum Weight Independent Set Problems on Permutation Graphs.” Information Processing Letters43(6), 293–295.
de Vries, S. and R. Vohra. (2003). “Combinatorial Auctions: A Survey.” To appear in INFORMS Journal on Computing15.
Fujishima, Y., K. Leyton-Brown, and Y. Shoham. (1999). “Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches.” In Proc. IJCAI'99, pp. 548–553.
Halldórsson, M.M. (2000). “Approximation of Weighted Independent Set and Hereditary Subset Problems.” J. of Graphs Algorithms and Applications4(1), 1–16.
Harvey, W.D. and M.L. Ginsberg. (1995). “Limited Discrepancy Search.” In Proc. IJCAI'95,vol. 1, pp. 607–615.
Håstad, J. (1999). “Clique is Hard to Approximate Within <InlineEquation ID="IE1"> <EquationSource Format="MATHTYPE"> <![CDATA[ % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rjpeeu0df9frFj0-yqpe % ea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs0dXdbPYxe9vr0-vr % 0-vqpWqaaeaabiGaciaacaqabeaadaqaaqaaaOqaaiaad6gadaahaa % WcbeqaaiaaigdacqGHsisltuuDJXwAK1uy0HwmaeHbfv3ySLgzG0uy % 0Hgip5wzaGqbciab-v7aYdaaaaa!443E! ]]></EquationSource> <EquationSource Format="TEX"> <![CDATA[$$n {1-\varepsilon } $$]]></EquationSource></InlineEquation>” Acta Mathematica182, 105–142.
Lehmann, D., L. Ita O'Callaghan, and Y. Shoham. (2002). “Truth Revelation in Approximately Efficient Combi-natorial Auctions.” J. of ACM49(5), 577–602.
Leyton-Brown, K., M. Pearson, and Y. Shoham. (2000). “Towards a Universal Test Suite for Combinatorial Auction Algorithms.” In ACM Conf. on Electronic Commerce, pp. 66–76.
Rothkopf, M.H., A. Pekeč, and R.M. Harstad. (1998). “Computationally Manageable Combinatorial Auctions.” Management Science44(8), 1131–1147.
Sakai, S., M. Togasaki, and K. Yamazaki. (2003). “A Note on Greedy Algorithms for Maximum Weighted Inde-pendent Set Problem.” Discrete Applied Mathematics126(2/3), 313–322.
Sakurai, Y., M. Yokoo, and K. Kamei. (2000). “An Efficient Approximate Algorithm for Winner Determination in Combinatorial Auctions.” In ACM Conf. on Electronic Commerce, pp. 30–37.
Sandholm, T. (2002). “Algorithm for Optimal Winner Determination in Combinatorial Auctions.” Artificial Intel-ligence 135(1/2), 1–54.
Sandholm, T. and S. Suri. (2000). “Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations.” In Proc. AAAI, pp. 90–97.
Sandholm, T., S. Suri, A. Gilpin, and D. Levine. (2001). “CABOB: A Fast Optimal Algorithm for Combinatorial Auctions.” In Proc. IJCAI'01, pp. 1102–1108.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mito, M., Fujita, S. On Heuristics for Solving Winner Determination Problem in Combinatorial Auctions. Journal of Heuristics 10, 507–523 (2004). https://doi.org/10.1023/B:HEUR.0000045322.51784.2a
Issue Date:
DOI: https://doi.org/10.1023/B:HEUR.0000045322.51784.2a