Table of Links
Abstract and 1. Introduction
1.1 Our Contributions
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
A. Comparison of Collusion-Resilience Notions
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.
• 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.
• 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.
• 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.
• 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).
• 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.
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.
[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]).
