IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v153y2007i1p131-16410.1007-s10479-007-0179-z.html
   My bibliography  Save this article

Combinatorial auctions

Author

Listed:
  • Jawad Abrache
  • Teodor Crainic
  • Michel Gendreau
  • Monia Rekik

Abstract

Combinatorial auctions are an important class of market mechanisms in which participants are allowed to bid on bundles of multiple heterogeneous items. In this paper, we discuss several complex issues that are encountered in the design of combinatorial auctions. These issues are related to the formulation of the winner determination problem, the expression of combined bids, the design of progressive combinatorial auctions that require less information revelation, and the need for decision support tools to help participants make profitable bidding decisions. For each issue, we survey the existing literature and propose avenues for further research. Copyright Springer Science+Business Media, LLC 2007

Suggested Citation

  • Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    • Handle: RePEc:spr:annopr:v:153:y:2007:i:1:p:131-164:10.1007/s10479-007-0179-z
    DOI: 10.1007/s10479-007-0179-z
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-007-0179-z
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-007-0179-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Bourbeau, Benoit & Gabriel Crainic, Teodor & Gendreau, Michel & Robert, Jacques, 2005. "Design for optimized multi-lateral multi-commodity markets," European Journal of Operational Research, Elsevier, vol. 163(2), pages 503-529, June.
    2. Rafael Epstein & Lysette Henríquez & Jaime Catalán & Gabriel Y. Weintraub & Cristián Martínez, 2002. "A Combinational Auction Improves School Meals in Chile," Interfaces, INFORMS, vol. 32(6), pages 1-14, December.
    3. Aleksandar Pekev{c} & Michael H. Rothkopf, 2003. "Combinatorial Auction Design," Management Science, INFORMS, vol. 49(11), pages 1485-1503, November.
    4. 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.
    5. de Vries, Sven & Schummer, James & Vohra, Rakesh V., 2007. "On ascending Vickrey auctions for heterogeneous objects," Journal of Economic Theory, Elsevier, vol. 132(1), pages 95-118, January.
    6. Xia, Mu & Koehler, Gary J. & Whinston, Andrew B., 2004. "Pricing combinatorial auctions," European Journal of Operational Research, Elsevier, vol. 154(1), pages 251-270, April.
    7. Lee, Chi-Guhn & Kwon, Roy H. & Ma, Zhong, 2007. "A carrier's optimal bid generation problem in combinatorial auctions for transportation procurement," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 43(2), pages 173-191, March.
    8. Paul Klemperer, 1999. "Auction Theory: A Guide to the Literature," Journal of Economic Surveys, Wiley Blackwell, vol. 13(3), pages 227-286, July.
    9. Frank Kelly & Richard Steinberg, 2000. "A Combinatorial Auction with Multiple Winners for Universal Service," Management Science, INFORMS, vol. 46(4), pages 586-596, April.
    10. John O. Ledyard & Mark Olson & David Porter & Joseph A. Swanson & David P. Torma, 2002. "The First Use of a Combined-Value Auction for Transportation Services," Interfaces, INFORMS, vol. 32(5), pages 4-12, October.
    11. 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.
    12. Mas-Colell, Andreu & Whinston, Michael D. & Green, Jerry R., 1995. "Microeconomic Theory," OUP Catalogue, Oxford University Press, number 9780195102680, Decembrie.
    13. Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
    14. Gul, Faruk & Stacchetti, Ennio, 2000. "The English Auction with Differentiated Commodities," Journal of Economic Theory, Elsevier, vol. 92(1), pages 66-95, May.
    15. Wurman, Peter R. & Wellman, Michael P. & Walsh, William E., 2001. "A Parametrization of the Auction Design Space," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 304-338, April.
    16. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    17. M. E. Oren & A. C. Williams, 1975. "On Competitive Bidding," Operations Research, INFORMS, vol. 23(6), pages 1072-1079, December.
    18. Michael H. Rothkopf & Aleksandar Pekev{c} & Ronald M. Harstad, 1998. "Computationally Manageable Combinational Auctions," Management Science, INFORMS, vol. 44(8), pages 1131-1147, August.
    19. David C. Parkes & Jayant Kalagnanam, 2005. "Models for Iterative Multiattribute Procurement Auctions," Management Science, INFORMS, vol. 51(3), pages 435-451, March.
    20. Gail Hohner & John Rich & Ed Ng & Grant Reid & Andrew J. Davenport & Jayant R. Kalagnanam & Ho Soo Lee & Chae An, 2003. "Combinatorial and Quantity-Discount Procurement Auctions Benefit Mars, Incorporated and Its Suppliers," Interfaces, INFORMS, vol. 33(1), pages 23-35, February.
    21. R. H. Kwon & G. Anandalingam & L. H. Ungar, 2005. "Iterative Combinatorial Auctions with Bidder-Determined Combinations," Management Science, INFORMS, vol. 51(3), pages 407-418, March.
    22. Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
    23. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    24. Robert L. Graves & Linus Schrage & Jayaram Sankaran, 1993. "An Auction Method for Course Registration," Interfaces, INFORMS, vol. 23(5), pages 81-92, October.
    25. 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.
    26. Jeffrey S. Banks & John O. Ledyard & David P. Porter, 1989. "Allocating Uncertain and Unresponsive Resources: An Experimental Approach," RAND Journal of Economics, The RAND Corporation, vol. 20(1), pages 1-25, Spring.
    27. Lawrence M. Ausubel & Peter Cramton, 2004. "Auctioning Many Divisible Goods," Journal of the European Economic Association, MIT Press, vol. 2(2-3), pages 480-493, 04/05.
    28. Peter R. Wurman & Michael P. Wellman, 1999. "Equilibrium Prices in Bundle Auctions," Working Papers 99-09-064, Santa Fe Institute.
    29. O'Neill, Richard P. & Sotkiewicz, Paul M. & Hobbs, Benjamin F. & Rothkopf, Michael H. & Stewart, William R., 2005. "Efficient market-clearing prices in markets with nonconvexities," European Journal of Operational Research, Elsevier, vol. 164(1), pages 269-285, July.
    30. Song, Jiongjiong & Regan, Amelia, 2005. "Approximation algorithms for the bid construction problem in combinatorial auctions for the procurement of freight transportation contracts," Transportation Research Part B: Methodological, Elsevier, vol. 39(10), pages 914-933, December.
    31. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    32. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    33. Abrache, Jawad & Crainic, Teodor Gabriel & Gendreau, Michel, 2005. "Models for bundle trading in financial markets," European Journal of Operational Research, Elsevier, vol. 160(1), pages 88-105, January.
    34. Richard Engelbrecht-Wiggans, 1980. "State of the Art---Auctions and Bidding Models: A Survey," Management Science, INFORMS, vol. 26(2), pages 119-142, February.
    35. Rothkopf, Michael H & Teisberg, Thomas J & Kahn, Edward P, 1990. "Why Are Vickrey Auctions Rare?," Journal of Political Economy, University of Chicago Press, vol. 98(1), pages 94-109, February.
    36. Bikhchandani, Sushil & Mamer, John W., 1997. "Competitive Equilibrium in an Exchange Economy with Indivisibilities," Journal of Economic Theory, Elsevier, vol. 74(2), pages 385-413, June.
    37. Michael H. Rothkopf & Sunju Park, 2001. "An Elementary Introduction to Auctions," Interfaces, INFORMS, vol. 31(6), pages 83-97, December.
    38. John McMillan, 1994. "Selling Spectrum Rights," Journal of Economic Perspectives, American Economic Association, vol. 8(3), pages 145-162, Summer.
    39. Klemperer, Paul, 1999. " Auction Theory: A Guide to the Literature," Journal of Economic Surveys, Wiley Blackwell, vol. 13(3), pages 227-86, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. T. Andersson & C. Andersson & A. Talman, 2013. "Sets in excess demand in simple ascending auctions with unit-demand bidders," Annals of Operations Research, Springer, vol. 211(1), pages 27-36, December.
    2. F. Bonomo & J. Catalán & G. Durán & R. Epstein & M. Guajardo & A. Jawtuschenko & J. Marenco, 2017. "An asymmetric multi-item auction with quantity discounts applied to Internet service procurement in Buenos Aires public schools," Annals of Operations Research, Springer, vol. 258(2), pages 569-585, November.
    3. Rönnqvist, Mikael & D'Amours, Sophie & Carle, Marc-André & Azouzi, Riadh, 2018. "Timber selling policies using bundle-based auction: The case of public forests in Québec," Forest Policy and Economics, Elsevier, vol. 96(C), pages 9-18.
    4. Gansterer, Margaretha & Hartl, Richard F. & Sörensen, Kenneth, 2020. "Pushing frontiers in auction-based transport collaborations," Omega, Elsevier, vol. 94(C).
    5. Anders Lunander & Sofia Lundberg, 2013. "Bids And Costs In Combinatorial And Noncombinatorial Procurement Auctions—Evidence From Procurement Of Public Cleaning Contracts," Contemporary Economic Policy, Western Economic Association International, vol. 31(4), pages 733-745, October.
    6. Hammami, Farouk & Rekik, Monia & Coelho, Leandro C., 2021. "Exact and hybrid heuristic methods to solve the combinatorial bid construction problem with stochastic prices in truckload transportation services procurement auctions," Transportation Research Part B: Methodological, Elsevier, vol. 149(C), pages 204-229.
    7. Erik Heilmann & Nikolai Klempp & Heike Wetzel, 2020. "Market design of regional flexibility markets: A classification metric for flexibility products and its application to German prototypical flexibility markets," MAGKS Papers on Economics 202002, Philipps-Universität Marburg, Faculty of Business Administration and Economics, Department of Economics (Volkswirtschaftliche Abteilung).
    8. Vangerven, Bart & Goossens, Dries R. & Spieksma, Frits C.R., 2017. "Winner determination in geometrical combinatorial auctions," European Journal of Operational Research, Elsevier, vol. 258(1), pages 254-263.
    9. 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.
    10. Heilmann, Erik & Klempp, Nikolai & Wetzel, Heike, 2020. "Design of regional flexibility markets for electricity: A product classification framework for and application to German pilot projects," Utilities Policy, Elsevier, vol. 67(C).
    11. Gansterer, Margaretha & Hartl, Richard F. & Savelsbergh, Martin, 2020. "The value of information in auction-based carrier collaborations," International Journal of Production Economics, Elsevier, vol. 221(C).
    12. Triki, Chefi & Oprea, Simona & Beraldi, Patriza & Crainic, Teodor Gabriel, 2014. "The stochastic bid generation problem in combinatorial transportation auctions," European Journal of Operational Research, Elsevier, vol. 236(3), pages 991-999.
    13. Remli, Nabila & Amrouss, Amine & El Hallaoui, Issmail & Rekik, Monia, 2019. "A robust optimization approach for the winner determination problem with uncertainty on shipment volumes and carriers’ capacity," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 127-148.
    14. Bo Chen & Emilios Galariotis & Lijun Ma & Zijia Wang & Zhaobo Zhu, 2023. "On disclosure of participation in innovation contests: a dominance result," Annals of Operations Research, Springer, vol. 328(2), pages 1615-1629, 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.
    1. G. Anandalingam & Robert W. Day & S. Raghavan, 2005. "The Landscape of Electronic Market Design," Management Science, INFORMS, vol. 51(3), pages 316-327, March.
    2. Ronald M. Harstad & Aleksandar Saša Pekeč, 2008. "Relevance to Practice and Auction Theory: A Memorial Essay for Michael Rothkopf," Interfaces, INFORMS, vol. 38(5), pages 367-380, October.
    3. 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.
    4. Aleksandar Pekev{c} & Michael H. Rothkopf, 2003. "Combinatorial Auction Design," Management Science, INFORMS, vol. 49(11), pages 1485-1503, November.
    5. 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.
    6. Tomoya Kazumura & Shigehiro Serizawa, 2016. "Efficiency and strategy-proofness in object assignment problems with multi-demand preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 633-663, October.
    7. 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.
    8. 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.
    9. Mishra, Debasis & Parkes, David C., 2009. "Multi-item Vickrey-Dutch auctions," Games and Economic Behavior, Elsevier, vol. 66(1), pages 326-347, May.
    10. Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
    11. Vohra, Rakesh V., 2015. "Combinatorial Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    12. Blumrosen, Liad & Nisan, Noam, 2010. "Informational limitations of ascending combinatorial auctions," Journal of Economic Theory, Elsevier, vol. 145(3), pages 1203-1223, May.
    13. Xu, Su Xiu & Huang, George Q., 2014. "Efficient auctions for distributed transportation procurement," Transportation Research Part B: Methodological, Elsevier, vol. 65(C), pages 47-64.
    14. 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.
    15. Martin Bichler & Alexander Pikovsky & Thomas Setzer, 2009. "An Analysis of Design Problems in Combinatorial Procurement Auctions," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 1(1), pages 111-117, February.
    16. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    17. 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.
    18. 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.
    19. Andersson, Tommy & Erlanson, Albin, 2013. "Multi-item Vickrey–English–Dutch auctions," Games and Economic Behavior, Elsevier, vol. 81(C), pages 116-129.
    20. De Liu & Adib Bagh, 2020. "Preserving Bidder Privacy in Assignment Auctions: Design and Measurement," Management Science, INFORMS, vol. 66(7), pages 3162-3182, July.

    Corrections

    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:spr:annopr:v:153:y:2007:i:1:p:131-164:10.1007/s10479-007-0179-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.