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 Feasibility and Impossibility of UIC + MIC + OCA-Proof
We can generalize the proof in Section 5, and rule out UIC, MIC, and OCA-proof (rather than global SCP) for truthful mechanisms. Recall that for a truthful mechanism, the difference between OCA-proof and global SCP is that global SCP insists that the optimal strategy of the global coalition is the truthful strategy, whereas OCA-proofness allows it to be some other strategy in which each user acts independently and bids the outcome of some function σ(·).
Interestingly, if we allow the bidding rule to be not truth-telling, i.e. considering non-truthful mechanisms, we can have a mechanism that satisfies UIC, MIC, and OCA-proof. We present the feasibility for non-truthful mechanisms in Section 6.1, and we prove the impossibility of UIC + MIC + OCA-proof for truthful mechanisms in Section 6.2. Notice that because of the feasibility in Section 6.1, we must require the bidding rule to be truth-telling to reach an impossibility in Section 6.2.
6.1 A Non-Truthful Mechanism with UIC + MIC + OCA-Proof
The rationale of the design is to signal to the mechanism when everyone is adopting the globally optimal strategy σ (as opposed to the bidding rule used to establish UIC). When the mechanism detects that everyone is behaving according to σ, it adopts a different behavior to optimize social welfare. We use the range [0, 1) to encode the actual bid, and use the range [1,∞) for signalling. While the resulting mechanism is somewhat contrived and not necessarily meaningful from a practical point of view, it clarifies which notions of collusion-resilience most accurately capture the intended modeling goals and illustrates some technical challenges involved in the proof in Section 6.2. Consider the following TFM:
• Globally optimal strategy σ(v): Given a true value v, output a bid v + 1.
• Bidding rule: Given a true value v, output a bid 1/(v + 2).
• Inclusion rule: Let S be the set of all pending bids that are in [0, 1). If |S| > k, then randomly select k bids from S to include. If 1 ≤ |S| ≤ k, then include all bids in S. If |S| = 0, choose the top up to k bids to include.
• Confirmation, payment, and miner revenue rules: All included bids are confirmed. Each confirmed bid pays nothing, and the miner gets nothing.
Obviously, this mechanism is non-trivial.
Claim 6.1. The above mechanism satisfies UIC, MIC, and OCA-proofness.
Proof. For UIC, notice that if a user follows the bidding rule, its bid is always in [0, 1). If there is no bid in [0, 1) before a user submits its bid, then bidding 1/(v + 2) always guarantees user’s bid to be included and confirmed, where v denote the true value. If there is already some bids in [0, 1) before a user submits its bid, then bidding 1/(v + 2) is a dominant strategy since it guarantees the user’s bid is added to S, the set of all bids in [0, 1), which is the best a user can do. Next, MIC holds since the miner revenue is always zero. Finally, if all users follow the globally optimal strategy σ, everyone’s bid is at least 1. The honest inclusion rule will include the top up to k bids, which maximizes the social welfare. Thus, OCA-proofness holds.
Remark 1. We can try to apply revelation principle, and bake the bidding rule into the mechanism so that the resulting mechanism is truthful. For example, whenever seeing a bid b, the miner and the mechanism view it as 1/(b + 2). The modified mechanism, however, does not satisfy OCAproofness anymore when the number of users is larger than the block size, since the miner should choose k users with the highest true values instead of the random selection as indicated by the inclusion rule. This is not a coincidence: in the next section, we show that it is impossible to have a non-trivial truthful mechanism satisfying UIC, MIC, and OCA-proofness.
