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

Revenue-Optimal Efficient Mechanism Design with General Type Spaces

Author

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

Abstract

We derive the revenue-optimal efficient (welfare-maximizing) mechanism in a general multidimensional mechanism design setting when type spaces -- that is, the underlying domains from which agents' values come from -- can capture arbitrarily complex informational constraints about the agents. Type spaces can encode information about agents representing, for example, machine learning predictions of agent behavior, institutional knowledge about feasible market outcomes (such as item substitutability or complementarity in auctions), and correlations between multiple agents. Prior work has only dealt with connected type spaces, which are not expressive enough to capture many natural kinds of constraints such as disjunctive constraints. We provide two characterizations of the optimal mechanism based on allocations and connected components; both make use of an underlying network flow structure to the mechanism design. Our results significantly generalize and improve the prior state of the art in revenue-optimal efficient mechanism design. They also considerably expand the scope of what forms of agent information can be expressed and used to improve revenue.

Suggested Citation

  • Siddharth Prasad & Maria-Florina Balcan & Tuomas Sandholm, 2025. "Revenue-Optimal Efficient Mechanism Design with General Type Spaces," Papers 2505.13687, arXiv.org.
    • Handle: RePEc:arx:papers:2505.13687
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. 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.
    2. Fajemisin, Adejuyigbe O. & Maragno, Donato & den Hertog, Dick, 2024. "Optimization with constraint learning: A framework and survey," European Journal of Operational Research, Elsevier, vol. 314(1), pages 1-14.
    3. Tuomas Sandholm & Anton Likhodedov, 2015. "Automated Design of Revenue-Maximizing Combinatorial Auctions," Operations Research, INFORMS, vol. 63(5), pages 1000-1025, October.
    4. Paulo Monteiro, 2009. "Abstract types and distributions in independent private value auctions," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 40(3), pages 497-507, September.
    5. Benjamin Edelman & Michael Ostrovsky & Michael Schwarz, 2007. "Internet Advertising and the Generalized Second-Price Auction: Selling Billions of Dollars Worth of Keywords," American Economic Review, American Economic Association, vol. 97(1), pages 242-259, March.
    6. Bajari, Patrick & Yeo, Jungwon, 2009. "Auction design and tacit collusion in FCC spectrum auctions," Information Economics and Policy, Elsevier, vol. 21(2), pages 90-100, June.
    7. Green, Jerry & Laffont, Jean-Jacques, 1977. "Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public Goods," Econometrica, Econometric Society, vol. 45(2), pages 427-438, March.
    8. 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.
    9. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    10. Manelli, Alejandro M. & Vincent, Daniel R., 2006. "Bundling as an optimal selling mechanism for a multiple-good monopolist," Journal of Economic Theory, Elsevier, vol. 127(1), pages 1-35, March.
    11. Myerson, Roger B. & Satterthwaite, Mark A., 1983. "Efficient mechanisms for bilateral trading," Journal of Economic Theory, Elsevier, vol. 29(2), pages 265-281, April.
    12. William S. Lovejoy, 2006. "Optimal Mechanisms with Finite Agent Types," Management Science, INFORMS, vol. 52(5), pages 788-803, May.
    13. Holmstrom, Bengt, 1979. "Groves' Scheme on Restricted Domains," Econometrica, Econometric Society, vol. 47(5), pages 1137-1144, September.
    14. Skreta, Vasiliki, 2006. "Mechanism design for arbitrary type spaces," Economics Letters, Elsevier, vol. 91(2), pages 293-299, May.
    15. 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.
    16. Maria-Florina Balcan & Tuomas Sandholm & Ellen Vitercik, 2025. "Generalization Guarantees for Multi-Item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms," Operations Research, INFORMS, vol. 73(2), pages 648-663, March.
    17. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    18. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, 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. 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.
    2. Marek Pycia & Peter Troyan, 2023. "A Theory of Simplicity in Games and Mechanism Design," Econometrica, Econometric Society, vol. 91(4), pages 1495-1526, July.
    3. Jehiel, Philippe & Meyer-ter-Vehn, Moritz & Moldovanu, Benny, 2007. "Mixed bundling auctions," Journal of Economic Theory, Elsevier, vol. 134(1), pages 494-512, May.
    4. Siddharth Prasad & Maria-Florina Balcan & Tuomas Sandholm, 2025. "Weakest Bidder Types and New Core-Selecting Combinatorial Auctions," Papers 2505.13680, arXiv.org.
    5. Maria-Florina Balcan & Siddharth Prasad & Tuomas Sandholm, 2023. "Bicriteria Multidimensional Mechanism Design with Side Information," Papers 2302.14234, arXiv.org, revised Oct 2024.
    6. Committee, Nobel Prize, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.
    7. 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.
    8. Seiji Takanashi & Takehiro Kawasaki & Taiki Todo & Makoto Yokoo, 2019. "Efficiency in Truthful Auctions via a Social Network," Papers 1904.12422, arXiv.org.
    9. Simon Loertscher & Leslie M. Marx, 2022. "To sell public or private goods," Review of Economic Design, Springer;Society for Economic Design, vol. 26(3), pages 385-415, September.
    10. Guo, Mingyu & Conitzer, Vincent, 2009. "Worst-case optimal redistribution of VCG payments in multi-unit auctions," Games and Economic Behavior, Elsevier, vol. 67(1), pages 69-98, September.
    11. Vijay Krishna & Motty Perry, 1997. "Efficient Mechanism Design," Game Theory and Information 9703010, University Library of Munich, Germany, revised 28 Apr 1998.
    12. Josheski Dushko & Karamazova Elena, 2021. "Auction theory and a note on game mechanisms," Croatian Review of Economic, Business and Social Statistics, Sciendo, vol. 7(1), pages 43-59, May.
    13. Delacrétaz, David & Loertscher, Simon & Marx, Leslie M. & Wilkening, Tom, 2019. "Two-sided allocation problems, decomposability, and the impossibility of efficient trade," Journal of Economic Theory, Elsevier, vol. 179(C), pages 416-454.
    14. Tim Roughgarden & Inbal Talgam-Cohen & Qiqi Yan, 2019. "Robust Auctions for Revenue via Enhanced Competition," Operations Research, INFORMS, vol. 68(4), pages 1074-1094, July.
    15. Michael H. Rothkopf, 2007. "Decision Analysis: The Right Tool for Auctions," Decision Analysis, INFORMS, vol. 4(3), pages 167-172, September.
    16. Yi, Jianxin & Li, Yong, 2016. "A general impossibility theorem and its application to individual rights," Mathematical Social Sciences, Elsevier, vol. 81(C), pages 79-86.
    17. Dilip Mookherjee, 2008. "The 2007 Nobel Memorial Prize in Mechanism Design Theory," Scandinavian Journal of Economics, Wiley Blackwell, vol. 110(2), pages 237-260, June.
    18. Jiayin Liu & Chenglong Zhang, 2025. "Deep Learning for Double Auction," Papers 2504.05355, arXiv.org.
    19. Simon Loertscher & Leslie M. Marx, 2022. "Incomplete Information Bargaining with Applications to Mergers, Investment, and Vertical Integration," American Economic Review, American Economic Association, vol. 112(2), pages 616-649, February.
    20. Eric Maskin, 2004. "The Unity of Auction Theory: Paul Milgrom's Masterclass," Economics Working Papers 0044, Institute for Advanced Study, School of Social Science.

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