IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2505.13680.html
   My bibliography  Save this paper

Weakest Bidder Types and New Core-Selecting Combinatorial Auctions

Author

Listed:
  • Siddharth Prasad
  • Maria-Florina Balcan
  • Tuomas Sandholm

Abstract

Core-selecting combinatorial auctions are popular auction designs that constrain prices to eliminate the incentive for any group of bidders -- with the seller -- to renegotiate for a better deal. They help overcome the low-revenue issues of classical combinatorial auctions. We introduce a new class of core-selecting combinatorial auctions that leverage bidder information available to the auction designer. We model such information through constraints on the joint type space of the bidders -- these are constraints on bidders' private valuations that are known to hold by the auction designer before bids are elicited. First, we show that type space information can overcome the well-known impossibility of incentive-compatible core-selecting combinatorial auctions. We present a revised and generalized version of that impossibility result that depends on how much information is conveyed by the type spaces. We then devise a new family of core-selecting combinatorial auctions and show that they minimize the sum of bidders' incentives to deviate from truthful bidding. We develop new constraint generation techniques -- and build upon existing quadratic programming techniques -- to compute core prices, and conduct experiments to evaluate the incentive, revenue, fairness, and computational merits of our new auctions. Our new core-selecting auctions directly improve upon existing designs that have been used in many high-stakes auctions around the world. We envision that they will be a useful addition to any auction designer's toolkit.

Suggested Citation

  • Siddharth Prasad & Maria-Florina Balcan & Tuomas Sandholm, 2025. "Weakest Bidder Types and New Core-Selecting Combinatorial Auctions," Papers 2505.13680, arXiv.org.
  • Handle: RePEc:arx:papers:2505.13680
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2505.13680
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Martin Bichler & Stefan Waldherr, 2022. "Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions," Operations Research, INFORMS, vol. 70(1), pages 241-264, January.
    2. Paul Klemperer, 2010. "The Product-Mix Auction: A New Auction Design for Differentiated Goods," Journal of the European Economic Association, MIT Press, vol. 8(2-3), pages 526-536, 04-05.
    3. Martin Bichler & Pasha Shabalin & Jürgen Wolf, 2013. "Do core-selecting Combinatorial Clock Auctions always lead to high efficiency? An experimental analysis of spectrum auction designs," Experimental Economics, Springer;Economic Science Association, vol. 16(4), pages 511-545, December.
    4. Benedikt Bünz & Benjamin Lubin & Sven Seuken, 2022. "Designing Core-Selecting Payment Rules: A Computational Search Approach," Information Systems Research, INFORMS, vol. 33(4), pages 1157-1173, December.
    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. Rad Niazadeh & Jason Hartline & Nicole Immorlica & Mohammad Reza Khani & Brendan Lucier, 2022. "Fast Core Pricing for Rich Advertising Auctions," Operations Research, INFORMS, vol. 70(1), pages 223-240, January.
    7. 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.
    8. Aytek Erdil & Paul Klemperer, 2010. "A New Payment Rule for Core-Selecting Package Auctions," Journal of the European Economic Association, MIT Press, vol. 8(2-3), pages 537-547, 04-05.
    9. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    10. , K. & ,, 2016. "On the impossibility of core-selecting auctions," Theoretical Economics, Econometric Society, vol. 11(1), January.
    11. Ignacio Palacios-Huerta & David C. Parkes & Richard Steinberg, 2024. "Combinatorial Auctions in Practice," Journal of Economic Literature, American Economic Association, vol. 62(2), pages 517-553, June.
    12. Myerson, Roger B. & Satterthwaite, Mark A., 1983. "Efficient mechanisms for bilateral trading," Journal of Economic Theory, Elsevier, vol. 29(2), pages 265-281, 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. Lawrence M. Ausubel & Oleg Baranov, 2020. "Core-selecting auctions with incomplete information," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(1), pages 251-273, March.
    15. Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
    16. Martin Bichler & Paul Milgrom & Gregor Schwarz, 2023. "Taming the Communication and Computation Complexity of Combinatorial Auctions: The FUEL Bid Language," Management Science, INFORMS, vol. 69(4), pages 2217-2238, April.
    17. Robert W. Day & Peter Cramton, 2012. "Quadratic Core-Selecting Payment Rules for Combinatorial Auctions," Operations Research, INFORMS, vol. 60(3), pages 588-603, June.
    18. Andor Goetzendorff & Martin Bichler & Pasha Shabalin & Robert W. Day, 2015. "Compact Bid Languages and Core Pricing in Large Multi-item Auctions," Management Science, INFORMS, vol. 61(7), pages 1684-1703, July.
    19. Bichler, Martin & Waldherr, Stefan, 2017. "Core and pricing equilibria in combinatorial exchanges," Economics Letters, Elsevier, vol. 157(C), pages 145-147.
    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. Ott, Marion & Beck, Marissa, 2013. "Incentives for Overbidding in Minimum-Revenue Core-Selecting Auctions," VfS Annual Conference 2013 (Duesseldorf): Competition Policy and Regulation in a Global Economic Order 79946, Verein für Socialpolitik / German Economic Association.
    22. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    23. Robert W. Day & S. Raghavan, 2007. "Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions," Management Science, INFORMS, vol. 53(9), pages 1389-1406, September.
    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. Benedikt Bünz & Benjamin Lubin & Sven Seuken, 2022. "Designing Core-Selecting Payment Rules: A Computational Search Approach," Information Systems Research, INFORMS, vol. 33(4), pages 1157-1173, December.
    2. Jeong, Seungwon (Eugene) & Lee, Joosung, 2024. "The groupwise-pivotal referral auction: Core-selecting referral strategy-proof mechanism," Games and Economic Behavior, Elsevier, vol. 143(C), pages 191-203.
    3. Ryuji Sano, 2018. "An equilibrium analysis of a core-selecting package auction with reserve prices," Review of Economic Design, Springer;Society for Economic Design, vol. 22(3), pages 101-122, December.
    4. Ott, Marion, 2019. "Simple Bayesian and Ex-Post Equilibria in Combinatorial Auctions," VfS Annual Conference 2019 (Leipzig): 30 Years after the Fall of the Berlin Wall - Democracy and Market Economy 203616, Verein für Socialpolitik / German Economic Association.
    5. Lamprirni Zarpala & Dimitris Voliotis, 2022. "A core-selecting auction for portfolio's packages," Papers 2206.11516, arXiv.org, revised Feb 2024.
    6. Mochon, A. & Saez, Y. & Gomez-Barroso, J.L. & Isasi, P., 2012. "Exploring pricing rules in combinatorial sealed-bid auctions," Journal of Economic Behavior & Organization, Elsevier, vol. 82(2), pages 462-478.
    7. Committee, Nobel Prize, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.
    8. Kemal Guler & Martin Bichler & Ioannis Petrakis, 2016. "Ascending Combinatorial Auctions with Risk Averse Bidders," Group Decision and Negotiation, Springer, vol. 25(3), pages 609-639, May.
    9. Lawrence M. Ausubel & Oleg Baranov, 2020. "Core-selecting auctions with incomplete information," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(1), pages 251-273, March.
    10. Paul Karaenke & Martin Bichler & Stefan Minner, 2019. "Coordination Is Hard: Electronic Auction Mechanisms for Increased Efficiency in Transportation Logistics," Management Science, INFORMS, vol. 65(12), pages 5884-5900, December.
    11. Marszalec, Daniel, 2018. "Fear not the simplicity - An experimental analysis of auctions for complements," Journal of Economic Behavior & Organization, Elsevier, vol. 152(C), pages 81-97.
    12. Vohra, Rakesh V., 2015. "Combinatorial Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    13. , K. & ,, 2016. "On the impossibility of core-selecting auctions," Theoretical Economics, Econometric Society, vol. 11(1), January.
    14. Isa Hafalir & Hadi Yektaş, 2015. "Core deviation minimizing auctions," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(2), pages 367-376, May.
    15. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    16. Ryuji Sano, 2015. "Improving Efficiency Using Reserve Prices: An Equilibrium Analysis of Core-Selecting Auctions," KIER Working Papers 926, Kyoto University, Institute of Economic Research.
    17. Siddharth Prasad & Maria-Florina Balcan & Tuomas Sandholm, 2025. "Revenue-Optimal Efficient Mechanism Design with General Type Spaces," Papers 2505.13687, arXiv.org.
    18. 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.
    19. Jonathan Levin & Andrzej Skrzypacz, 2016. "Properties of the Combinatorial Clock Auction," American Economic Review, American Economic Association, vol. 106(9), pages 2528-2551, September.
    20. Aytek Erdil & Paul Klemperer, 2010. "A New Payment Rule for Core-Selecting Package Auctions," Journal of the European Economic Association, MIT Press, vol. 8(2-3), pages 537-547, 04-05.

    More about this item

    Statistics

    Access and download statistics

    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:arx:papers:2505.13680. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.