Table of Links Abstract and 1. Introduction Abstract and 1. Introduction 1.1 Our Contributions 1.1 Our Contributions 1.2 TFM Incentive-Compatibility Notions: A Cheat Sheet 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 Definitions
2.1 Transaction Fee Mechanism
2.2 Incentive Compatibility Notions Definitions 2.1 Transaction Fee Mechanism 2.1 Transaction Fee Mechanism 2.2 Incentive Compatibility Notions 2.2 Incentive Compatibility Notions Preliminary: Myerson’s Lemma Preliminary: Myerson’s Lemma Preliminary: Myerson’s Lemma Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms Warmup: Impossibility of UIC + MIC + Global SCP for Deterministic Mechanisms 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 Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap Impossibility of UIC + MIC + Global SCP for Randomized Mechanisms and 5.1 Proof Roadmap 5.2 Formal Proofs 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 Feasibility and Impossibility of UIC + MIC + OCA-Proof Feasibility and Impossibility of UIC + MIC + OCA-Proof 6.1 A Non-Truthful Mechanism with 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 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 How to Circumvent the Impossibilities and 7.1 Allowing the Globally Optimal Strategy to Coordinate 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.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 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 Static Revelation Principle for Transaction Fee Mechanisms Static Revelation Principle for Transaction Fee Mechanisms 8.1 Static Revelation Principle: Bidding Rules That Output Single Bid 8.1 Static Revelation Principle: Bidding Rules That Output Single Bid 8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple Bids 8.2 Static Revelation Principle: Allowing Bidding Rules that Output Multiple Bids A. Comparison of Collusion-Resilience Notions A. Comparison of Collusion-Resilience Notions References 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] revelation principle 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. Later 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 Π′. Theorem 8.1 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 β. Authors:
(1) Hao Chung∗, Carnegie Mellon University (haochung@andrew.cmu.edu);
(2) Tim Roughgarden†, Columbia University and a16z (crypto tim.roughgarden@gmail.com);
(3) Elaine Shi∗, Carnegie Mellon University (runting@cs.cmu.edu). Authors: Authors: (1) Hao Chung∗, Carnegie Mellon University (haochung@andrew.cmu.edu); (2) Tim Roughgarden†, Columbia University and a16z (crypto tim.roughgarden@gmail.com); (3) Elaine Shi∗, Carnegie Mellon University (runting@cs.cmu.edu). This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv available on arxiv [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.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Static Revelation Principle for Transaction Fee Mechanisms

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

5 Ways to Measure Privacy Risks in Text Data

Why the Perfect Blockchain Fee Mechanism May Be Impossible

Why Truthful Blockchain Mechanisms Fail Under Finite Block Sizes

Why No Transaction Fee Mechanism Can Truly Be Collusion-Proof

What Is a Transaction Fee Mechanism? Definitions, Incentives, and Strategies

5 Ways to Measure Privacy Risks in Text Data

Why the Perfect Blockchain Fee Mechanism May Be Impossible

Why Truthful Blockchain Mechanisms Fail Under Finite Block Sizes

Why No Transaction Fee Mechanism Can Truly Be Collusion-Proof

What Is a Transaction Fee Mechanism? Definitions, Incentives, and Strategies

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps