×

zbMATH — the first resource for mathematics

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.

MSC:
68P10 Searching and sorting
68W05 Nonnumerical algorithms
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
CABOB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersson, M.R.; Sandholm, T., Leveled commitment contracting among myopic individually rational agents, (), 26-33
[2] Andersson, M.R.; Sandholm, T., Time-quality tradeoffs in reallocative negotiation with combinatorial contract types, (), 3-10
[3] Andersson, M.; Sandholm, T., Contract type sequencing for reallocative negotiation, ()
[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, (), 527-534
[6] Chandra, B.; Halldórsson, M.M., Greedy local search and weighted set packing approximation, (), 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 Dordrecht
[9] Conen, W.; Sandholm, T., Minimal preference elicitation in combinatorial auctions, (), 71-80
[10] Conen, W.; Sandholm, T., Preference elicitation in combinatorial auctions: extended abstract, ()
[11] Cook, W.J.; Cunningham, W.H.; Pulleyblank, W.R.; Schrijver, A., Combinatorial optimization, (1998), Wiley New York · Zbl 0909.90227
[12] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., Introduction to algorithms, (1990), 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, (), 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, (), 1-14 · Zbl 0903.05044
[19] Halldórsson, M.M., Approximations of weighted independent set and hereditary subset problems, (), 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 n1−ε, 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 Boston, MA
[26] Karp, R.M., Reducibility among combinatorial problems, (), 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, (), 27-34
[30] Larson, K.; Sandholm, T., Costly valuation computation in auctions: deliberation equilibrium, (), 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, (), 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, (), 1-12
[38] Papadimitriou, C.H., Computational complexity, (1995), 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∗, (), 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, ()
[44] Sandholm, T., An implementation of the contract net protocol based on marginal cost calculations, (), 256-262
[45] Sandholm, T., Negotiation among self-interested computationally limited agents, ph.D. thesis, (1996), 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, (), 68-75
[47] Sandholm, T., Emediator: A next generation electronic commerce server, (), 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, (), 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, (), 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, (), 90-97
[54] Sandholm, T.; Suri, S., Market clearability, (), 1145-1151
[55] Sandholm, T.; Suri, S., Side constraints and non-price attributes in markets, (), 55-61
[56] Sandholm, T.; Suri, S.; Gilpin, A.; Levine, D., CABOB: A fast optimal algorithm for combinatorial auctions, (), 1102-1108
[57] Sandholm, T.; Suri, S.; Gilpin, A.; Levine, D., Winner determination in combinatorial auction generalizations, (), 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 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, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.