Table of Links
-
Understanding OCA
B. Non-anonymous Deterministic Mechanisms
6 Discussion
Our characterization of DSIC+1-OCA-proof and MMIC+1-OCA-proof mechanisms extends known incidental results in the literature. For example, Table 1 in [Rou21] notes that the first price auction is MMIC+1-OCA-proof, the second-price auction is DSIC+1-OCA-proof, and that EIP-1559 (which is essentially a first-price auction with a dynamically adjusted burned reserve price) is MMIC+1-OCA-proof. Our characterization confirms these results, but also precisely extends them: In essence, it shows that all MMIC+1-OCA-proof are “EIP-1559 - type” mechanisms, in the sense of having a threshold bid r and a constant burn, albeit with the freedom to choose any monotone payment function and not necessarily first-price payments. Similarly, for DSIC+1- OCA-proof mechanisms, any second-price auction with a constant burn is possible. These results are made more important by our impossibility result (Theorem 4.7), since if all requirements cannot be satisfied at once, satisfying at least two of the three may be a good compromise.
Throughout the work, we analyze anonymous mechanisms. While this is a common assumption in the literature, we wish to explore how much it affects the impossibility result of Theorem 4.7. In Appendix B, we remove this restriction and develop a characterization of all, not necessarily anonymous, DSIC+MMIC+1-OCA-proof mechanisms. We find that non-anonymous mechanisms that satisfy these desired properties are very restricted: all of them must have some constant unique bidder (among all possible named bidders) that can be allocated the item, where the auction follows the form of a burned posted-price auction. This limitation is reminiscent of the “2-user-friendly” impossibility in Theorem 6.1 of [CS23].
References
[AGHH23] Sarah Azouvi, Guy Goren, Lioba Heimbach, and Alexander Hicks. “Base Fee Manipulation In Ethereum’s EIP-1559 Transaction Fee Mechanism”. en. In: (Apr. 2023). doi: 10.4230/LIPICS.DISC.2023.11. eprint: 2304.11478.
[AM02] Lawrence M Ausubel and Paul R Milgrom. “Ascending Auctions with Package Bidding”. In: The B.E. Journal of Theoretical Economics 1.1 (Aug. 2002). issn: 2194-6124. doi: 10.2202/1534-5963.1019.
[AR20] Musab A. Alturki and Grigore Roşu. “Statistical Model Checking of RANDAO’s Resilience to Pre-computed Reveal Strategies”. In: Formal Methods. FM 2019 International Workshops. Springer International Publishing, 2020, pp. 337–349. isbn: 9783030549947. doi: 10.1007/978-3-030-54994-7_25.
[Bac10] Yoram Bachrach. “Honor among Thieves: Collusion in Multi-Unit Auctions”. In: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1 - Volume 1. AAMAS ’10. Toronto, Canada: International Foundation for Autonomous Agents and Multiagent Systems, 2010, pp. 617–624. isbn: 9780982657119.
[BEOS23] Soumya Basu, David Easley, Maureen O’Hara, and Emin Gün Sirer. “StableFees: A Predictable Fee Market for Cryptocurrencies”. In: Management Science 69.11 (Nov. 2023), pp. 6508–6524. issn: 1526-5501. doi: 10.1287/ mnsc.2023.4735.
[BGB17] Benedikt Bünz, Steven Goldfeder, and Joseph Bonneau. Proofs-of-delay and randomness beacons in ethereum. 2017.
[BGR23a] Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden. Transaction Fee Mechanism Design with Active Block Producers. July 2023. doi: 10. 48550/ARXIV.2307.01686. arXiv: 2307.01686 [cs.GT].
[BGR23b] Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden. “When Bidders Are DAOs”. en. In: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi: 10.4230/LIPICS.AFT.2023.21. url: https://doi.org/10. 4230/LIPIcs.AFT.2023.21.
[CK09] Yeon-Koo Che and Jinwoo Kim. “Optimal collusion-proof auctions”. In: Journal of Economic Theory 144.2 (2009), pp. 565–603. issn: 0022-0531. doi: https://doi.org/10.1016/j.jet.2008.07.004. url: https://www.sciencedirect.com/science/article/pii/S0022053108001270.
[CMB23] K. Choi, A. Manoj, and J. Bonneau. “SoK: Distributed Randomness Beacons”. In: 2023 IEEE Symposium on Security and Privacy (SP). Los Alamitos, CA, USA: IEEE Computer Society, May 2023, pp. 75–92. doi: 10 . 1109/SP46215.2023.00192. url: https://doi.ieeecomputersociety. org/10.1109/SP46215.2023.00192.
[CS23] Hao Chung and Elaine Shi. “Foundations of Transaction Fee Mechanism Design”. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2023, pp. 3856–3899. doi: 10.1137/1.9781611977554.ch150. url: https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch150.
[CSZZ23] Xi Chen, David Simchi-Levi, Zishuo Zhao, and Yuan Zhou. Bayesian Mechanism Design for Blockchain Transaction Fee Allocation. 2023. arXiv: 2209. 13099 [cs.GT].
[DD13] Shahar Dobzinski and Shaddin Dughmi. “On the Power of Randomization in Algorithmic Mechanism Design”. In: SIAM Journal on Computing 42.6 (2013), pp. 2287–2304. doi: 10.1137/090780146. eprint: https://doi. org/10.1137/090780146. url: https://doi.org/10.1137/090780146.
[DM17] Alan Deckelbaum and Silvio Micali. “Collusion, efficiency, and dominant strategies”. In: Games and Economic Behavior 103 (2017). John Nash Memorial, pp. 83–93. issn: 0899-8256. doi: https://doi.org/10.1016/j.geb. 2016.03.008. url: https://www.sciencedirect.com/science/article/ pii/S0899825616300136.
[DPG24] Sankarshan Damle, Manisha Padala, and Sujit Gujar. Designing Redistribution Mechanisms for Reducing Transaction Fees in Blockchains. Jan. 2024. doi: 10.48550/ARXIV.2401.13262. arXiv: 2401.13262 [cs.GT].
[Edg23] Ben Edgington. Upgrading Ethereum | 2.9.2 Randomness. Sept. 2023. url: https://web.archive.org/web/20240204094612/https://eth2book. info/capella/part2/building_blocks/randomness/.
[ES04] Péter Eső and James Schummer. “Bribing and signaling in second price auctions”. In: Games and Economic Behavior 47.2 (2004), pp. 299–324. issn: 0899-8256. doi: https://doi.org/10.1016/j.geb.2003.06.005. url: https://www.sciencedirect.com/science/article/pii/S0899825603001878.
[FMPS21] Matheus V. X. Ferreira, Daniel J. Moroz, David C. Parkes, and Mitchell Stern. “Dynamic Posted-Price Mechanisms for the Blockchain TransactionFee Market”. In: Proceedings of the 3rd ACM Conference on Advances in Financial Technologies. AFT ’21. Arlington, Virginia: Association for Computing Machinery, 2021, pp. 86–99. isbn: 9781450390828. doi: 10.1145/ 3479722.3480991. url: https://arxiv.org/pdf/2103.14144.pdf.
[FPR23] Elijah Fox, Mallesh Pai, and Max Resnick. Censorship Resistance in OnChain Auctions. 2023. arXiv: 2301.13321 [econ.TH].
[GH05] Andrew V. Goldberg and Jason D. Hartline. “Collusion-Resistant Mechanisms for Single-Parameter Agents”. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’05. Vancouver, British Columbia: Society for Industrial and Applied Mathematics, 2005, pp. 620–629. isbn: 0898715857.
[GHKSW06] Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks, and Andrew Wright. “Competitive auctions”. In: Games and Economic Behavior 55.2 (2006). Mini Special Issue: Electronic Market Design, pp. 242–269. issn: 0899-8256. doi: https://doi.org/10.1016/j.geb.2006.02.003. url: https://www.sciencedirect.com/science/article/pii/S0899825606000303.
[GL16] Jacob K. Goeree and Yuanchuan Lien. “On the impossibility of core-selecting auctions”. In: Theoretical Economics 11.1 (2016), pp. 41–52. doi: https://doi.org/10.3982/TE1198. eprint: https://onlinelibrary.wiley.com/doi/pdf/10.3982/TE1198. url: https://onlinelibrary.wiley.com/doi/abs/10.3982/TE1198.
[GL79] Jerry Green and Jean-Jacques Laffont. “On Coalition Incentive Compatibility”. In: The Review of Economic Studies 46.2 (1979), pp. 243–254. issn: 00346527, 1467937X. url: http://www.jstor.org/stable/2297048 (visited on 01/06/2024).
[GY23] Yotam Gafni and Aviv Yaish. Greedy Transaction Fee Mechanisms for (Non- )myopic Miners. 2023. arXiv: 2210.07793 [cs.GT]. [Har06] Jason Hartline. “Lectures on optimal mechanism design”. In: Lecture notes (2006).
[HP23] Jens Leth Hougaard and Mohsen Pourpouneh. “Farsighted Miners under Transaction Fee Mechanism EIP1559”. In: 2023 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). IEEE, May 2023. doi: 10.1109/icbc56567.2023.10174974. url: https://doi.org/10.1109/ ICBC56567.2023.10174974.
[KKLP23] Aggelos Kiayias, Elias Koutsoupias, Philip Lazos, and Giorgos Panagiotakos. Tiered Mechanisms for Blockchain Transaction Fees. Apr. 2023. doi: 10.48550/ARXIV.2304.06014. arXiv: 2304.06014 [cs.GT].
[LLNZZZ22] Yulin Liu, Yuxuan Lu, Kartik Nayak, Fan Zhang, Luyao Zhang, and Yinhong Zhao. “Empirical Analysis of EIP-1559: Transaction Fees, Waiting Times, and Consensus Security”. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. CCS ’22. Los Angeles, CA, USA: Association for Computing Machinery, 2022, pp. 2099– 2113. isbn: 9781450394505. doi: 10.1145/3548606.3559341. url: https://doi.org/10.1145/3548606.3559341.
[LMN03] R. Lavi, Ahuva Mu’alem, and N. Nisan. “Towards a characterization of truthful combinatorial auctions”. In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. 2003, pp. 574–583. doi: 10.1109/SFCS.2003.1238230.
[LRMP23] Stefanos Leonardos, Daniël Reijsbergen, Barnabé Monnot, and Georgios Piliouras. “Optimality Despite Chaos in Fee Markets”. In: Lecture Notes in Computer Science. Springer Nature Switzerland, Dec. 2023, pp. 346–362. isbn: 9783031477515. doi:10.1007/978-3-031-47751-5_20.
[LST00] Kevin Leyton-Brown, Yoav Shoham, and Moshe Tennenholtz. “Bidding Clubs: Institutionalized Collusion in Auctions”. In: Proceedings of the 2nd ACM Conference on Electronic Commerce. EC ’00. Minneapolis, Minnesota, USA: Association for Computing Machinery, 2000, pp. 253–259. isbn: 1581132727. doi: 10.1145/352871.352899. url: https://doi.org/10.1145/352871. 352899.
[LSZ19] Ron Lavi, Or Sattath, and Aviv Zohar. “Redesigning Bitcoin’s Fee Market”. In: The World Wide Web Conference. WWW ’19. San Francisco, CA, USA: Association for Computing Machinery, 2019, pp. 2950–2956. isbn: 9781450366748. doi: 10.1145/3308558.3313454. url: https://doi.org/ 10.1145/3308558.3313454.
[MHAG22] Jason Milionis, Dean Hirsch, Andy Arditi, and Pranav Garimidi. “A Framework for Single-Item NFT Auction Mechanism Design”. In: Proceedings of the 2022 ACM CCS Workshop on Decentralized Finance and Security. CCS ’22. ACM, Nov. 2022. doi: 10.1145/3560832.3563436.
[MM92] R. Preston McAfee and John McMillan. “Bidding Rings”. In: The American Economic Review 82.3 (1992), pp. 579–599. issn: 00028282. url: http : //www.jstor.org/stable/2117323 (visited on 01/06/2024).
[Mye81] Roger B Myerson. “Optimal auction design”. In: Mathematics of operations research 6.1 (1981), pp. 58–73.
[NHJ24] Mohammad Sadegh Nourbakhsh, Feng Hao, and Arshad Jhumka. Transaction Fee Mechanism For Order-Sensitive Blockchain-based Applications. 2024. url: https://www.dcs.warwick.ac.uk/~fenghao/files/CBT_Order_Oriented_TFM.pdf.
[Nis23] Noam Nisan. Serial Monopoly on Blockchains. 2023. url: https://www. cs.huji.ac.il/~noam/publications/ser-mon.pdf.
[NR01] Noam Nisan and Amir Ronen. “Algorithmic Mechanism Design”. In: Games and Economic Behavior 35.1 (2001), pp. 166–196. issn: 0899-8256. doi: https://doi.org/10.1006/game.1999.0790. url: https://www.sciencedirect.com/science/article/pii/S089982569990790X.
[Rac14] Shiran Rachmilevitch. “First-best collusion without communication”. In: Games and Economic Behavior 83 (2014), pp. 224–230. issn: 0899-8256. doi: https://doi.org/10.1016/j.geb.2013.11.007. url: https://www.sciencedirect.com/science/article/pii/S0899825613001607.
[Rac15] Shiran Rachmilevitch. “Bribing in second-price auctions”. In: Games and Economic Behavior 92 (2015), pp. 191–205. issn: 0899-8256. doi: https://doi.org/10.1016/j.geb.2015.06. 008. url: https://www.sciencedirect.com/science/article/pii/S0899825615000962.
[Rou20] Tim Roughgarden. “Transaction Fee Mechanism Design for the Ethereum Blockchain: An Economic Analysis of EIP-1559”. In: CoRR abs/2012.00854 (2020). arXiv: 2012.00854.
[Rou21] Tim Roughgarden. “Transaction fee mechanism design”. In: ACM SIGecom Exchanges 19.1 (2021), pp. 52–55.
[RSMLSP21] Daniël Reijsbergen, Shyam Sridhar, Barnabé Monnot, Stefanos Leonardos, Stratis Skoulakis, and Georgios Piliouras. “Transaction Fees on a Honeymoon: Ethereum’s EIP-1559 One Month Later”. In: 2021 IEEE International Conference on Blockchain (Blockchain) (2021), pp. 196–204.
[SCW23] Elaine Shi, Hao Chung, and Ke Wu. “What Can Cryptography Do for Decentralized Mechanism Design?” In: 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA. Ed. by Yael Tauman Kalai. Vol. 251. LIPIcs. Saarbrücken/Wadern, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, 97:1–97:22. doi: 10.4230/LIPIcs.ITCS.2023.97. url: https://doi.org/10.4230/LIPIcs.ITCS.2023.97.
[Sti64] George J. Stigler. “A Theory of Oligopoly”. In: Journal of Political Economy 72.1 (1964), pp. 44–61. issn: 00223808, 1537534X. url: http://www.jstor. org/stable/1828791 (visited on 01/06/2024).
[VM07] Paul Valiant and Silvio Micali. “Collusion-Resilient Revenue In Combinatorial Auctions”. In: (2007).
[WSC23] Ke Wu, Elaine Shi, and Hao Chung. Maximizing Miner Revenue in Transaction Fee Mechanism Design. Cryptology ePrint Archive, Paper 2023/283. https://eprint.iacr.org/2023/283. 2023. url: https://eprint.iacr. org/2023/283.
[Yao18] Andrew Chi-Chih Yao. An Incentive Analysis of some Bitcoin Fee Designs. 2018. doi: 10.48550/ARXIV.1811.02351.
[YSZ23] Aviv Yaish, Gilad Stern, and Aviv Zohar. “Uncle Maker: (Time)Stamping Out The Competition in Ethereum”. In: Proceedings of the 2023 ACM SIGSAC Conference on Computerand Communications Security (CCS ’23). CCS ’23. Copenhagen, Denmark: Association for Computing Machinery, 2023. isbn: 9798400700507. doi: 10.1145/3576915.3616674.
[ZXECWWQWSG23] L. Zhou, X. Xiong, J. Ernstberger, S. Chaliasos, Z. Wang, Y. Wang, K. Qin, R. Wattenhofer, D. Song, and A. Gervais. “SoK: Decentralized Finance (DeFi) Attacks”. In: 2023 IEEE Symposium on Security and Privacy (SP). Los Alamitos, CA, USA: IEEE Computer Society, May 2023, pp. 2444–2461. doi: 10.1109/SP46215.2023.10179435. url: https://doi.ieeecomputersociety.org/10.1109/SP46215.2023.10179435.
A Missing Proofs
We now show that f(v) must be monotone whenever v ≥ r. If not, then there is such v ′ > v ≥ r so that f(v′) < f(v). Consider two bidders who bid v′, v. Without miner intervention, the miner would receive payment f(v′)−r. If the miner omits the bid v′, it receives payment f(v)−r > f(v′)−r, and so this contradicts MMIC.
( =⇒ All auctions of the form specified are MMIC+1-OCA-proof)
We have 1-OCA-proofness by the characterization of Lemma 4.4. Regarding MMIC, the miner cannot gain by adding fake bids since the burn is constant and the payment only depends on the winning bid: If the added fake bids do not change the winning bid, then the miner revenue does not change, and if they do, since the item is allocated to the highest bidder, this means that one of the fake bids wins, and the miner revenue is then non-positive. The miner cannot gain by omitting bids since the burn is constant and the payment is monotone in the highest bid, and the highest bid can only decrease by omitting bids.
B Non-anonymous Deterministic Mechanisms
We quickly revisit our auction model to allow for non-anonymous mechanisms. We now have a fixed set of N possible named bidders, out of which some subset I ⊆ N actually participates in the auction. The allocation, payment, and burn rule a, p, β now operate on the domain RI and may incorporate the identities of the bidders into the outcome. The DSIC, MMIC, OCA-proofness, and SCP notions remain the same, with the important emphasis that we still allow for the miner to issue fake bids. This is justified by the fact that an agent may hold multiple bidder identities, and so in the analysis perspective it is possible that the miner is in control of virtually any of the bidder identities.
Importantly, Lemma 3.5 (0 revenue in the single bidder case), Fact 3.4 (Myerson’s Lemma), Theorem 4.1 (0 revenue in the general case) transfer to the non-anonymous case and we subsequently use them.
We now characterize the space of DSIC+MMIC+1-OCA-proof non-anonymous mechanisms. We do so by proving progressive refinements of the space of possible mechanisms.
Lemma B.1. All DSIC+MMIC+1-OCA-proof mechanisms satisfy the following properties:
Proof. We give a proof sketch, as the proof resembles the one for the anonymous case.
We prove each property separately.
It is then straightforward to show that the class of mechanisms we identified cannot be further refined, and in fact satisfies a stronger property:
Lemma B.2. The class of mechanisms characterized in Lemma B.1 is DSIC+MMIC+SCP.
Proof. Consider a mechanism contained in the class. It is DSIC, as per the definition of the class in Lemma B.1, the mechanism satisfies the monotone allocation and critical bid payment conditions of Myerson’s Lemma Fact 3.4. The MMIC property is satisfied as the payment and burn rules are equal, implying that the miner always receives 0 revenue, thereby preventing the miner from being able to unilaterally increase its revenue without potentially colluding with users.
le to unilaterally increase its revenue without potentially colluding with users. Finally, note that no beneficial collusion exists: the individual burn rate is fixed for each user, and cannot change as dependent on the bids of the other transactions included in the block, or the identities of the transactions’ creators.
SCP is satisfied since if the coalition C does not contain i∗, the aggregate utility of the coalition is 0 with truthful reports, while non-positive under any manipulation. If the coalition does contain i∗, the SCP condition becomes the DSIC condition for agent i∗, which is satisfied as the mechanism is DSIC.
Authors:
(1) Yotam Gafni, Weizmann Institute ([email protected]);
(2) Aviv Yaish, The Hebrew University, Jerusalem ([email protected]).
This paper is