IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v49y2003i11p1485-1503.html
   My bibliography  Save this article

Combinatorial Auction Design

Author

Listed:
  • Aleksandar Pekev{c}

    (Decision Sciences, The Fuqua School of Business, Duke University, Durham, North Carolina 27708-0120)

  • Michael H. Rothkopf

    (RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, New Jersey 08854-8003)

Abstract

Combinatorial auctions have two features that greatly affect their design: computational complexity of winner determination and opportunities for cooperation among competitors. Dealing with these forces trade-offs between desirable auction properties such as allocative efficiency, revenue maximization, low transaction costs, fairness, failure freeness, and scalability. Computational complexity can be dealt with algorithmically by relegating the computational burden to bidders, by maintaining fairness in the face of computational limitations, by limiting biddable combinations, and by limiting the use of combinatorial bids. Combinatorial auction designs include single-round, first-price sealed bidding, Vickrey-Clarke-Groves (VCG) mechanisms, uniform and market-clearing price auctions, and iterative combinatorial auctions. Combinatorial auction designs must deal with exposure problems, threshold problems, ways to keep the bidding moving at a reasonable pace, avoiding and resolving ties, and controlling complexity.

Suggested Citation

  • Aleksandar Pekev{c} & Michael H. Rothkopf, 2003. "Combinatorial Auction Design," Management Science, INFORMS, vol. 49(11), pages 1485-1503, November.
    • Handle: RePEc:inm:ormnsc:v:49:y:2003:i:11:p:1485-1503
    DOI: 10.1287/mnsc.49.11.1485.20585
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.49.11.1485.20585
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.49.11.1485.20585?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
    ---><---

    References listed on IDEAS

    as
    1. Estelle Cantillon, 2002. "Combination Bidding in Multi-Unit Auctions," Theory workshop papers 357966000000000091, UCLA Department of Economics.
    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. Rosenthal, Robert W. & Wang, Ruqu, 1996. "Simultaneous Auctions with Synergies and Common Values," Games and Economic Behavior, Elsevier, vol. 17(1), pages 32-55, November.
    4. Frank Kelly & Richard Steinberg, 2000. "A Combinatorial Auction with Multiple Winners for Universal Service," Management Science, INFORMS, vol. 46(4), pages 586-596, April.
    5. 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.
    6. 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.
    7. Rassenti, Stephen J. & Smith, Vernon L., 2008. "The Combinatorial Auction," Handbook of Experimental Economics Results, in: Charles R. Plott & Vernon L. Smith (ed.), Handbook of Experimental Economics Results, edition 1, volume 1, chapter 68, pages 644-653, Elsevier.
    8. Rothkopf, Michael H & Harstad, Ronald M, 1995. "Two Models of Bid-Taker Cheating in Vickrey Auctions," The Journal of Business, University of Chicago Press, vol. 68(2), pages 257-267, April.
    9. Cramton Peter & Schwartz Jesse A, 2002. "Collusive Bidding in the FCC Spectrum Auctions," The B.E. Journal of Economic Analysis & Policy, De Gruyter, vol. 1(1), pages 1-20, December.
    10. Peter Cramton, 1997. "The FCC Spectrum Auctions: An Early Assessment," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 6(3), pages 431-495, September.
    11. Cramton, Peter & Schwartz, Jesse A, 2000. "Collusive Bidding: Lessons from the FCC Spectrum Auctions," Journal of Regulatory Economics, Springer, vol. 17(3), pages 229-252, May.
    12. Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
    13. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    14. Krishna, Vijay & Rosenthal, Robert W., 1996. "Simultaneous Auctions with Synergies," Games and Economic Behavior, Elsevier, vol. 17(1), pages 1-31, November.
    15. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    16. Peter C. Cramton, 1995. "Money Out of Thin Air: The nationwide Narrowband pcs Auction," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 4(2), pages 267-343, June.
    17. 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.
    18. McAfee, R Preston & McMillan, John, 1987. "Auctions and Bidding," Journal of Economic Literature, American Economic Association, vol. 25(2), pages 699-738, June.
    19. 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.
    20. Brewer, Paul J. & Plott, Charles R., 1996. "A binary conflict ascending price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks," International Journal of Industrial Organization, Elsevier, vol. 14(6), pages 857-886, October.
    21. Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
    22. Michael H. Rothkopf & Aleksandar Pekev{c} & Ronald M. Harstad, 1998. "Computationally Manageable Combinational Auctions," Management Science, INFORMS, vol. 44(8), pages 1131-1147, August.
    23. 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.
    24. Peter C. Fishburn & Aleksandar Pekeč & James A. Reeds, 2002. "Subset Comparisons for Additive Linear Orders," Mathematics of Operations Research, INFORMS, vol. 27(1), pages 227-243, February.
    25. Milgrom, Paul R & Weber, Robert J, 1982. "A Theory of Auctions and Competitive Bidding," Econometrica, Econometric Society, vol. 50(5), pages 1089-1122, September.
    26. Marc S. Robinson, 1985. "Collusion and the Choice of Auction," RAND Journal of Economics, The RAND Corporation, vol. 16(1), pages 141-145, Spring.
    27. Hobbs, Benjamin F. & Rothkopf, Michael H. & Hyde, Laurel C. & O'Neill, Richard P., 2000. "Evaluation of a Truthful Revelation Auction in the Context of Energy Markets with Nonconcave Benefits," Journal of Regulatory Economics, Springer, vol. 18(1), pages 5-32, July.
    28. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. G. Anandalingam & Robert W. Day & S. Raghavan, 2005. "The Landscape of Electronic Market Design," Management Science, INFORMS, vol. 51(3), pages 316-327, March.
    3. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    4. 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.
    5. 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.
    6. Peter Cramton, 2002. "Spectrum Auctions," Papers of Peter Cramton 01hte, University of Maryland, Department of Economics - Peter Cramton, revised 16 Jul 2001.
    7. Lawrence M. Ausubel & Peter Cramton & Paul Milgrom, 2012. "System and Method for a Hybrid Clock and Proxy Auction," Papers of Peter Cramton 12acmhc, University of Maryland, Department of Economics - Peter Cramton, revised 2012.
    8. Kazumori, Eiichiro & Belch, Yaakov, 2019. "t-Tree: The Tokyo toolbox for large-scale combinatorial auction experiments," Journal of Behavioral and Experimental Finance, Elsevier, vol. 24(C).
    9. Sven de Vries & Rakesh V. Vohra, 2003. "Combinatorial Auctions: A Survey," INFORMS Journal on Computing, INFORMS, vol. 15(3), pages 284-309, August.
    10. Lawrence M. Ausubel & Paul Milgrom, 2004. "Ascending Proxy Auctions," Discussion Papers 03-035, Stanford Institute for Economic Policy Research.
    11. Committee, Nobel Prize, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.
    12. Michael H. Rothkopf, 2007. "Thirteen Reasons Why the Vickrey-Clarke-Groves Process Is Not Practical," Operations Research, INFORMS, vol. 55(2), pages 191-197, April.
    13. 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.
    14. 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.
    15. Tobias Scheffel & Alexander Pikovsky & Martin Bichler & Kemal Guler, 2011. "An Experimental Comparison of Linear and Nonlinear Price Combinatorial Auctions," Information Systems Research, INFORMS, vol. 22(2), pages 346-368, June.
    16. 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.
    17. Vohra, Rakesh V., 2015. "Combinatorial Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    18. Chernomaz, Kirill & Levin, Dan, 2012. "Efficiency and synergy in a multi-unit auction with and without package bidding: An experimental study," Games and Economic Behavior, Elsevier, vol. 76(2), pages 611-635.
    19. Pallab Sanyal, 2016. "Characteristics and Economic Consequences of Jump Bids in Combinatorial Auctions," Information Systems Research, INFORMS, vol. 27(2), pages 347-364, June.
    20. 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.

    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:inm:ormnsc:v:49:y:2003:i:11:p:1485-1503. 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.

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