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.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. 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∗. Proof 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. 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. Proof 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. 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. 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. Proof 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. Remark 2. 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.

UIC, MIC, and OCA Walk Into a Bar… and Break Mechanism Design

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