Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 1.1 Our Contributions 1.1 Our Contributions 1.2 TFM Incentive-Compatibility Notions: A Cheat Sheet 1.2 TFM Incentive-Compatibility Notions: A Cheat Sheet Definitions
2.1 Transaction Fee Mechanism
2.2 Incentive Compatibility Notions


Preliminary: Myerson’s Lemma


Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms


Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap
5.2 Formal Proofs


Feasibility and Impossibility of UIC + MIC + OCA-Proof
6.1 A Non-Truthful Mechanism with UIC + MIC + OCA-Proof
6.2 Impossibility of UIC + MIC + OCA-Proof for Truthful Mechanisms


How to Circumvent the Impossibilities and 7.1 Allowing the Globally Optimal Strategy to Coordinate
7.2 Allowing the Globally Optimal Strategy to Output Multiple Bids
7.3 Inclusion-Rule-Respecting and 7.4 Discussions and Open Questions Regarding the Use of Cryptography


Static Revelation Principle for Transaction Fee Mechanisms
8.1 Static Revelation Principle: Bidding Rules That Output Single Bid
8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple Bids Definitions
2.1 Transaction Fee Mechanism
2.2 Incentive Compatibility Notions Definitions 2.1 Transaction Fee Mechanism 2.1 Transaction Fee Mechanism 2.2 Incentive Compatibility Notions 2.2 Incentive Compatibility Notions Preliminary: Myerson’s Lemma Preliminary: Myerson’s Lemma Preliminary: Myerson’s Lemma Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap
5.2 Formal Proofs Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap 5.2 Formal Proofs 5.2 Formal Proofs Feasibility and Impossibility of UIC + MIC + OCA-Proof
6.1 A Non-Truthful Mechanism with UIC + MIC + OCA-Proof
6.2 Impossibility of UIC + MIC + OCA-Proof for Truthful Mechanisms Feasibility and Impossibility of UIC + MIC + OCA-Proof Feasibility and Impossibility of UIC + MIC + OCA-Proof 6.1 A Non-Truthful Mechanism with UIC + MIC + OCA-Proof 6.1 A Non-Truthful Mechanism with UIC + MIC + OCA-Proof 6.2 Impossibility of UIC + MIC + OCA-Proof for Truthful Mechanisms 6.2 Impossibility of UIC + MIC + OCA-Proof for Truthful Mechanisms How to Circumvent the Impossibilities and 7.1 Allowing the Globally Optimal Strategy to Coordinate
7.2 Allowing the Globally Optimal Strategy to Output Multiple Bids
7.3 Inclusion-Rule-Respecting and 7.4 Discussions and Open Questions Regarding the Use of Cryptography How to Circumvent the Impossibilities and 7.1 Allowing the Globally Optimal Strategy to Coordinate How to Circumvent the Impossibilities and 7.1 Allowing the Globally Optimal Strategy to Coordinate 7.2 Allowing the Globally Optimal Strategy to Output Multiple Bids 7.2 Allowing the Globally Optimal Strategy to Output Multiple Bids 7.3 Inclusion-Rule-Respecting and 7.4 Discussions and Open Questions Regarding the Use of Cryptography 7.3 Inclusion-Rule-Respecting and 7.4 Discussions and Open Questions Regarding the Use of Cryptography Static Revelation Principle for Transaction Fee Mechanisms
8.1 Static Revelation Principle: Bidding Rules That Output Single Bid
8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple Bids Static Revelation Principle for Transaction Fee Mechanisms Static Revelation Principle for Transaction Fee Mechanisms 8.1 Static Revelation Principle: Bidding Rules That Output Single Bid 8.1 Static Revelation Principle: Bidding Rules That Output Single Bid 8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple Bids 8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple Bids A. Comparison of Collusion-Resilience Notions A. Comparison of Collusion-Resilience Notions References References 1.2 TFM Incentive-Compatibility Notions: A Cheat Sheet We gather here informal definitions and comparisons of the key incentive-compatibility notions used in this paper. First, a transaction fee mechanism specifies how a user is supposed to bid (as a function of its private valuation), which transactions a miner is supposed to include (as a function of the transactions it knows about and their bids), and the resulting outcome (the subset of included transactions that get confirmed, and the payments made by the users and received by the miner). If the bidding strategy suggested by the TFM is the identity, then we additionally call the TFM truthful. In this paper, as in the rest of the TFM literature, we consider only static mechanisms. truthful • UIC. (Definition 2) Provided that the miner follows the suggested inclusion rule, the bidding strategy suggested by the TFM is a dominant strategy for users. UIC • MIC. (Definition 3) The inclusion rule suggested by the TFM is always revenue-maximizing for the miner regardless of users’ bids; moreover, the miner cannot increase its revenue through the injection of fake transactions. MIC • Global SCP. (Definition 5) If the miner follows the inclusion rule suggested by the TFM and all users follow the bidding rule suggested by the TFM, then their joint surplus is at least as large as it would be from any coordinated deviation. • Global SCP. • c-SCP. (Definition 4) For every coalition of the miner and at most c users, if the miner follows the inclusion rule suggested by the TFM and the users in the coalition follow the bidding rule suggested by the TFM, then the joint surplus of the coalition is at least as large as it would be from any coordinated deviation (holding fixed the bids of users outside the coalition). • c-SCP • OCA-proof. (Definition 6) If the miner follows the inclusion rule suggested by the TFM and all users follow a suitably chosen individually rational bidding rule σ (possibly different from the one suggested in the TFM description), then their joint surplus is as large as it would be from any coordinated deviation. • OCA-proof. For example, in [Rou21] it was shown that Ethereum’s EIP-1559 TFM and a variant called the “tipless mechanism” satisfy UIC, MIC, and OCA-proofness when there is no contention between transactions; in fact, in this case, these TFMs satisfy the c-SCP condition for every c ≥ 1. When there is contention between transactions for inclusion in a block, the EIP-1559 TFM loses its UIC property and the tipless mechanism loses (all three notions of) collusion-resilience. As mentioned above: • (Theorem 8.1) A relevation principle holds for the global SCP and c-SCP notions: any UIC and MIC TFM that satisfies one of these properties can be simulated by a truthful UIC and MIC TFM that satisfies the same property. • A relevation principle does not in general hold for the OCA-proof notion: while there are non-truthful TFMs that satisfy UIC, MIC, and OCA-proofness (Section 6.1), there are no truthful TFMs that satisfy UIC, MIC, and OCA-proofness (Theorem 6.9). The main result in Chung and Shi [CS23] states that, even among randomized TFMs, no TFM satisfies UIC and c-SCP for any c ≥ 1. Our Theorem 5.6 proves that, even among randomized TFMs, no TFM satisfies UIC, MIC, and global SCP. (Due to the revelation principle mentioned above, these impossibility results apply to both truthful and non-truthful TFMs.) Our Theorem 6.9 proves the stronger statement that, even among randomized TFMs, no truthful TFM satisfies UIC, MIC, and OCA-proofness. Reflecting on the competing notions of collusion-resilience, we can observe the following. The cSCP condition may be particularly appropriate in scenarios where the primary concern is deviations by small coalitions, or in scenarios where users may wish to deviate in ways that exploit other users. The c-SCP condition is also notable in that, together with the UIC condition, it already triggers the impossibility result in [CS23] (without any appeal to MIC). The OCA-proofness condition is distinguished by being the weakest of the three notions (thus leading to the strongest impossibility results) and by allowing the discussion of non-UIC mechanisms.[4] For TFMs that are UIC and MIC, like those studied in this paper, global SCP is arguably the “right” definition—capturing the spirit of OCA-proofness, without any additional technical complications arising from users using different bidding strategies to satisfy UIC and collusion-resilience. Put differently, the UIC and MIC conditions imply that the miner and the users following their intended strategies constitutes a Nash equilibrium; the global SCP condition asserts that this Nash equilibrium is also robust to deviations by the grand coalition, while OCA-proofness only asserts such robustness for a possibly different strategy profile (defined by the intended inclusion rule and some individually rational bidding strategy). From this vantage point, one might view Theorem 5.6 as the main impossibility result in this paper, with Theorem 6.9 serving as a technically challenging extension of the result under still weaker incentive-compatibility conditions. Authors:
(1) Hao Chung∗, Carnegie Mellon University (haochung@andrew.cmu.edu);
(2) Tim Roughgarden†, Columbia University and a16z (crypto tim.roughgarden@gmail.com);
(3) Elaine Shi∗, Carnegie Mellon University (runting@cs.cmu.edu). Authors: Authors: (1) Hao Chung∗, Carnegie Mellon University (haochung@andrew.cmu.edu); (2) Tim Roughgarden†, Columbia University and a16z (crypto tim.roughgarden@gmail.com); (3) Elaine Shi∗, Carnegie Mellon University (runting@cs.cmu.edu). This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv available on arxiv [4] For example, in a first-price auction, the “reference outcome” might be defined by a (non-truthful) bidding strategy that would constitute a Bayes-Nash equilibrium with respect to some prior over user valuations (cf., Corollary 5.12 in [Rou21]).

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Ethereum

Why No Transaction Fee Mechanism Can Truly Be Collusion-Proof

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

5 Ways to Measure Privacy Risks in Text Data

Why the Perfect Blockchain Fee Mechanism May Be Impossible

Why Truthful Blockchain Mechanisms Fail Under Finite Block Sizes

What Is a Transaction Fee Mechanism? Definitions, Incentives, and Strategies

No Blockchain Auction Can Satisfy UIC, MIC, and Global SCP at Once

5 Ways to Measure Privacy Risks in Text Data

Why the Perfect Blockchain Fee Mechanism May Be Impossible

Why Truthful Blockchain Mechanisms Fail Under Finite Block Sizes

What Is a Transaction Fee Mechanism? Definitions, Incentives, and Strategies

No Blockchain Auction Can Satisfy UIC, MIC, and Global SCP at Once

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps