When Every Mechanism Burns: The Theoretical Boundaries of DSIC, MMIC, and OCA-Proof Design

Table of Links

Abstract and 1. Introduction

1.1 Technical Overview

1.2 Related Work

2. Model and Preliminaries and 2.1 Transaction Fee Mechanisms

   2.2 The TFM Desiderata

3. Understanding OCA

   3.1 The Difference Between SCP and OCA

   3.2 Useful Preliminary Results for OCA-proof TFMs

4. Deterministic OCA-proof Mechanisms

5. Randomized OCA-proof Mechanisms

6. Discussion and References

A. Missing Proofs

B. Non-anonymous Deterministic Mechanisms

1.1 Technical Overview

We start our work by fully understanding the single bidder case. In Lemma 3.5, we observe that due to the analogy in this case between the bidder’s utility (w.r.t. payments) and the joint utility of the bidder and miner (w.r.t. to the amount of fees that are burnt), it must hold that all payments are burnt, meaning that miner revenue must equal 0. As we show in Example 3.6, this analogy does not hold once more bidders are involved. However, this important observation paves the way for our general result on the deterministic multi-bidder case. Thus, in Theorem 4.1 we show that the miner cannot have any revenue in the general case, as otherwise this would allow the miner to achieve positive revenue in the single bidder case by introducing fake bids.

Going beyond this result, we fully characterize the OCA-proof single bidder case and find it takes the form of a “posted burn” (in analogy to the “posted price” characterization of the single bidder DSIC case). I.e., there is some reserve “burn” r, so that the price the bidder must pay is equal to or above it, with r completely burnt. The mechanism has freedom in choosing the payment as long as it is larger than r, as to allow burning the reserve price in full. Then, we extend this structure to any number of bidders, again due to the OCA-proofness property. That is since the highest bidder and the miner always have the option to omit all other bids and give the item (subject to the “posted burn” r) to the highest bidder, thus maximizing their joint utility. We therefore derive a general structure for OCA-proof mechanisms as allocating to the highest bidder with a “posted burn” r. This generalizes a known result in the TFM literature: Both the “tipless mechanism” and EIP-1559 are OCA-proof [Rou21] when the burn rate is high enough, where both have different payments. Our result emphasizes that, in fact, there can be a wide variety of mechanisms of this sort.

This characterization of OCA-proof mechanisms, where the payment is the only degree of freedom left for the mechanism besides deciding the “posted burn” r, is then what drives our impossibility result for the deterministic case. This is because DSIC and MMIC payment rules differ conceptually: DSIC rules must follow the Myerson critical bid form (Fact 3.4), and so DSIC+OCAproof mechanisms follow the form of a second-price auction with a reserve price r that is burned (Theorem 4.5), while MMIC payment rules must be robust to the miner artificially increasing them through fake bids, and so must only depend on the winning bid. Strictly speaking, the payment does not have to be the winning bid itself (i.e., first-price with burned reserves), but rather any function that increases with the winning bid and respects the “posted burn” r. This can be considered as a form of “generalized first-price” (Theorem 4.6). Our characterizations of all DSIC+OCA-proof and MMIC+OCA-proof mechanisms, have just a single mechanism at their intersection: the trivial mechanism, thus resulting in our 0 revenue impossibility result for DSIC+MMIC+OCA-proof mechanisms (Theorem 4.7).

We then turn our attention to randomized mechanisms. We first consider the natural class of scale invariant mechanisms. For such mechanisms, any homogeneous transformation of the bids preserves the allocation outcome. These mechanisms are natural, as intuitively, the relative values of the different bidders should be the decisive factor when allocating bids, and not the “measurement unit”. Indeed, many commonplace auctions are scale invariant, e.g., the first-price auction, the second-price auction, and the all-pay auction. The crucial technical property of scale-invariant OCA-proof auctions is that they cannot burn any fees. This is because given a non-zero burn rule, bidders can coordinate to all scale down their bids, to the point that this burn exceeds what is allowed by basic auction properties such as individual rationality and burn balance. Thus, the burnt amount must be lowered, in contradiction to OCA-proofness. Together with our understanding of the single bidder case as having 0 revenue, this implies that the item must be either always or never given to the single bidder (Lemma 5.5). Having the item fully allocated to the bidder with no burn in the single bidder case is very lucrative for the joint utility of the bidder and the miner, as they can achieve optimal utility. With OCA-proofness, this degenerates the multi-bidder case to be forced to give the item to the highest bidder with full probability, which brings us back to the deterministic case, and thus to an impossibility (Theorem 5.6).

Lastly, we show efficiency approximation hardness results for general randomized mechanisms (i.e., not necessarily scale-invariant). Key to these results is Claim 5.11, which shows a lower bound on the possible aggregate burn for the two bidder case. While in the deterministic case we were able to show zero revenue, the miner has harder time introducing fake bids in the randomized case. That is because a fake bid might also win with some probability, and thus resulting in having some of its payment burnt. Still, while not implying zero revenue for the miner, this at least implies that its payment from the real bid must be bounded by the aggregate burn. Since the joint utility expression depends on the aggregate burn, this serves to bound the two-bidder allocation rule with the single bidder allocation rule (Lemma 5.12), by first tying together the allocation and payment through Myerson’s lemma, and then the payment and burn through Claim 5.11.

Using the way Lemma 5.12 ties the two-bidder case together with the single-bidder case, we are then able to infer two important results, both limiting the efficiency approximation that mechanisms may achieve. First, in Theorem 5.13, we upper bound the maximal probability with which the item is allocated in the single bidder case. No matter how high the single bid is, the item cannot be allocated with probability higher than 0.914. Then, in Lemma 5.14, we tie together the allocation probability in the two bidder case with the utility in the single bidder case. We use this in Corollary 5.15 to upper bound the utility in single bidder case (depending on the bidder’s value). Notice that because of our scale-invariance result, we know that the mechanism must behave differently given different bidder’s values. Corollary 5.15 shows that for some bidders’ values it must behave quite badly, allowing for efficiency approximation, i.e., the ratio between the joint utility and the optimal joint utility where the item is fully allocated without any burn, is at most 0.842.