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

Greedy Transaction Fee Mechanisms for (Non-)myopic Miners

Author

Listed:
  • Yotam Gafni
  • Aviv Yaish

Abstract

Decentralized cryptocurrencies are payment systems that rely on aligning the incentives of users and miners to operate correctly and offer a high quality of service to users. Recent literature studies the mechanism design problem of the auction serving as a cryptocurrency's transaction fee mechanism (TFM). We present a general framework that captures both myopic and non-myopic settings, as well as different possible strategic models for users. Within this general framework, when restricted to the myopic case, we show that while the mechanism that requires a user to "pay-as-bid", and greedily chooses among available transactions based on their fees, is not dominant strategy incentive-compatible for users, it has a Bayesian-Nash equilibrium where bids are slightly shaded. Relaxing this incentive compatibility requirement circumvents the impossibility results proven by previous works, and allows for an approximately revenue and welfare optimal, myopic miner incentive-compatible (MMIC), and off-chain-agreement (OCA)-proof mechanism. We prove these guarantees using different benchmarks, and show that the pay-as-bid greedy auction is the revenue optimal Bayesian incentive-compatible, MMIC and 1-OCA-proof mechanism among a large class of mechanisms. We move beyond the myopic setting explored in the literature, to one where users offer transaction fees for their transaction to be accepted, as well as report their urgency level by specifying the time to live of the transaction, after which it expires. We analyze pay-as-bid mechanisms in this setting, and show the competitive ratio guarantees provided by the greedy allocation rule. We then present a better-performing non-myopic rule, and analyze its competitive ratio. The above analysis is stated in terms of a cryptocurrency TFM, but applies to other settings, such as cloud computing and decentralized "gig" economy, as well.

Suggested Citation

  • Yotam Gafni & Aviv Yaish, 2022. "Greedy Transaction Fee Mechanisms for (Non-)myopic Miners," Papers 2210.07793, arXiv.org, revised Feb 2024.
  • Handle: RePEc:arx:papers:2210.07793
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Schilling, Linda & Uhlig, Harald, 2019. "Some simple bitcoin economics," Journal of Monetary Economics, Elsevier, vol. 106(C), pages 16-26.
    2. Tim Roughgarden, 2020. "Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559," Papers 2012.00854, arXiv.org.
    3. Brenner, Menachem & Galai, Dan & Sade, Orly, 2009. "Sovereign debt auctions: Uniform or discriminatory?," Journal of Monetary Economics, Elsevier, vol. 56(2), pages 267-274, March.
    4. Michel Rauchs & Garrick Hileman, 2017. "Global Cryptocurrency Benchmarking Study," Cambridge Centre for Alternative Finance Reports 201704-gcbs, Cambridge Centre for Alternative Finance, Cambridge Judge Business School, University of Cambridge.
    5. Tim Roughgarden, 2021. "Transaction Fee Mechanism Design," Papers 2106.01340, arXiv.org, revised Dec 2023.
    6. Bulow, Jeremy & Klemperer, Paul, 1996. "Auctions versus Negotiations," American Economic Review, American Economic Association, vol. 86(1), pages 180-194, March.
    7. Julien Prat & Benjamin Walter, 2021. "An Equilibrium Model of the Market for Bitcoin Mining," Journal of Political Economy, University of Chicago Press, vol. 129(8), pages 2415-2452.
    8. Federico, Giulio & Rahman, David, 2003. "Bidding in an Electricity Pay-as-Bid Auction," Journal of Regulatory Economics, Springer, vol. 24(2), pages 175-211, September.
    9. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    10. Yuan Deng & Jieming Mao & Balasubramanian Sivan & Kangning Wang, 2021. "Optimal Pricing Schemes for an Impatient Buyer," Papers 2106.02149, arXiv.org, revised Feb 2023.
    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. Pycia, Marek & Woodward, Kyle, 2021. "Auctions of Homogeneous Goods: A Case for Pay-as-Bid," CEPR Discussion Papers 15656, C.E.P.R. Discussion Papers.
    2. Andrea Canidio, 2023. "Auctions with Tokens: Monetary Policy as a Mechanism Design Choice," Papers 2301.13794, arXiv.org, revised Aug 2023.
    3. Yuxuan Lu & Qian Qi & Xi Chen, 2023. "A Framework of Transaction Packaging in High-throughput Blockchains," Papers 2301.10944, arXiv.org.
    4. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press, vol. 33(4), pages 541-571.
    5. Schmitz, Patrick W., 2003. "On second-price auctions and imperfect competition," Journal of Mathematical Economics, Elsevier, vol. 39(8), pages 901-909, November.
    6. Yuen Leng Chow & Isa E. Hafalir & Abdullah Yavas, 2015. "Auction versus Negotiated Sale: Evidence from Real Estate Sales," Real Estate Economics, American Real Estate and Urban Economics Association, vol. 43(2), pages 432-470, June.
    7. Walter Beckert, 2004. "Dynamic Monopolies with Stochastic Demand," Birkbeck Working Papers in Economics and Finance 0404, Birkbeck, Department of Economics, Mathematics & Statistics.
    8. Jehiel, Philippe & Lamy, Laurent, 2014. "On discrimination in procurement auctions," CEPR Discussion Papers 9790, C.E.P.R. Discussion Papers.
    9. Dominic Coey & Bradley Larsen & Kane Sweeney, 2019. "The bidder exclusion effect," RAND Journal of Economics, RAND Corporation, vol. 50(1), pages 93-120, March.
    10. Jason Shachat & Lijia Tan, 2015. "An Experimental Investigation of Auctions and Bargaining in Procurement," Management Science, INFORMS, vol. 61(5), pages 1036-1051, May.
    11. 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.
    12. Ronald M. Harstad, 2007. "Does a Seller Really Want Another Bidder?," Working Papers 0711, Department of Economics, University of Missouri.
    13. Yongmin Chen & Ruqu Wang, 2004. "Equilibrium Selling Mechanisms," Annals of Economics and Finance, Society for AEF, vol. 5(2), pages 335-355, November.
    14. Jeremy Bulow & Paul Klemperer, 2007. "When are Auctions Best?," Economics Papers 2007-W03, Economics Group, Nuffield College, University of Oxford.
    15. Philippe Jehiel & Laurent Lamy, 2020. "On the Benefits of Set-Asides," Journal of the European Economic Association, European Economic Association, vol. 18(4), pages 1655-1696.
    16. Syngjoo Choi & Lars Nesheim & Imran Rasul, 2016. "Reserve Price Effects In Auctions: Estimates From Multiple Regression-Discontinuity Designs," Economic Inquiry, Western Economic Association International, vol. 54(1), pages 294-314, January.
    17. Stephanie Rosenkranz & Patrick W. Schmitz, 2007. "Reserve Prices in Auctions as Reference Points," Economic Journal, Royal Economic Society, vol. 117(520), pages 637-653, April.
    18. Chawla, Shuchi & Hartline, Jason D. & Sivan, Balasubramanian, 2019. "Optimal crowdsourcing contests," Games and Economic Behavior, Elsevier, vol. 113(C), pages 80-96.
    19. Sven-Olof Fridolfsson and Thomas P. Tangeras, 2015. "Nuclear Capacity Auctions," The Energy Journal, International Association for Energy Economics, vol. 0(Number 3).
    20. Sander Onderstal & Yang Yang, 2020. "Cheap-talk Communication in Procurement Auctions: Theory and Experiment," Tinbergen Institute Discussion Papers 20-013/VII, Tinbergen Institute.

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