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
6.2 Impossibility of UIC + MIC + OCA-Proof for Truthful Mechanisms
The structure of the proof in this section is similar to the proof in Section 5. In fact, Lemmas 6.2, 6.3 and 6.6 to 6.8 and Theorem 6.9 are the analogs of Lemmas 5.1 to 5.5 and Theorem 5.6, respectively, except that we need to work on the images of σ in order to apply OCA-proofness. Before diving into the proof, we make a few remarks.
• A key step in Section 5 is to prove a user with true value v must have zero utility, and we prove it by making an unconfirmed bid arbitrarily close to v (see Lemma 5.4). To extend the similar idea to OCA-proofness, we require σ to be strictly increasing and continuous. In fact, we show that being strictly increasing is a consequence of UIC and OCA-proofness (Lemma 6.4), and being strictly increasing implies that there exists a point at which σ is continuous (Corollary 6.5).
• As we have seen a feasibility for non-truthful mechanisms in Section 6.1, we must require the bidding rule to be truth-telling to reach an impossibility. Indeed, the proofs of Lemmas 6.4, 6.7 and 6.8 and Theorem 6.9 rely on Myerson’s lemma, and Myerson’s lemma requires the mechanism to be truthful. Notice that the mechanism in Section 6.1 does not satisfy the requirements of Myerson’s lemma. If we apply the revelation principle to make the mechanism become truthful so that Myerson’s lemma could apply, it breaks OCA-proofness (see Remark 1).
• Notice that OCA-proofness requires σ to output a single real-valued bid. In fact, if we allow σ to output multiple bids, we can have a (somewhat contrived) mechanism that satisfies UIC, MIC, and OCA-proof (see Section 7.2). In particular, Lemma 6.4 requires σ to only output a single real number.
• The original definition of OCA-proofness in [Rou21] also requires σ to be individually rational, but this will not be needed for the impossibility proof.
There are two possible cases.
Corollary 6.5. Suppose a truthful mechanism satisfies UIC and OCA-proofness with the globally optimal strategy σ, and let the block size be k. Then, there exists a constant c ∗ such that for any real number a > c∗, there exists a real number a ∗ ≥ a at which σ is continuous.
Proof. A well-known fact is that any function that is monotone must have only countably many discontinuities within any interval [x1, x2] where x2 > x1; further, all such discontinuities must be jump discontinuities. By Lemma 6.4, there exists a constant c ∗ such that σ is monotone for all inputs larger than c∗. Thus, for any a > c∗, within the interval [a, a + 1], σ is monotone and there must exist a point a ∗ such that σ is continuous at a∗.
Lemma 6.6. Suppose the mechanism satisfies MIC and OCA-proofness with the globally optimal strategy σ. Let a, b, b′ be arbitrary vectors. Consider two scenarios (σ(a), σ(b)) and (σ(a), σ(b′)). Suppose that σ(b) and σ(b′) have 0 confirmation probability in each of the two scenarios, respectively. Then, both scenarios enjoy the same expected miner utility, social welfare, and total user utility.
Proof. The equivalence in expected miner utility follows directly from MIC and the fact that the miner can change from b to b′ for free, or vice versa, since these bids are unconfirmed.
The equivalence in social welfare follows from OCA-proofness, and the fact that σ maximizes social welfare. Suppose, for example, the social welfare under (σ(a), σ(b)) is strictly greater than (σ(a), σ(b′)). Then, under the scenario where the users’ true values are (a, b′), everyone following σ will not maximize social welfare, since there is an OCA that have the users bid (σ(a), σ(b)) instead which strictly increases the social welfare.
The equivalence in total user utility follows directly from the above, since total user utility is the difference between the social welfare and the miner utility.
Lemma 6.7. Suppose a truthful mechanism satisfies UIC, MIC and OCA-proofness with the globally optimal strategy σ, and the block size is k. Then, there exists a constant c ∗ such that for any i ∈ [k], the following holds.
Theorem 6.9. No non-trivial, possibly randomized truthful TFM can simultaneously satisfy UIC, MIC, and OCA-proofness when the block size is finite.
Proof. We will show that under any sufficiently large a at which σ is continuous, the confirmation probability under a single bid σ(a) is non-zero. If we can show this, then we can show a contradiction to UIC and the Myerson’s lemma. Specifically, consider b > a which both are sufficiently large and at which σ is continuous (Corollary 6.5 guarantees such a, b exist). By Lemma 6.8, under both scenarios, the user utility is 0 (assuming the bid, σ(a) or σ(b), is the same as the user’s true value). By Lemma 6.4, for sufficiently large a, we have σ(b) > σ(a). However, by Myerson’s lemma, if the confirmation probabilities under a single σ(a) and under a single σ(b) are both non-zero, it cannot be that in both cases the user’s utility is 0. Otherwise, the user with the true value σ(b) can underbid σ(a). Since the confirmation probability is non-zero and the payment is at most σ(a), the user enjoys positive utility, which violates UIC.
Remark 2. Notice that Chung and Shi [CS23] showed that no TFM can simultaneously satisfy UIC and 1-SCP when the block size is finite. Their impossibility does not rely on MIC, while MIC is necessary for proving Theorem 6.9. Specifically, consider the second-price auction without burning defined as follows. Given the block size k, the miner includes the top up to k bids in the block. If the number of included bids is less than k, then all included bids are confirmed, and pay nothing. If the number of included bids is k, then the top k − 1 bids are confirmed, while the k-th bid is unconfirmed (break ties arbitrarily). All confirmed bids pay the k-th bid, and all the payments go to the miner. This mechanism satisfies UIC since the confirmation and the payment satisfy the requirements of Myerson’s lemma. The mechanism also satisfies OCA-proofness when σ is just bidding truthfully since the confirmed bids are always the ones with the highest true values, which maximizes the social welfare. However, it does not satisfy MIC, since the miner is incentivized to inject a fake bid to increase the k-th bid.
