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

Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for all Distributions

Author

Listed:
  • Meryem Essaidi
  • Matheus V. X. Ferreira
  • S. Matthew Weinberg

Abstract

We consider a revenue-maximizing seller with a single item for sale to multiple buyers with i.i.d. valuations. Akbarpour and Li (2020) show that the only optimal, credible, strategyproof auction is the ascending price auction with reserves which has unbounded communication complexity. Recent work of Ferreira and Weinberg (2020) circumvents their impossibility result assuming the existence of cryptographically secure commitment schemes, and designs a two-round credible, strategyproof, optimal auction. However, their auction is only credible when buyers' valuations are MHR or $\alpha$-strongly regular: they show their auction might not be credible even when there is a single buyer drawn from a non-MHR distribution. In this work, under the same cryptographic assumptions, we identify a new single-item auction that is credible, strategyproof, revenue optimal, and terminates in constant rounds in expectation for all distributions with finite monopoly price.

Suggested Citation

  • Meryem Essaidi & Matheus V. X. Ferreira & S. Matthew Weinberg, 2022. "Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for all Distributions," Papers 2205.14758, arXiv.org.
    • Handle: RePEc:arx:papers:2205.14758
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Tim Roughgarden, 2021. "Transaction Fee Mechanism Design," Papers 2106.01340, arXiv.org, revised Dec 2023.
    2. Matheus V. X. Ferreira & Daniel J. Moroz & David C. Parkes & Mitchell Stern, 2021. "Dynamic Posted-Price Mechanisms for the Blockchain Transaction Fee Market," Papers 2103.14144, arXiv.org, revised Nov 2021.
    3. Qingmin Liu & Konrad Mierendorff & Xianwen Shi & Weijie Zhong, 2019. "Auctions with Limited Commitment," American Economic Review, American Economic Association, vol. 109(3), pages 876-910, March.
    4. Mohammad Akbarpour & Shengwu Li, 2020. "Credible Auctions: A Trilemma," Econometrica, Econometric Society, vol. 88(2), pages 425-467, March.
    5. Shengwu Li, 2017. "Obviously Strategy-Proof Mechanisms," American Economic Review, American Economic Association, vol. 107(11), pages 3257-3287, November.
    6. Matheus V. X. Ferreira & S. Matthew Weinberg, 2020. "Credible, Truthful, and Two-Round (Optimal) Auctions via Cryptographic Commitments," Papers 2004.01598, arXiv.org, revised May 2020.
    7. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    8. Matheus V. X. Ferreira & S. Matthew Weinberg, 2021. "Proof-of-Stake Mining Games with Perfect Randomness," Papers 2107.04069, arXiv.org, revised Dec 2021.
    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. Matheus V. X. Ferreira & David C. Parkes, 2022. "Credible Decentralized Exchange Design via Verifiable Sequencing Rules," Papers 2209.15569, arXiv.org, revised Apr 2023.
    2. Maryam Bahrani & Pranav Garimidi & Tim Roughgarden, 2023. "Transaction Fee Mechanism Design with Active Block Producers," Papers 2307.01686, arXiv.org, revised Oct 2023.

    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. Matheus V. X. Ferreira & David C. Parkes, 2022. "Credible Decentralized Exchange Design via Verifiable Sequencing Rules," Papers 2209.15569, arXiv.org, revised Apr 2023.
    2. Hao Chung & Elaine Shi, 2021. "Foundations of Transaction Fee Mechanism Design," Papers 2111.03151, arXiv.org, revised Nov 2022.
    3. Maryam Bahrani & Pranav Garimidi & Tim Roughgarden, 2023. "Transaction Fee Mechanism Design with Active Block Producers," Papers 2307.01686, arXiv.org, revised Oct 2023.
    4. Loertscher, Simon & Marx, Leslie M., 2020. "Asymptotically optimal prior-free clock auctions," Journal of Economic Theory, Elsevier, vol. 187(C).
    5. Aranyak Mehta & Andres Perlroth, 2023. "Auctions without commitment in the auto-bidding world," Papers 2301.07312, arXiv.org, revised Mar 2023.
    6. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    7. Pablo Guillen & Róbert F. Veszteg, 2021. "Strategy-proofness in experimental matching markets," Experimental Economics, Springer;Economic Science Association, vol. 24(2), pages 650-668, June.
    8. Loertscher, Simon & Mezzetti, Claudio, 2021. "A dominant strategy, double clock auction with estimation-based tatonnement," Theoretical Economics, Econometric Society, vol. 16(3), July.
    9. Kevin Leyton-Brown & Paul Milgrom & Neil Newman & Ilya Segal, 2023. "Artificial Intelligence and Market Design: Lessons Learned from Radio Spectrum Reallocation," NBER Chapters, in: New Directions in Market Design, National Bureau of Economic Research, Inc.
    10. Sander Onderstal & Yang Yang, 2020. "Cheap-talk Communication in Procurement Auctions: Theory and Experiment," Tinbergen Institute Discussion Papers 20-013/VII, Tinbergen Institute.
    11. Luyao Zhang & Fan Zhang, 2023. "Understand Waiting Time in Transaction Fee Mechanism: An Interdisciplinary Perspective," Papers 2305.02552, arXiv.org.
    12. Matheus V. X. Ferreira & S. Matthew Weinberg, 2020. "Credible, Truthful, and Two-Round (Optimal) Auctions via Cryptographic Commitments," Papers 2004.01598, arXiv.org, revised May 2020.
    13. Ryuji Sano, 2021. "Dynamic communication mechanism design," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(1), pages 163-180, July.
    14. Sylvain Chassang & Lucia Del Carpio & Samuel Kapon, 2022. "Using Divide and Conquer to Improve Tax Collection: Theory and Laboratory Evidence," Working Papers 299, Princeton University, Department of Economics, Center for Economic Policy Studies..
    15. Burguet, Roberto & Sákovics, József, 2019. "Personalized prices and uncertainty in monopsony," International Journal of Industrial Organization, Elsevier, vol. 67(C).
    16. Yannai A. Gonczarowski & Ori Heffetz & Clayton Thomas, 2022. "Strategyproofness-Exposing Mechanism Descriptions," Papers 2209.13148, arXiv.org, revised Jul 2023.
    17. 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.
    18. Jarman, Felix & Meisner, Vincent, 2017. "Ex-post optimal knapsack procurement," Journal of Economic Theory, Elsevier, vol. 171(C), pages 35-63.
    19. Jason Milionis & Dean Hirsch & Andy Arditi & Pranav Garimidi, 2022. "A Framework for Single-Item NFT Auction Mechanism Design," Papers 2209.11293, arXiv.org.
    20. Matheus V. X. Ferreira & Daniel J. Moroz & David C. Parkes & Mitchell Stern, 2021. "Dynamic Posted-Price Mechanisms for the Blockchain Transaction Fee Market," Papers 2103.14144, arXiv.org, revised Nov 2021.

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