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
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.49.11.1485.20585
    Download Restriction: no

    References listed on IDEAS

    as
    1. Estelle Cantillon, 2002. "Combination Bidding in Multi-Unit Auctions," Theory workshop papers 357966000000000091, UCLA Department of Economics.
    2. Peter Cramton & Morley Gunderson & Joseph Tracy, 1999. "The Effect Of Collective Bargaining Legislation On Strikes And Wages," The Review of Economics and Statistics, MIT Press, pages 475-487.
    3. 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.
    4. 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.
    5. Frank Kelly & Richard Steinberg, 2000. "A Combinatorial Auction with Multiple Winners for Universal Service," Management Science, INFORMS, vol. 46(4), pages 586-596, April.
    6. 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.
    7. Marcel Fafchamps & Agnes R. Quisumbing, 1999. "Human Capital, Productivity, and Labor Allocation in Rural Pakistan," Journal of Human Resources, University of Wisconsin Press, pages 369-406.
    8. Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
    9. 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.
    10. Michael H. Rothkopf & Aleksandar Pekev{c} & Ronald M. Harstad, 1998. "Computationally Manageable Combinational Auctions," Management Science, INFORMS, vol. 44(8), pages 1131-1147, August.
    11. Peter Cramton, 1995. "Money Out of Thin Air: The Nationwide Narrowband PCS Auction," Papers of Peter Cramton 95jems, University of Maryland, Department of Economics - Peter Cramton, revised 09 Jun 1998.
    12. Lawrence M. Ausubel & Peter Cramton & R. Preston McAfee & John McMillan, 1997. "Synergies in Wireless Telephony: Evidence from the Broadband PCS Auctions," Journal of Economics & Management Strategy, Wiley Blackwell, pages 497-527.
    13. 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.
    14. Cramton, Peter C, 1995. "Money Out of Thin Air: The Nationwide Narrowband PCS Auction," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 4(2), pages 267-343, Summer.
    15. Krishna, Vijay & Rosenthal, Robert W., 1996. "Simultaneous Auctions with Synergies," Games and Economic Behavior, Elsevier, vol. 17(1), pages 1-31, November.
    16. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    17. 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.
    18. 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, pages 1-25.
    19. Milgrom, Paul R & Weber, Robert J, 1982. "A Theory of Auctions and Competitive Bidding," Econometrica, Econometric Society, vol. 50(5), pages 1089-1122, September.
    20. Peter Cramton, 1997. "The FCC Spectrum Auctions: An Early Assessment," Journal of Economics & Management Strategy, Wiley Blackwell, vol. 6(3), pages 431-495, September.
    21. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    22. Marc S. Robinson, 1985. "Collusion and the Choice of Auction," RAND Journal of Economics, The RAND Corporation, pages 141-145.
    23. 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.
    24. 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.
    25. 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.
    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. 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.
    2. Pickl, Matthias & Wirl, Franz, 2011. "Auction design for gas pipeline transportation capacity--The case of Nabucco and its open season," Energy Policy, Elsevier, vol. 39(4), pages 2143-2151, April.
    3. Griffin, Robert, 2013. "Auction designs for allocating wind energy leases on the U.S. outer continentalshelf," Energy Policy, Elsevier, vol. 56(C), pages 603-611.
    4. Ahlert, Klaus-Henning & Corsten, Hans & Gössinger, Ralf, 2009. "Capacity management in order-driven production networks--A flexibility-oriented approach to determine the size of a network capacity pool," International Journal of Production Economics, Elsevier, vol. 118(2), pages 430-441, April.
    5. Muñoz, Juan Carlos & Molina, Diego, 2009. "A multi-unit tender award process: The case of Transantiago," European Journal of Operational Research, Elsevier, vol. 197(1), pages 307-311, August.
    6. Schellhorn, Henry, 2009. "A double-sided multiunit combinatorial auction for substitutes: Theory and algorithms," European Journal of Operational Research, Elsevier, vol. 197(2), pages 799-808, September.
    7. Cheng, Meng & Xu, Su Xiu & Huang, George Q., 2016. "Truthful multi-unit multi-attribute double auctions for perishable supply chain trading," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 93(C), pages 21-37.
    8. Xu, Su Xiu & Huang, George Q., 2013. "Transportation service procurement in periodic sealed double auctions with stochastic demand and supply," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 136-160.
    9. Choi, Jin Ho & Chang, Yong Sik & Han, Ingoo, 2009. "The empirical analysis of the N-bilateral optimized combinatorial auction model," Omega, Elsevier, vol. 37(2), pages 482-493, April.
    10. Schellhorn, Henry, 2011. "A trading mechanism contingent on several indices," European Journal of Operational Research, Elsevier, vol. 213(3), pages 551-558, September.
    11. Meeus, Leonardo & Verhaegen, Karolien & Belmans, Ronnie, 2009. "Block order restrictions in combinatorial electric energy auctions," European Journal of Operational Research, Elsevier, vol. 196(3), pages 1202-1206, August.
    12. Tong Che & Zeyu Peng & Zhongsheng Hua, 2016. "Characteristics of online group-buying website and consumers intention to revisit: the moderating effects of visit channels," Electronic Commerce Research, Springer, vol. 16(2), pages 171-188, June.
    13. 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.
    14. Feng, Bo & Li, Yanzhi & Shen, Huaxiao, 2015. "Tying mechanism for airlines’ air cargo capacity allocation," European Journal of Operational Research, Elsevier, vol. 244(1), pages 322-330.
    15. Avenali, Alessandro & D'Alfonso, Tiziana & Leporelli, Claudio & Matteucci, Giorgio & Nastasi, Alberto & Reverberi, Pierfrancesco, 2015. "An incentive pricing mechanism for efficient airport slot allocation in Europe," Journal of Air Transport Management, Elsevier, vol. 42(C), pages 27-36.
    16. Doukidis, Georgios I. & Pramatari, Katerina & Lekakos, Georgios, 2008. "OR and the management of electronic services," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1296-1309, June.
    17. Henry Schellhorn, 2004. "A Double-Sided Multiunit Combinatorial Auction for Substitutes: Theory and Algorithms," FAME Research Paper Series rp123, International Center for Financial Asset Management and Engineering.
    18. 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.
    19. Lorentziadis, Panos L., 2008. "Pricing in multiple-item procurement auctions with a common to all items fixed cost," European Journal of Operational Research, Elsevier, vol. 190(3), pages 790-797, November.
    20. Perennes, Patricia, 2014. "Use of combinatorial auctions in the railway industry: Can the “invisible hand” draw the railway timetable?," Transportation Research Part A: Policy and Practice, Elsevier, vol. 67(C), pages 175-187.
    21. 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.
    22. 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.
    23. Margaretha Gansterer & Richard F. Hartl, 2016. "Request evaluation strategies for carriers in auction-based collaborations," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 3-23, January.
    24. Bagchi, Aniruddha & Aliyas Paul, Jomon & Maloni, Michael, 2011. "Improving bid efficiency for humanitarian food aid procurement," International Journal of Production Economics, Elsevier, vol. 134(1), pages 238-245, November.

    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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc). General contact details of provider: http://edirc.repec.org/data/inforea.html .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.