Static Revelation Principle for Transaction Fee Mechanisms | HackerNoon

Table of Links

Abstract and 1. Introduction

1.1 Our Contributions

1.2 TFM Incentive-Compatibility Notions: A Cheat Sheet

2. Definitions

   2.1 Transaction Fee Mechanism

   2.2 Incentive Compatibility Notions

3. Preliminary: Myerson’s Lemma

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

5. Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap

   5.2 Formal Proofs

6. 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

7. 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

8. 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

8 Static Revelation Principle for Transaction Fee Mechanisms

Informally speaking, the revelation principle says that any mechanism can be simulated by an equivalent truthful mechanism. Whenever the revelation principle holds, without loss of generality, we may assume that the users’ honest bidding strategy is simply truth-telling. We focus here on a revelation principle for “static” mechanisms in which users interact with a mechanism simply by submitting a bid.[10]

TFMs differ from traditional auctions in that they additionally need to satisfy MIC and collusion resilience, and also the separation of the inclusion rule (executed by the miner) and the confirmation/payment rules (executed by the blockchain). Therefore, revelation principles are not “automatic.” In this section, we prove that for any fixed c, the revelation principle holds for TFMs that must satisfy UIC, MIC, and c-SCP. As a direct corollary, the revelation principle holds for TFMs that satisfy UIC, MIC, and global SCP. The main subtlety in the proof is that when we bake the user’s non-truth-telling bidding rule β into the mechanism itself, not only do we need to have the miner’s inclusion rule execute β, the blockchain’s confirmation/payment rules must also double-check the correct enforcement of β again. Otherwise, a strategic miner may not honestly enforce β.

Notice that we focus on the mechanisms that satisfy c-SCP instead of OCA-proofness in this section. c-SCP requires that following the honest bidding rule and the honest inclusion rule is a dominant strategy for a coalition consisting of the miner and at most c users. For a non-truthful mechanism with the bidding rule β, β is used by users to satisfy both the UIC and the c-SCP conditions. In Section 8.1, we assume the honest bidding rule β only outputs a single bid. in Section 8.2, we generalize the proof so that β can output any non-negative number of bids.

8.1 Static Revelation Principle: Bidding Rules That Output Single Bid

Theorem 8.1 (Static revelation principle). Let c be any natural number. Suppose Π is a nontruthful TFM for block size k that is UIC, MIC, and c-SCP with an individually rational bidding rule β. If β always outputs a single bid, then there exists a truthful TFM Π′ for block size k that is UIC, MIC, and c-SCP such that 1) the honest bidding rule is truth-telling, and 2) given any vector of true values, the outcome under an honest execution of Π is identically distributed as the outcome under an honest execution of Π′.

Notice that β is individually rational under Π, so the payment corresponding to the bid β(v) never exceeds v. Thus, under the induced mechanism Π′, the payment never exceeds the bid, so the individual rationality of the payment rule is respected.

Next, by directly checking the syntax, the user’s confirmation probability and expected payment when submitting a bid b under Π′ is identically distributed to submitting a bid β(b) under Π assuming the miner follows the inclusion rule. Similarly, the miner’s revenue when creating a block B under Π′ is identically distributed to creating a block β(B) under Π. Thus, the outcome under an honest execution of Π is identically distributed as the outcome under an honest execution of Π′.

Finally, we show that the induced mechanism Π′ satisfies UIC, MIC, and global SCP. Since submitting a bid b and creating a block B under Π′ is equivalent to submitting a bid β(b) and creating a block β(B) under Π, respectively, the fact that Π′ satisfies UIC and global SCP directly follows from the fact that Π satisfies UIC and global SCP under the user’s honest bidding rule β.

[10] More generally, typical revelation principles in auction theory transform non-direct mechanisms (in which the action space may be different from the valuation space, for example due to multiple rounds of user-mechanism interaction) into a direct mechanisms.