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 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. • Globally optimal strategy • Bidding rule: Given a true value v, output a bid 1/(v + 2). • Bidding rule • 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. • Inclusion rule • Confirmation, payment, and miner revenue rules: All included bids are confirmed. Each confirmed bid pays nothing, and the miner gets nothing. • Confirmation, payment, and miner revenue rules Obviously, this mechanism is non-trivial. Claim 6.1. The above mechanism satisfies UIC, MIC, and OCA-proofness. 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. Proof 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. Remark 1. 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

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

The Impossibility Theorem Behind Truthful Blockchain Bidding 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