Algorithm for optimal winner determination in combinatorial auctions. (English) Zbl 0984.68039

Summary: Combinatorial auctions, that is, auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auction mechanisms in multi-item auctions where the agents’ valuations of the items are not additive. However, determining the winners so as to maximize revenue is NP-complete. First, we analyze existing approaches for tackling this problem: exhaustive enumeration, dynamic programming, and restricting the allowable combinations. Second, we study the possibility of approximate winner determination, proving inapproximability in the general case, and discussing approximation algorithms for special cases. We then present our search algorithm for optimal winner determination. Experiments are shown on several bid distributions which we introduce. The algorithm allows combinatorial auctions to scale up to significantly larger numbers of items and bids than prior approaches to optimal winner determination by capitalizing on the fact that the space of bids is sparsely populated in practice. The algorithm does this by provably sufficient selective generation of children in the search tree, by using a secondary search for fast child generation, by using heuristics that are admissible and optimized for speed, and by preprocessing the search space in four ways. Incremental winner determination and quote computation techniques are presented. We show that basic combinatorial auctions only allow bidders to express complementarity of items. We then introduce two fully expressive bidding languages, called XOR-bids and OR-of-XORs, with which bidders can express general preferences (both complementarity and substitutability). The latter language is more concise. We show how these languages enable the use of the Vickrey–Clarke–Groves mechanism to construct a combinatorial auction where each bidder’s dominant strategy is to bid truthfully. Finally, we extend our search algorithm and preprocessors to handle these languages as well as arbitrary XOR-constraints between bids.


68P10 Searching and sorting
68W05 Nonnumerical algorithms
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)


Full Text: DOI


[1] Andersson, M. R.; Sandholm, T., Leveled commitment contracting among myopic individually rational agents, (Proc. Third International Conference on Multi-Agent Systems (ICMAS), Paris, France (1998)), 26-33
[2] Andersson, M. R.; Sandholm, T., Time-quality tradeoffs in reallocative negotiation with combinatorial contract types, (Proc. AAAI-99, Orlando, FL (1999)), 3-10
[3] Andersson, M.; Sandholm, T., Contract type sequencing for reallocative negotiation, (Proc. Twentieth International Conference on Distributed Computing Systems, Taipei, Taiwan (2000))
[4] Andersson, M. R.; Sandholm, T., Leveled commitment contracts with myopic and strategic agents, J. Economic Dynamics and Control (Special Issue on Agent-Based Computational Economics.), 25, 615-640 (2001), early version appeared in: Proc. AAAI-98, Madison, WI, 1998, pp. 38-45 · Zbl 0960.91047
[5] Boutilier, C.; Goldszmidt, M.; Sabata, B., Sequential auctions for the allocation of resources with complementarities, (Proc. IJCAI-99, Stockholm, Sweden (1999)), 527-534
[6] Chandra, B.; Halldórsson, M. M., Greedy local search and weighted set packing approximation, (Proc. 10th Annual SIAM-ACM Symposium on Discrete Algorithms (SODA), Baltimore, MD (1999)), 169-176 · Zbl 0961.90093
[7] Clarke, E. H., Multipart pricing of public goods, Public Choice, 11, 17-33 (1971)
[8] Comtet, L., Advanced Combinatorics (1974), D. Reidel: D. Reidel Dordrecht
[9] Conen, W.; Sandholm, T., Minimal preference elicitation in combinatorial auctions, (Proc. IJCAI-2001 Workshop on Economic Agents, Models, and Mechanisms, Seattle, WA (2001)), 71-80
[10] Conen, W.; Sandholm, T., Preference elicitation in combinatorial auctions: Extended abstract, (Proc. ACM Conference on Electronic Commerce (ACM-EC), Tampa, FL (2001))
[11] Cook, W. J.; Cunningham, W. H.; Pulleyblank, W. R.; Schrijver, A., Combinatorial Optimization (1998), Wiley: Wiley New York · Zbl 0909.90227
[12] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press: MIT Press Cambridge, MA · Zbl 1158.68538
[13] de Vries, S.; Vohra, R., Combinatorial auctions: A survey. Draft (August 28th, 2000)
[14] DeMartini, C.; Kwasnica, A.; Ledyard, J.; Porter, D., A new and improved design for multi-object iterative auctions, Technical Report 1054 (1998), California Institute of Technology, Social Science
[15] 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
[16] Garfinkel, R.; Nemhauser, G., The set partitioning problem: Set covering with equality constraints, Oper. Res., 17, 5, 848-856 (1969) · Zbl 0184.23101
[17] Groves, T., Incentives in teams, Econometrica, 41, 617-631 (1973) · Zbl 0311.90002
[18] Halldórsson, M. M., Approximations of independent sets in graphs, (Jansen, K.; Rolim, J., The First International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Aalborg, Denmark. The First International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Aalborg, Denmark, Lecture Notes in Computer Science, 1444 (1998), Springer: Springer Berlin), 1-14 · Zbl 0903.05044
[19] Halldórsson, M. M., Approximations of weighted independent set and hereditary subset problems, (Computing and Combinatorics, J. Graph Algorithms Appl. 4 (1) (2000) 1-16; early versions appeared in: Computing and Combinatorics, Proceedings of the 5th Annual International Conference (COCOON), Tokyo, Japan 1999; and in. Computing and Combinatorics, J. Graph Algorithms Appl. 4 (1) (2000) 1-16; early versions appeared in: Computing and Combinatorics, Proceedings of the 5th Annual International Conference (COCOON), Tokyo, Japan 1999; and in, Lecture Notes in Computer Science, 1627 (1999), Springer: Springer Berlin), 261-270 · Zbl 0945.68146
[20] Halldórsson, M. M.; Kratochvı́l, J.; Telle, J. A., Independent sets with domination constraints, Discrete Appl. Math. (1998), also appeared in: Proceedings of the 25th International Conference on Automata, Languages, and Programming (ICALP), Aalborg, Denmark, Springer Lecture Notes in Computer Science, Vol. 1443, July 1998
[21] Halldórsson, M. M.; Lau, H. C., Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and 3-coloring, J. Graph Algorithm Appl., 1, 3, 1-13 (1997) · Zbl 0891.05061
[22] Håstad, J., Clique is hard to approximate within \(n^{1−ε}\), Acta Mathematica, 182, 105-142 (1999) · Zbl 0989.68060
[23] Hausch, D. B., Multi-object auctions: Sequential vs. simultaneous sales, Management Sci., 32, 1599-1610 (1986) · Zbl 0607.90021
[24] Hochbaum, D. S., Efficient bounds for the stable set, vertex cover, and set packing problems, Discrete Appl. Math., 6, 243-254 (1983) · Zbl 0523.05055
[25] Hochbaum, D. S., Approximation Algorithms for NP-hard Problems (1997), PWS Publishing Company: PWS Publishing Company Boston, MA
[26] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041
[27] Kelly, F.; Steinberg, R., A combinatorial auction with multiple winners for universal services, Management Sci., 46, 4, 586-596 (2000) · Zbl 1231.91119
[28] Korf, R. E., Depth-first iterative-deepening: An optimal admissible tree search, Artificial Intelligence, 27, 1, 97-109 (1985) · Zbl 0573.68030
[29] Larson, K.; Sandholm, T., Computationally limited agents in auctions, (Proc. AGENTS-01 Workshop of Agents for B2B, Montreal, Canada (2001)), 27-34
[30] Larson, K.; Sandholm, T., Costly valuation computation in auctions: Deliberation equilibrium, (Proc. Theoretical Aspects of Reasoning about Knowledge (TARK), Siena, Italy (2001)), 169-182
[31] Ledyard, J., Personal communications at the National Science Foundation Workshop on Research Priorities in Electronic Commerce, Austin, TX (1998)
[32] Lehmann, D.; O’Callaghan, L. I.; Shoham, Y., Truth revelation in rapid, approximately efficient combinatorial auctions, (Proc. ACM Conference on Electronic Commerce (ACM-EC), Denver, CO (1999)), 96-102
[33] Loukakis, E.; Tsouros, C., An algorithm for the maximum internally stable set in a weighted graph, Internat. J. Comput. Math., 13, 117-129 (1983) · Zbl 0502.68013
[34] Preston McAfee, R.; McMillan, J., Analyzing the airwaves auction, J. Economic Perspectives, 10, 1, 159-175 (1996)
[35] McMillan, J., Selling spectrum rights, J. Economic Perspectives, 8, 3, 145-162 (1994)
[36] Milgrom, P., Putting auction theory to work: The simultaneous ascending auction, Technical Report (1997), Stanford University, Department of Economics, Revised 4/21/1999
[37] Nisan, N., Bidding and allocation in combinatorial auctions, (Proc. ACM Conference on Electronic Commerce (ACM-EC), Minneapolis, MN (2000)), 1-12
[38] Papadimitriou, C. H., Computational Complexity (1995), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0557.68033
[39] Pardalos, P. M.; Desai, N., An algorithm for finding a maximum weighted independent set in an arbitrary graph, Internat. J. Comput. Math., 38, 163-175 (1991) · Zbl 0723.68085
[40] Rassenti, S. J.; Smith, V. L.; Bulfin, R. L., A combinatorial auction mechanism for airport time slot allocation, Bell J. Econom., 13, 402-417 (1982)
[41] Reinefeld, A.; Schnecke, V., AIDA∗—Asynchronous parallel IDA∗, (Proc. 10th Canadian Conf. on AI, Banff, Alberta (1994)), 295-302
[42] Rothkopf, M. H.; Pekeč, A.; Harstad, R. M., Computationally manageable combinatorial auctions, Management Sci., 44, 8, 1131-1147 (1998) · Zbl 0989.90094
[43] Sandholm, T., A strategy for decreasing the total transportation costs among area-distributed transportation centers, (Nordic Operations Analysis in Cooperation (NOAS): OR in Business, Turku School of Economics, Finland (1991))
[44] Sandholm, T., An implementation of the contract net protocol based on marginal cost calculations, (Proc. AAAI-93, Washington, DC (1993)), 256-262
[45] Sandholm, T., Negotiation among self-interested computationally limited agents, Ph.D. Thesis (1996), University of Massachusetts: University of Massachusetts Amherst, MA, Available at http://www.cs.cmu.edu/ sandholm/dissertation.ps
[46] Sandholm, T., Contract types for satisficing task allocation, I: Theoretical results, (Proc. AAAI Spring Symposium Series: Satisficing Models, Stanford University, CA (1998)), 68-75
[47] Sandholm, T., eMediator: A next generation electronic commerce server, (Proc. Fourth International Conference on Autonomous Agents (AGENTS), Barcelona, Spain (2000)), 73-96, early version appeared in: Proc. AAAI-99 Workshop on AI in Electronic Commerce, Orlando, FL, July 1999, pp. 46-55, and as: Washington University, St. Louis, Dept. of Computer Science Technical Report WU-CS-99-02, January 1999
[48] 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
[49] Sandholm, T.; Larson, K. S.; Andersson, M. R.; Shehory, O.; Tohmé, F., Coalition structure generation with worst case guarantees, Artificial Intelligence, 111, 1-2, 209-238 (1999), early version appeared in: Proc. AAAI-98, Madison, WI, 1998, pp. 46-53 · Zbl 0997.91004
[50] Sandholm, T.; Lesser, V. R., Issues in automated negotiation and electronic commerce: Extending the contract net framework, (Proc. First International Conference on Multi-Agent Systems (ICMAS), San Francisco, CA (1995)), 328-335, Reprinted in: M.N. Huhns and M.P. Singh (Eds.), Readings in Agents, Morgan Kaufmann, San Mateo, CA, 1997, pp. 66-73
[51] Sandholm, T.; Lesser, V. R., Leveled commitment contracts and strategic breach, Games and Economic Behavior (Special issue on AI and Economics), 35, 212-270 (2001), Short early version appeared as ‘Advantages of a Leveled Commitment Contracting Protocol’ in: Proc. AAAI-96, Portland, OR, 1996, pp. 126-133. Extended version: University of Massachusetts at Amherst, Computer Science Department, Technical Report 95-72 · Zbl 1050.91034
[52] Sandholm, T.; Sikka, S.; Norden, S., Algorithms for optimizing leveled commitment contracts, (Proc. IJCAI-99, Stockholm, Sweden (1999)), 535-540, Extended version: Washington University, Department of Computer Science, Technical Report WUCS-99-04
[53] Sandholm, T.; Suri, S., Improved algorithms for optimal winner determination in combinatorial auctions and generalizations, (Proc. AAAI-00, Austin, TX (2000)), 90-97
[54] Sandholm, T.; Suri, S., Market clearability, (Proc. IJCAI-01, Seattle, WA (2001)), 1145-1151
[55] Sandholm, T.; Suri, S., Side constraints and non-price attributes in markets, (Proc. IJCAI-2001 Workshop on Distributed Constraint Reasoning, Seattle, WA (2001)), 55-61
[56] Sandholm, T.; Suri, S.; Gilpin, A.; Levine, D., CABOB: A fast optimal algorithm for combinatorial auctions, (Proc. IJCAI-01, Seattle, WA (2001)), 1102-1108
[57] Sandholm, T.; Suri, S.; Gilpin, A.; Levine, D., Winner determination in combinatorial auction generalizations, (Proc. AGENTS-01 Workshop on Agent-Based Approaches to B2B, Montreal, Canada (2001)), 35-41
[58] Vickrey, W., Counterspeculation, auctions, and competitive sealed tenders, J. Finance, 16, 8-37 (1961)
[59] Federal Communications Commission, Wireless telecommunications action WT 98-35 (September 1998)
[60] Wolsey, L. A., Integer Programming (1998), Wiley: Wiley New York · Zbl 0299.90012
[61] Wurman, P. R.; Wellman, M. P.; Walsh, W. E., The Michigan Internet AuctionBot: A configurable auction server for human and software agents, (Proc. Second International Conference on Autonomous Agents (AGENTS), Minneapolis/St. Paul, MN (1998)), 301-308
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.