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.1 Our Contributions
As explained above, both Roughgarden’s and Chung and Shi’s collusion-resilience notions capture meaningful incentive compatibility considerations. Recognizing their differences, one natural question is: does Chung and Shi’s finite-block impossibility result still hold if we adopt the original OCA-proofness notion of Roughgarden in lieu of c-SCP? Notably, no existing TFM construction [LSZ19, Yao, BEOS19, BCD+, Rou20, Rou21, FMPS21, CS23, SCW23, WSC24, GY22, ZCZ22, BGR23, TY23, KKLP23, XFP23, CMW23, LRMP23, Ndi23] simultaneously satisfies user incentive compatibility, miner incentive compatibility, and OCA-proofness under finite block size.
Main impossibility result. In our work, we give an affirmative answer to the above question. We show that, indeed, an analog of Chung and Shi’s finite-block impossibility result still holds when we replace the c-SCP requirement with OCA-proofness. Specifically, we prove the following theorem.
Theorem 1.1. Suppose the block size is finite. Then, no possibly randomized, truthful TFM can simultaneously satisfy user incentive compatibility (UIC), miner incentive compatibility (MIC), and OCA-proofness. Further, this impossibility holds even when the globally optimal strategy σ need not be individually rational.
In a truthful TFM, a user is expected to bid truthfully, so if the mechanism satisfies UIC, a user’s utility is maximized when it just reports its true value. However, OCA-proofness allows the global coalition to adopt a non-truthful bidding strategy σ even for truthful mechanisms.
Our Theorem 1.1 is intuitively stronger but technically incomparable in comparison with Chung and Shi’s impossibility, which shows that no TFM can simultaneously satisfy UIC and 1-SCP for finite block sizes. The reason is that Chung and Shi’s impossibility does not rely on MIC; however, MIC is necessary for our Theorem 1.1 to hold. Specifically, a simple second-price auction with no burning (see Remark 2) satisfies both UIC and OCA-proofness, but does not satisfy MIC since the miner may benefit by injecting a fake (t + 1)-th bid where t is the number of confirmed bids, since the (t + 1)-th bid sets the price for confirmed bids.
Global SCP. We suggest a simpler version of OCA-proofness that we call global SCP, which also intuitively captures the requirement that strategic users and miners cannot steal from the protocol, and is perhaps more appropriate when focusing on UIC TFMs (as we do in this paper). In our work, global SCP is not only a technical stepping stone towards proving Theorem 1.1, but also of independent interest as we explain below. Specifically, global SCP is almost the same as OCAproofness, except for requiring σ to be the honest bidding strategy indicated by the mechanism (i.e., the same bidding strategy used to establish UIC). In other words, a mechanism satisfies global SCP if and only if the honest strategy is surplus-maximizing for the global coalition. It is easy to see that for a truthful mechanism, c-SCP for any c implies global SCP, which in turn implies OCA-proofness. To prove Theorem 1.1, we first prove the following theorem:
Theorem 1.2. Suppose that the block size is finite. Then no possibly randomized TFM can simultaneously satisfy user incentive compatibility (UIC), miner incentive compatibility (MIC), and global SCP. Further, the impossibility holds even for non-truthful mechanisms.
We now explain why the global SCP notion is of independent interest. One advantage of global SCP is that the revelation principle holds for any TFM that satisfies UIC, MIC, and global SCP, which we formally prove in Section 8. In other words, given any TFM that is UIC, MIC, and global SCP, there is an equivalent truthful mechanism that simulates it. For this reason, Theorem 1.2 rules out even non-truthful TFMs that simultaneously satisfy UIC, MIC, and global SCP.[3]
By contrast, Theorem 1.1 holds only for truthful mechanisms. In particular, in Section 6.1, we show a non-truthful mechanism that simultaneously satisfies UIC, MIC, and OCA-proof. The mechanism is contrived, but it demonstrates the subtlety and the technical challenges when modeling the notion of collusion-resilience. This also suggests that the revelation principle does not hold for mechanisms that satisfy UIC, MIC, and OCA-proofness, partly because in such a mechanism, the bidding strategies used to establish UIC and OCA-proofness may be different.
Ways to circumvent the impossibilities. We show in Section 7 that the impossibility of Theorem 1.1 can be circumvented by allowing non-truthful mechanisms or by allowing users to coordinate in bidding in the globally optimal strategy σ. In the same section, we raise an open question regarding whether it is possible to use cryptography (e.g., the MPC-assisted model of Shi et al. [SCW23]) and Bayesian notions of incentive compatibility to circumvent the impossibilities.
[3] Simultaneously with and independently of this paper, Gafni and Yaish [GY24] proved, among other results, a version of Theorem 1.2 for the special case of deterministic mechanisms and a block size of 1.
