article

Algorithm for optimal winner determination in combinatorial auctions

Author:

Tuomas SandholmAuthors Info & Claims

Artificial Intelligence, Volume 135, Issue 1-2

Pages 1 - 54

https://doi.org/10.1016/S0004-3702(01)00159-X

Published: 01 February 2002 Publication History

Abstract

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.

References

[1]

M.R. Andersson, T. Sandholm, Leveled commitment contracting among myopic individually rational agents, in: Proc. Third International Conference on Multi-Agent Systems (ICMAS), Pans, France, 1998, pp 26-33.

[2]

M.R. Andersson, T. Sandholm, Time-quality tradeoffs in reallocative negotiation with combinatorial contract types, in: Proc. AAAI-99, Orlando, FL, 1999, pp. 3-10.

[3]

M. Andersson, T. Sandholm, Contract type sequencing for reallocative negotiation, in: Proc. Twentieth International Conference on Distributed Computing Systems, Taipei, Taiwan, 2000,

[4]

M.R. Andersson, T. Sandholm, Leveled commitment contracts with mxopic and strategic agents, J. Economic Dynamics and Control (Special Issue on Agent-Based Computational Economics.) 25 (2001) 615-640, early version appeared in: Proc. AAAI-98, Madison, WI, 1998, pp. 38-45.

[5]

C. Boutilier, M. Goldszmidt, B. Sabata, Sequential auctions for the allocation of resources with complementarities, in: Proc. IJCAI-99, Stockholm, Sweden, 1999, pp. 527-534.

[6]

B. Chandra, M.M. Halldrsson, Greedy local search and weighted set packing approximation, in: Proc. 10th Annual SIAM-ACM Symposium on Discrete Algonthms (SODA), Baltimore, MD, 1999, pp. 169-176.

[7]

E.H. Clarke, Multtpart pricing of public goods, Public Choice 11(1971)17-33.

[8]

L. Comet, Advanced Combinaiorics, D. Reidel, Dordrecht, 1974.

[9]

W. Conen, T. Sandholm, Minimal preference elicitation in combinatorial auctions, in: Proc. IJCAI.200I Workshop on Economic Agents. Models, and Mechanisms, Seattle, WA, 2001, pp. 71-80.

[10]

W. Conen, T. Sandholm, Preference elicitation in combinatorial auctions: Extended abstract, in: Proc. ACM Conference on Electronic Commerce (ACM-EC). Tampa, FL, 2001.

Digital Library

[11]

W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver. Combinatorial Optimization, Wiley. New York, 1998.

[12]

T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge. MA, 1990.

[13]

S. de Vries, R. Vohra, Combinatorial auctions: A survey. Draft, August 28th. 2000.

[14]

C. DeMartini, A. Kwasnica, J. Ledyard, D. Porter, A new and improved design for multiobject iterative auctions, Technical Report 1054, California Institute of Technology, Social Science, 1998.

[15]

Y. Fujtshima, K. Leyton-Brown, Y Shoham, Taming the computational complexity of combinatonal auctions'. Optimal and approximate approaches, in: Proc. IJCAI-99, Stockholm. Sweden, 1999, pp. 548-553.

[16]

R. Garfinkel, G. Nemhauser, The set partitioning problem: Set covering with equality constraints, Oper. Res. 17(5) (1969) 848-856.

Digital Library

[17]

T. Groves, Incentives in teams, Econometnca 41 (1973) 617-631.

[18]

M.M. Halldrsson, Approximations of independent sets in graphs, in: K. Jansen, J. Rolim (Eds.), The First International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Aalburg, Denmark, Lecture Notes in Computer Science, Vol. 1444, Springer, Berlin, 1998, pp 1-14.

[19]

M.M. Halldrsson, Approximations of weighted independent set and hereditary subset problems, in: Computing and Combinatorics. J. Graph Algorithms AppI. 4 (I) (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, Vol. 1627. Spnnger. Berlin, 1999, pp. 261-70.

[20]

M.M. Halldrsson, J, Kratochvl, J.A. Telle. Independent sets with domination constraints, Discrete AppI. Math. (1998): also appeared in' Proceedings of the 25th International Conference on Automata, Languages, and Programing (ICALP), Aalborg. Denmark, Sprinter Lecture Note, in Computer Science. Vol 1443. July 1998.

[21]

M.M. Halldrsson, H.C. Lau, Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and 3-coloring, J. Graph Algorithm AppI. 1(3) (1997) 1-13.

[22]

J. Hstad, Clique is hard to approximate within Acta Mathematica 182 (1999) 105-142.

[23]

D.B. Hausch, Multi-object auctions: Sequential vs. simultaneous sales, Management Set. 32 (1986) 1599-1610.

Digital Library

[24]

D.S. Hochbaum, Efficient bounds for the stable set, vertex cover, and set packing problems, Discrete Appi Math. 6(1983)243-254.

[25]

D.S. Hochbaum, Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston, MA. 1997.

[26]

R.M. Karp, Reducibility among combinatorial problems, in: RE. Miller, 1W. Thatcher (Eds.), Complexity of Computer Computations. Plenum Press, New York, 1972, pp. 85-103.

[27]

F. Kelly, R. Steinberg, A combinatorial auction with multiple winners for universal services. Management Sci. 46(4) (2000) 586-596.

Digital Library

[28]

R.E. Korf, Depth-first iterative-deepening: An optimal admissible tree search, Artificial Intelligence 27 (1) (1985)97-109.

Digital Library

[29]

K. Larson, T. Sandholm. Computationally limited agents in auctions, in: Pros, AGENTS-01 Workshop Agents for B2B. Montreal, Canada. 2001, pp. 27-34.

[30]

K. Larson, T. Sandholm, Costly valuation computation in auctions: Deliberation equilibrium, in Pio, Theoretical Aspects of Reasoning about Knowledge (TARK), Siena, Italy, 2001, pp. 169-182.

[31]

J. Ledyard, Personal communications at the National Science Foundation Workshop on Research Prioritics in Electronic Commerce. Austin, TX, 1998.

[32]

D. Lehmann, L.I. O'Callaghan, Y. Shoham, Truth revelation in rapid, approximately efficient combinaton:l auctions, in: Proc. ACM Conference on Electronic Commerce (ACM-EC), Denver, CO, 1999, pp. 96-} 112

Digital Library

[33]

E. Loukakis, C. Tsouros, An algorithm for the maximum internally stable set in a weighted graph. Internat. J. Comput. Math. 13(1983)117-129.

[34]

R. Preston McAfee, J. McMillan, Analyzing the airwaves auction, 1. Economic Perspectives 10(1) (l996) 159-175,

[35]

J. McMillan. Selling spectrum rights, J. Economic Perspectives 8(3) (1994) 145-162.

[36]

P. Milgrom, Putting auction theory to work: The simultaneous ascending auction, Technical Report. .Sian}rd University, Department of Economics, 1997. Revised 4/21/1999.

[37]

N. Nisan. Bidding and allocation in combinatorial auctions, in: Proc. ACM Conference On Electronic Commerce (ACM-EC). Minneapolis. MN, 2000, pp. 1-12.

Digital Library

[38]

C.H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading. MA. 1995.

[39]

P.M. Pardalos, N. Desai, An algorithm for finding a maximum weighted independent set in an arbitrary graph. Internat. 1. Contain. Math. 38(1991)163-175.

[40]

S.J. Rassenti, V.L. Smith, R.L.,Bulfin, A combinatorial auction mechanism for airport time slot allocation, Bell 1. Econom. 13 (1982) 402-417.

[41]

A. Reinefeld, V. Schnecke, AIDA*_Asynchronous parallel IDA*, in: Proc. 10th Canadian Conf. on Al Banff. Alberta, 1994, pp. 295-302.

[42]

M.H. Rothkopf, A. Pekec, R.M. Harstad, Computationally manageable combinatorial auctions, Management Sci.44(8)(1998) 1131-1147.

Digital Library

[43]

T. Sandholm, A strategy for decreasing the total transportation costs among areadistributed transpori.it centers, in: Nordic Operations Analysis in Cooperation (NOAS): OR in Business, Turku Schoii Economics, Finland, 1991.

[44]

T. Sandholm, An implementation of the contract net protocol based on marginal cost calculations, in: Proc. AAAI-93. Washington, DC. 1993. pp. 256-262.

[45]

T. Sandholm, Negotiation among self-interested computationally limited agents, Ph.D. Thesis, University of Massachusetts, Amherst, MA, 1996. Available at http://www.cs.cmu.edu/sandholtrL/dissertatlOn.ps.

[46]

T. Sandholm, Contract types for satisficing task allocation, I: Theoretical results, in: Proc. AAAI Spring Symposium Series: Satislicing Models, Stanford University, CA. 1998, pp. 68-75.

[47]

T. Sandholm, eMediator: A next generation electronic commerce server, in: Proc. Fourth International Conference on Autonomous Agents (AGENTS), Barcelona, Spain. 2000, pp. 73-96; early version appeared in: Proc. AAAI-99 Workshop on Al 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]

T. Sandholm, Issues in computational Vickrey auctions. Internal. J. Electronic Commerce 4(3) (2000) 107129. Special Issue on Applying Intelligent Agents for Electronic Commerce. A short, early version appeared at he Second International Conference on Multi-Agent Systems (ICMAS), 1996, pp. 299-306.

[49]

T. Sandholm, K.S. Larson, M.R. Andersson, 0. Shehory, F. Tohm, Coalition structure generation with worst case guarantees. Artificial Intelligence Ill (-2) (1999) 209-238; early version appeared in: Proc. AAAI-98, Madison, WI, 1998, pp. 46-53.

[50]

T. Sandholm, V.R. Lesser, Issues in automated negotiation and electronic commerce: Extending the contract net framework, in: Proc. First International Conference on Multi-Agent Systems (ICMAS), San Francisco, CA, 1995, pp. 328-335. Reprinted in: M.N. Hubris and M.P. Singh (Eds.), Readings in Agents, Morgan Kaufmann, San Maieo, CA, 1997, pp. 66-73.

[51]

T. Sandholm, V.R. Lesser, Leveled commitment contracts and strategic breach, Games and Economic Behavior (Special issue on Al and Economics) 35 (2001) 212-270. Short early version appeared as 'Advantages of a Leveled Commitment Contracting Protocol' in: Proc. AAAI96. Portland. OR, 1996, pp. 126-133. Extended version: University of Massachusetts at Amherst, Computer Science Department, Technical Report 95-72.

[52]

T. Sandholm, S. Sikka, S. Norden, Algonthms for optimizing leveled commitment contracts, in: Proc. IJCAI-99. Stockholm, Sweden, 1999. pp. 535-540. Extended version: Washington University, Department of Computer Science, Technical Report WUCS-99-04.

[53]

T. Sandholm. S. Suri, Improved algorithms for optimal winner determination in combinatorial auctions and generalizations, in, Proc. AAAI-00, Austin, TX, 2000, pp. 90-97.

[54]

T, Sandholm, S Suri, Market clearability, in: Proc. IJCAI-01, Seattle, WA. 2001. pp. 1145-1151.

[55]

T. Sandholm, S. Suri, Side constraints and non-price attributes in markets, in: Proc. IJCAI2001 Workshop on Distributed Constraint Reasoning, Seattle, WA, 2001, pp. 55-61.

[56]

T. Sandholm, S. Suri, A. Gilpin, D. Levine. CABOB: A fast optimal algorithm for combinatorial auctions, in: Proc. IJCAI-0l, Seattle, WA, 2001, pp. 1102-1108.

[57]

T. Sandholm, S. Suri, A. Gilpin, D. Levine. Winner determination in combinatonal auction generalizations, in: Proc. AGENTS-al Workshop on Agent-Based Approaches to B2B, Montreal, Canada, 2001, pp. 35-41.

[58]

W. Vickrey. Counterspeculation. auctions, and competitive sealed lenders, J. Finance 16 (1961) 8-37.

[59]

Wireless Telecommunications Bureau. Federal Communications Commission, Wireless telecommunications action WT 98-35, September 1998.

[60]

L.A. Wolsey. Integer Programming. Wiley. New York, 1998.

[61]

P.R. Wurman, M.P. Wellman, WE. Walsh, The Michigan Internet AuctionBot: A configurable auction server for human and software agents, in: Proc. Second International Conference on Autonomous Agents (AGENTS), Minneapolis/St. Paul, MN, 1998, pp. 301-308.

Digital Library

Cited By

Balcan MDick TSandholm TVitercik E(2024)Learning to Branch: Generalization Guarantees and Limits of Data-Independent DiscretizationJournal of the ACM10.1145/363784071:2(1-73)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3637840
Liu XLi W(2024)A Truthful Randomized Mechanism for Heterogeneous Resource Allocation With Multi-Minded in Mobile Edge ComputingIEEE Transactions on Network and Service Management10.1109/TNSM.2024.342607621:5(5677-5690)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TNSM.2024.3426076
Baumeister DBoes LLaußmann CRey SAgmon NAn BRicci AYeoh W(2023)Bounded Approval Ballots: Balancing Expressiveness and Simplicity for Multiwinner ElectionsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598790(1400-1408)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598790
Show More Cited By

Index Terms

Algorithm for optimal winner determination in combinatorial auctions

Recommendations

BOB: improved winner determination in combinatorial auctions and generalizations

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 ...
Mixed-bundling auctions with reserve prices
AAMAS '12: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2

Revenue maximization in multi-item settings is notoriously elusive. This paper studies a class of two-item auctions which we call a mixed-bundling auction with reserve prices (MBARP). It calls VCG on an enlarged set of agents by adding the seller---who ...
Competing Combinatorial Auctions
Combinatorial auctions are auctions in which bids can be submitted on sets of items, rather than just on individual items. These auctions are generally beneficial to both auctioneers and bidders, as they allow bidders to express their synergies for sets ...
We investigate whether revenue-maximizing auctioneers selling heterogeneous items will allow for combinatorial bidding in the presence of auctioneer competition. We compare the choice of auction format by two competing auctioneers with that of a single ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence

Artificial Intelligence Volume 135, Issue 1-2

02/01/2002

233 pages

ISSN:0004-3702

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 February 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

243
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Balcan MDick TSandholm TVitercik E(2024)Learning to Branch: Generalization Guarantees and Limits of Data-Independent DiscretizationJournal of the ACM10.1145/363784071:2(1-73)Online publication date: 10-Apr-2024
https://dl.acm.org/doi/10.1145/3637840
Liu XLi W(2024)A Truthful Randomized Mechanism for Heterogeneous Resource Allocation With Multi-Minded in Mobile Edge ComputingIEEE Transactions on Network and Service Management10.1109/TNSM.2024.342607621:5(5677-5690)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TNSM.2024.3426076
Baumeister DBoes LLaußmann CRey SAgmon NAn BRicci AYeoh W(2023)Bounded Approval Ballots: Balancing Expressiveness and Simplicity for Multiwinner ElectionsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598790(1400-1408)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598790
Bichler MMilgrom PSchwarz G(2023)Taming the Communication and Computation Complexity of Combinatorial AuctionsManagement Science10.1287/mnsc.2022.446569:4(2217-2238)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1287/mnsc.2022.4465
Balcan MPrasad SSandholm TKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Maximizing revenue under market shrinkage and market uncertaintyProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3600390(1643-1655)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3600390
Präntare FOsipov GEriksson LPelachaud CTaylor MFaliszewski PMascardi V(2022)Concise Representations and Complexity of Combinatorial Assignment ProblemsProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3536086(1714-1716)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3536086
Präntare FAppelgren HTiger MBergström DHeintz FPelachaud CTaylor MFaliszewski PMascardi V(2022)Learning Heuristics for Combinatorial Assignment by Optimally Solving SubproblemsProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3535970(1074-1082)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3535970
Umer ANazir BAhmad Z(2022)Adaptive market-oriented combinatorial double auction resource allocation model in cloud computingThe Journal of Supercomputing10.1007/s11227-021-03918-x78:1(1244-1286)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s11227-021-03918-x
Wu JCao JSun HWang C(2022)A Bayesian optimal social law synthesizing mechanism for strategical agentsAutonomous Agents and Multi-Agent Systems10.1007/s10458-022-09576-436:2Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10458-022-09576-4
Deligkas AMelissourgos TSpirakis PDignum FLomuscio AEndriss UNowé A(2021)Walrasian Equilibria in Markets with Small DemandsProceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3463952.3464005(413-419)Online publication date: 3-May-2021
https://dl.acm.org/doi/10.5555/3463952.3464005
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents