BOB: Improved winner determination in combinatorial auctions and generalizations. (English) Zbl 1082.68813

Summary: Combinatorial auctions can be used to reach efficient resource and task allocations in multiagent systems where the items are complementary or substitutable. Determining the winners is NP-complete and inapproximable, but it was recently shown that optimal search algorithms do very well on average. This paper presents a more sophisticated search algorithm for optimal (and anytime) winner determination, including structural improvements that reduce search tree size, faster data structures, and optimizations at search nodes based on driving toward, identifying and solving tractable special cases. We also uncover a more general tractable special case, and design algorithms for solving it as well as for solving known tractable special cases substantially faster. We generalize combinatorial auctions to multiple units of each item, to reserve prices on singletons as well as combinations, and to combinatorial exchanges. All of these generalizations support both complementarity and substitutability of the items. Finally, we present algorithms for determining the winners in these generalizations.


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
91B26 Auctions, bargaining, bidding and selling, and other market models
91A46 Combinatorial games


Full Text: DOI


[1] Andersson, A.; Tenhunen, M.; Ygge, F., Integer programming for combinatorial auction winner determination, (Proc. Fourth International Conference on Multi-Agent Systems (ICMAS), Boston, MA (2000)), 39-46
[2] Boutilier, C.; Goldszmidt, M.; Sabata, B., Sequential auctions for the allocation of resources with complementarities, (Proc. IJCAI-99, Stockholm, Sweden (1999)), 527-534
[4] Edmonds, J., Maximum matching and a polyhedron with 0, 1 vertices, J. Res. Nat. Bur. Standards B, 69, 125-130 (1965) · Zbl 0141.21802
[5] Eschen, E. M.; Spinrad, J., An \(O(n^2)\) algorithm for circular-arc graph recognition, (Proc. Annual SIAM-ACM Symposium on Discrete Algorithms (SODA) (1993)), 128-137 · Zbl 0801.68128
[6] Fujishima, Y.; Leyton-Brown, K.; Shoham, Y., Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches, (Proc. IJCAI-99, Stockholm, Sweden (1999)), 548-553
[7] Gonen, R.; Lehmann, D., Optimal solutions for multi-unit combinatorial auctions: Branch and bound heuristics, (Proc. ACM Conference on Electronic Commerce (ACM-EC), Minneapolis, MN (2000)), 13-20
[8] Håstad, J., Clique is hard to approximate within \(n^{1−ε}\), Acta Math., 182, 105-142 (1999) · Zbl 0989.68060
[9] Hoos, H.; Boutilier, C., Solving combinatorial auctions using stochastic local search, (Proc. AAAI-00, Austin, TX (2000)), 22-29
[10] Kelly, F.; Steinberg, R., A combinatorial auction with multiple winners for universal services, Management Sci., 46, 4, 586-596 (2000) · Zbl 1231.91119
[11] Korte, N.; Mohring, R. H., An incremental linear-time algorithm for recognizing interval graphs, SIAM J. Comput., 18, 1, 68-81 (1989) · Zbl 0678.68043
[12] Lehmann, D.; O’Callaghan, L. I.; Shoham, Y., Truth revelation in rapid, approximately efficient combinatorial auctions, J. ACM (2003), To appear. Early version appeared in ACMEC-99
[13] Leyton-Brown, K.; Tennenholtz, M.; Shoham, Y., An algorithm for multi-unit combinatorial auctions, (Proc. AAAI-00, Austin, TX (2000))
[14] McAfee, R. P.; McMillan, J., Analyzing the airwaves auction, J. Economic Perspectives, 10, 1, 159-175 (1996)
[15] McMillan, J., Selling spectrum rights, J. Economic Perspectives, 8, 3, 145-162 (1994)
[16] Myerson, R.; Satterthwaite, M., Efficient mechanisms for bilateral exchange, J. Economic Theory, 28, 265-281 (1983) · Zbl 0523.90099
[17] Nisan, N., Bidding and allocation in combinatorial auctions, (Proc. ACM Conference on Electronic Commerce (ACM-EC), Minneapolis, MN (2000)), 1-12
[18] Rassenti, S. J.; Smith, V. L.; Bulfin, R. L., A combinatorial auction mechanism for airport time slot allocation, Bell J. Economics, 13, 402-417 (1982)
[19] Rothkopf, M. H.; Pekeč, A.; Harstad, R. M., Computationally manageable combinatorial auctions, Management Sci., 44, 8, 1131-1147 (1998) · Zbl 0989.90094
[20] Russell, S.; Norvig, P., Artificial Intelligence: A Modern Approach (1995), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 0835.68093
[21] Sandholm, T., An implementation of the contract net protocol based on marginal cost calculations, (Proc. AAAI-93, Washington, DC (1993)), 256-262
[22] Sandholm, T., Issues in computational Vickrey auctions, Internat. J. Electronic Commerce, 4, 3, 107-129 (2000), Special Issue on Applying Intelligent Agents for Electronic Commerce. A short, early version appeared at the Second International Conference on Multi-Agent Systems (ICMAS), 1996, pp. 299-306
[23] Sandholm, T., Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, 135, 1-54 (2002), First appeared as an invited talk at the First International Conference on Information and Computation Economies, Charleston, SC, October 25-28, 1998. Extended version appeared as Washington Univ., Dept. of Computer Science, Technical Report WUCS-99-01, January 28th, 1999. Conference version appeared at the International Joint Conference on Artificial Intelligence (IJCAI), Stockholm, Sweden, 1999, pp. 542-547 · Zbl 0984.68039
[24] Sandholm, T., eMediator: A next generation electronic commerce server, Computational Intelligence, 18, 4, 656-676 (2002), Early versions appeared in the Conference on Autonomous Agents (AGENTS-00), 2000, pp. 73-96; AAAI-99 Workshop on AI in Electronic Commerce, Orlando, FL, July 1999, pp. 46-55; and as a Washington University, St. Louis, Dept. of Computer Science Technical Report WU-CS-99-02, January 1999
[25] Sandholm, T.; Suri, S.; Gilpin, A.; Levine, D., CABOB: A fast optimal algorithm for combinatorial auctions, (Proc. IJCAI-01, Seattle, WA (2001)), 1102-1108
[26] Sandholm, T.; Suri, S.; Gilpin, A.; Levine, D., Winner determination in combinatorial auction generalizations, (International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), Bologna, Italy (2002)), 69-76, Early version appeared at the AGENTS-01 Workshop on Agent-Based Approaches to B2B, Montreal, Canada, May 2001, pp. 35-41
[27] Tennenholtz, M., Some tractable combinatorial auctions, (Proc. AAAI-00, Austin, TX (2000)) · Zbl 0999.68003
[28] Weiss, M. A., Data Structures and Algorithm Analysis in C++ (1999), Addison-Wesley: Addison-Wesley Reading, MA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.