CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions
Author
Suggested Citation
DOI: 10.1287/mnsc.1040.0336
Download full text from publisher
References listed on IDEAS
- Frank Kelly & Richard Steinberg, 2000. "A Combinatorial Auction with Multiple Winners for Universal Service," Management Science, INFORMS, vol. 46(4), pages 586-596, April.
- Ausubel Lawrence M & Milgrom Paul R, 2002.
"Ascending Auctions with Package Bidding,"
The B.E. Journal of Theoretical Economics, De Gruyter, vol. 1(1), pages 1-44, August.
- Lawrence M. Ausubel & Paul Milgrom, 2002. "Ascending Auctions with Package Bidding," Working Papers 02004, Stanford University, Department of Economics.
- Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
- Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
- ., 2000. "Information costs and the division of labor," Chapters, in: Macroeconomic Instability and Coordination, chapter 14, Edward Elgar Publishing.
- John McMillan, 1994. "Selling Spectrum Rights," Journal of Economic Perspectives, American Economic Association, vol. 8(3), pages 145-162, Summer.
- S.J. Rassenti & V.L. Smith & R.L. Bulfin, 1982. "A Combinatorial Auction Mechanism for Airport Time Slot Allocation," Bell Journal of Economics, The RAND Corporation, vol. 13(2), pages 402-417, Autumn.
- Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
- Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
- Michael H. Rothkopf & Aleksandar Pekev{c} & Ronald M. Harstad, 1998. "Computationally Manageable Combinational Auctions," Management Science, INFORMS, vol. 44(8), pages 1131-1147, August.
- Karla L. Hoffman & Manfred Padberg, 1993. "Solving Airline Crew Scheduling Problems by Branch-and-Cut," Management Science, INFORMS, vol. 39(6), pages 657-682, June.
- Atamturk, Alper & Nemhauser, George L. & Savelsbergh, Martin W. P., 2000. "Conflict graphs in solving integer programming problems," European Journal of Operational Research, Elsevier, vol. 121(1), pages 40-55, February.
- R. Preston McAfee & John McMillan, 1996. "Analyzing the Airwaves Auction," Journal of Economic Perspectives, American Economic Association, vol. 10(1), pages 159-175, Winter.
Citations
Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
Cited by:
- Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2007. "Column aggregation-based pricing combinatorial auctions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 624, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
- Dries R. Goossens & Sander Onderstal & Jan Pijnacker & Frits C. R. Spieksma, 2014. "Solids: A Combinatorial Auction for Real Estate," Interfaces, INFORMS, vol. 44(4), pages 351-363, August.
- Rancourt, Marie-Ève & Bellavance, François & Goentzel, Jarrod, 2014. "Market analysis and transportation procurement for food aid in Ethiopia," Socio-Economic Planning Sciences, Elsevier, vol. 48(3), pages 198-219.
- Dixit, Aasheesh Kumar & Shakya, Garima & Jakhar, Suresh Kumar & Nath, Swaprava, 2023. "Algorithmic mechanism design for egalitarian and congestion-aware airport slot allocation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 169(C).
- Abhishek Ray & Mario Ventresca & Karthik Kannan, 2021. "A Graph-Based Ant Algorithm for the Winner Determination Problem in Combinatorial Auctions," Information Systems Research, INFORMS, vol. 32(4), pages 1099-1114, December.
- G. Anandalingam & Robert W. Day & S. Raghavan, 2005. "The Landscape of Electronic Market Design," Management Science, INFORMS, vol. 51(3), pages 316-327, March.
- Stößer, Jochen & Neumann, Dirk & Weinhardt, Christof, 2010. "Market-based pricing in grids: On strategic manipulation and computational cost," European Journal of Operational Research, Elsevier, vol. 203(2), pages 464-475, June.
- Gülşah Karakaya & Murat Köksalan, 2016. "An interactive approach for Bi-attribute multi-item auctions," Annals of Operations Research, Springer, vol. 245(1), pages 97-119, October.
- Alidaee, Bahram & Kochenberger, Gary & Lewis, Karen & Lewis, Mark & Wang, Haibo, 2008. "A new approach for modeling and solving set packing problems," European Journal of Operational Research, Elsevier, vol. 186(2), pages 504-512, April.
- A Drexl & K Jørnsten, 2007.
"Reflections about pseudo-dual prices in combinatorial auctions,"
Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1652-1659, December.
- Drexl, Andreas & Jörnsten, Kurt, 2005. "Reflections about pseudo-dual prices in combinatorial auctions," Discussion Papers 2005/1, Norwegian School of Economics, Department of Business and Management Science.
- Drexl, Andreas & Jörnsten, Kurt, 2005. "Reflections about pseudo-dual prices in combinatorial auctions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 590, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
- Yunpeng Pan & Zhe Liang, 2017. "Dual relaxations of the time-indexed ILP formulation for min–sum scheduling problems," Annals of Operations Research, Springer, vol. 249(1), pages 197-213, February.
- Chang, Tsung-Sheng, 2009. "Decision support for truckload carriers in one-shot combinatorial auctions," Transportation Research Part B: Methodological, Elsevier, vol. 43(5), pages 522-541, June.
- Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2009.
"Non-linear anonymous pricing combinatorial auctions,"
European Journal of Operational Research, Elsevier, vol. 199(1), pages 296-302, November.
- Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2005. "Non-linear anonymous pricing in combinatorial auctions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 598, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
- Drexl, Andreas & Jörnsten, Kurt & Knof, Diether, 2005. "Non-linear anonymous pricing in combinatorial auctions," Discussion Papers 2005/6, Norwegian School of Economics, Department of Business and Management Science.
- Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2007. "Non-linear anonymous pricing combinatorial auctions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 625, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
- Mu'alem, Ahuva & Nisan, Noam, 2008. "Truthful approximation mechanisms for restricted combinatorial auctions," Games and Economic Behavior, Elsevier, vol. 64(2), pages 612-631, November.
- Robert W. Day & S. Raghavan, 2009. "Matrix Bidding in Combinatorial Auctions," Operations Research, INFORMS, vol. 57(4), pages 916-933, August.
- Ervasti, Valtteri & Leskelä, Riikka-Leena, 2010. "Allocative efficiency in simulated multiple-unit combinatorial auctions with quantity support," European Journal of Operational Research, Elsevier, vol. 203(1), pages 251-260, May.
- Dries R. Goossens & Rudolf Müller & Frits C. R. Spieksma, 2010. "Algorithms for Recognizing Economic Properties in Matrix Bid Combinatorial Auctions," INFORMS Journal on Computing, INFORMS, vol. 22(3), pages 339-352, August.
- Richard Li-Yang Chen & Shervin AhmadBeygi & Amy Cohn & Damian R. Beil & Amitabh Sinha, 2009. "Solving Truckload Procurement Auctions Over an Exponential Number of Bundles," Transportation Science, INFORMS, vol. 43(4), pages 493-510, November.
- Schnizler, Bjorn & Neumann, Dirk & Veit, Daniel & Weinhardt, Christof, 2008. "Trading grid services - a multi-attribute combinatorial approach," European Journal of Operational Research, Elsevier, vol. 187(3), pages 943-961, June.
- Mercedes Landete & Juan Monge & Antonio Rodríguez-Chía, 2013. "Alternative formulations for the Set Packing Problem and their application to the Winner Determination Problem," Annals of Operations Research, Springer, vol. 207(1), pages 137-160, August.
- Gediminas Adomavicius & Shawn P. Curley & Alok Gupta & Pallab Sanyal, 2012. "Effect of Information Feedback on Bidder Behavior in Continuous Combinatorial Auctions," Management Science, INFORMS, vol. 58(4), pages 811-830, April.
- Tuomas Sandholm & David Levine & Michael Concordia & Paul Martyn & Rick Hughes & Jim Jacobs & Dennis Begg, 2006. "Changing the Game in Strategic Sourcing at Procter & Gamble: Expressive Competition Enabled by Optimization," Interfaces, INFORMS, vol. 36(1), pages 55-68, February.
- Gediminas Adomavicius & Alok Gupta & Mochen Yang, 2022. "Bidder Support in Multi-item Multi-unit Continuous Combinatorial Auctions: A Unifying Theoretical Framework," Information Systems Research, INFORMS, vol. 33(4), pages 1174-1195, December.
- Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
- Park, Sunju & Rothkopf, Michael H., 2005. "Auctions with bidder-determined allowable combinations," European Journal of Operational Research, Elsevier, vol. 161(2), pages 399-415, March.
- Oktay Günlük & Lászlo Ladányi & Sven de Vries, 2005. "A Branch-and-Price Algorithm and New Test Problems for Spectrum Auctions," Management Science, INFORMS, vol. 51(3), pages 391-406, March.
- Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2009.
"Non-linear anonymous pricing combinatorial auctions,"
European Journal of Operational Research, Elsevier, vol. 199(1), pages 296-302, November.
- Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2005. "Non-linear anonymous pricing in combinatorial auctions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 598, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
- Drexl, Andreas & Jörnsten, Kurt & Knof, Diether, 2005. "Non-linear anonymous pricing in combinatorial auctions," Discussion Papers 2005/6, Norwegian School of Economics, Department of Business and Management Science.
- Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2007. "Non-linear anonymous pricing combinatorial auctions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 625, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
- Aleksandar Pekev{c} & Michael H. Rothkopf, 2003. "Combinatorial Auction Design," Management Science, INFORMS, vol. 49(11), pages 1485-1503, November.
- Mishra, Debasis & Parkes, David C., 2007.
"Ascending price Vickrey auctions for general valuations,"
Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
- MISHRA, Debasis & PARKES, David C., 2005. "Ascending price Vickrey auctions for general valuations," LIDAM Discussion Papers CORE 2005052, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- Drexl, Andreas & Jørnsten, Kurt & Knof, Diether, 2007. "Column aggregation-based pricing combinatorial auctions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 624, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
- Nisan, Noam & Segal, Ilya, 2006. "The communication requirements of efficient allocations and supporting prices," Journal of Economic Theory, Elsevier, vol. 129(1), pages 192-224, July.
- Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
- Tuomas Sandholm & David Levine & Michael Concordia & Paul Martyn & Rick Hughes & Jim Jacobs & Dennis Begg, 2006. "Changing the Game in Strategic Sourcing at Procter & Gamble: Expressive Competition Enabled by Optimization," Interfaces, INFORMS, vol. 36(1), pages 55-68, February.
- A Drexl & K Jørnsten, 2007.
"Reflections about pseudo-dual prices in combinatorial auctions,"
Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1652-1659, December.
- Drexl, Andreas & Jörnsten, Kurt, 2005. "Reflections about pseudo-dual prices in combinatorial auctions," Discussion Papers 2005/1, Norwegian School of Economics, Department of Business and Management Science.
- Drexl, Andreas & Jörnsten, Kurt, 2005. "Reflections about pseudo-dual prices in combinatorial auctions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 590, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
- Vohra, Rakesh V., 2015. "Combinatorial Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
- Pallab Sanyal, 2016. "Characteristics and Economic Consequences of Jump Bids in Combinatorial Auctions," Information Systems Research, INFORMS, vol. 27(2), pages 347-364, June.
- G. Anandalingam & Robert W. Day & S. Raghavan, 2005. "The Landscape of Electronic Market Design," Management Science, INFORMS, vol. 51(3), pages 316-327, March.
- Blumrosen, Liad & Nisan, Noam, 2010. "Informational limitations of ascending combinatorial auctions," Journal of Economic Theory, Elsevier, vol. 145(3), pages 1203-1223, May.
- Avenali, Alessandro, 2009. "Exploring the VCG mechanism in combinatorial auctions: The threshold revenue and the threshold-price rule," European Journal of Operational Research, Elsevier, vol. 199(1), pages 262-275, November.
- Martin Bichler & Pasha Shabalin & Alexander Pikovsky, 2009. "A Computational Analysis of Linear Price Iterative Combinatorial Auction Formats," Information Systems Research, INFORMS, vol. 20(1), pages 33-59, March.
- Anthony M. Kwasnica & John O. Ledyard & Dave Porter & Christine DeMartini, 2005.
"A New and Improved Design for Multiobject Iterative Auctions,"
Management Science, INFORMS, vol. 51(3), pages 419-434, March.
- DeMartini, Christine & Kwasnica, Anthony M. & Ledyard, John O. & Porter, David, 1998. "A New and Improved Design For Multi-Object Iterative Auctions," Working Papers 1054, California Institute of Technology, Division of the Humanities and Social Sciences.
- Ning Sun & Zaifu Yang, 2014.
"An Efficient and Incentive Compatible Dynamic Auction for Multiple Complements,"
Journal of Political Economy, University of Chicago Press, vol. 122(2), pages 422-466.
- Ning Sun & Zaifu Yang, 2014. "An Efficient and Incentive Compatible Dynamic Auction for Multiple Complements," Discussion Papers 14/06, Department of Economics, University of York.
- Ausubel Lawrence M & Milgrom Paul R, 2002.
"Ascending Auctions with Package Bidding,"
The B.E. Journal of Theoretical Economics, De Gruyter, vol. 1(1), pages 1-44, August.
- Lawrence M. Ausubel & Paul Milgrom, 2002. "Ascending Auctions with Package Bidding," Working Papers 02004, Stanford University, Department of Economics.
More about this item
Keywords
auction; combinatorial auction; winner determination; winner-determination algorithm; search; branch and bound; MIP; anytime algorithm; branching heuristics; dynamically chosen heuristic; bounding across components; random restart;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:51:y:2005:i:3:p:374-390. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.