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

Bicriteria Multidimensional Mechanism Design with Side Information

Author

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

Abstract

We develop a versatile methodology for multidimensional mechanism design that incorporates side information about agents to generate high welfare and high revenue simultaneously. Side information sources include advice from domain experts, predictions from machine learning models, and even the mechanism designer's gut instinct. We design a tunable mechanism that integrates side information with an improved VCG-like mechanism based on weakest types, which are agent types that generate the least welfare. We show that our mechanism, when carefully tuned, generates welfare and revenue competitive with the prior-free total social surplus, and its performance decays gracefully as the side information quality decreases. We consider a number of side information formats including distribution-free predictions, predictions that express uncertainty, agent types constrained to low-dimensional subspaces of the ambient type space, and the traditional setting with known priors over agent types. In each setting we design mechanisms based on weakest types and prove performance guarantees.

Suggested Citation

  • Maria-Florina Balcan & Siddharth Prasad & Tuomas Sandholm, 2023. "Bicriteria Multidimensional Mechanism Design with Side Information," Papers 2302.14234, arXiv.org, revised Oct 2024.
  • Handle: RePEc:arx:papers:2302.14234
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Hal R. Varian & Christopher Harris, 2014. "The VCG Auction in Theory and Practice," American Economic Review, American Economic Association, vol. 104(5), pages 442-445, May.
    2. 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.
    3. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    4. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    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. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    7. Tuomas Sandholm & Anton Likhodedov, 2015. "Automated Design of Revenue-Maximizing Combinatorial Auctions," Operations Research, INFORMS, vol. 63(5), pages 1000-1025, October.
    8. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    9. Alexey Malakhov & Rakesh Vohra, 2009. "An optimal auction for capacity constrained bidders: a network perspective," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 39(1), pages 113-128, April.
    10. Pai, Mallesh M. & Vohra, Rakesh, 2014. "Optimal auctions with financially constrained buyers," Journal of Economic Theory, Elsevier, vol. 150(C), pages 383-425.
    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. Alexander Teytelboym & Shengwu Li & Scott Duke Kominers & Mohammad Akbarpour & Piotr Dworczak, 2021. "Discovering Auctions: Contributions of Paul Milgrom and Robert Wilson," Scandinavian Journal of Economics, Wiley Blackwell, vol. 123(3), pages 709-750, July.
    2. Kazumura, Tomoya & Mishra, Debasis & Serizawa, Shigehiro, 2020. "Mechanism design without quasilinearity," Theoretical Economics, Econometric Society, vol. 15(2), May.
    3. 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.
    4. Committee, Nobel Prize, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.
    5. 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.
    6. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    7. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object allocation: Ex-post revenue maximization with no wastage," Working Papers e116, Tokyo Center for Economic Research.
    8. Frank Kelly & Peter Key & Neil Walton, 2016. "Efficient Advert Assignment," Operations Research, INFORMS, vol. 64(4), pages 822-837, August.
    9. Philippe Jehiel & Laurent Lamy, 2018. "A Mechanism Design Approach to the Tiebout Hypothesis," Journal of Political Economy, University of Chicago Press, vol. 126(2), pages 735-760.
    10. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    11. Lawrence M. Ausubel & Paul Milgrom, 2004. "Ascending Proxy Auctions," Discussion Papers 03-035, Stanford Institute for Economic Policy Research.
    12. Jehiel, Philippe & Meyer-ter-Vehn, Moritz & Moldovanu, Benny, 2007. "Mixed bundling auctions," Journal of Economic Theory, Elsevier, vol. 134(1), pages 494-512, May.
    13. Satoru Fujishige & Zaifu Yang, 2020. "A Universal Dynamic Auction for Unimodular Demand Types: An Efficient Auction Design for Various Kinds of Indivisible Commodities," Discussion Papers 20/08, Department of Economics, University of York.
    14. Michael Ostrovsky & Michael Schwarz, 2023. "Reserve Prices in Internet Advertising Auctions: A Field Experiment," Journal of Political Economy, University of Chicago Press, vol. 131(12), pages 3352-3376.
    15. Tomoya Kazumura & Debasis Mishra & Shigehiro Serizawa, 2017. "Strategy-proof multi-object auction design: Ex-post revenue maximization with no wastage," ISER Discussion Paper 1001, Institute of Social and Economic Research, Osaka University.
    16. Dütting, Paul & Fischer, Felix & Parkes, David C., 2019. "Expressiveness and robustness of first-price position auctions," LSE Research Online Documents on Economics 85877, London School of Economics and Political Science, LSE Library.
    17. Núñez, Marina & Rafels, Carlos & Robles, Francisco, 2020. "A mechanism for package allocation problems with gross substitutes," Journal of Mathematical Economics, Elsevier, vol. 87(C), pages 6-14.
    18. Patrick Hummel, 2018. "Hybrid mechanisms for Vickrey–Clarke–Groves and generalized second-price bids," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(1), pages 331-350, March.
    19. Yu Ning & Su Xiu Xu & George Q. Huang & Xudong Lin, 2021. "Optimal digital product auctions with unlimited supply and rebidding behavior," Annals of Operations Research, Springer, vol. 307(1), pages 399-416, December.
    20. Seiji Takanashi & Takehiro Kawasaki & Taiki Todo & Makoto Yokoo, 2019. "Efficiency in Truthful Auctions via a Social Network," Papers 1904.12422, arXiv.org.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

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