Table of Links
-
Understanding OCA
B. Non-anonymous Deterministic Mechanisms
1.2 Related Work
Transaction Fee Mechanisms
The literature on applying auction theory to analyze blockchain transaction fee mechanisms has its early start in Lavi, Sattath, and Zohar [LSZ19], who put forward the monopolistic auction as a good TFM candidate that balances incentive-compatibility for users and the miner. Yao [Yao18] answers two open conjectures of [LSZ19] by providing a proof that the monopolistic auction is indeed asymptotically DSIC and that its revenue dominates the random sampling optimal price (RSOP) auction of Goldberg et al. [GHKSW06]. Roughgarden [Rou21; Rou20] introduces the OCA collusion-resistance notion and characterizes different aspects of the TFM space. He also provides detailed analysis of EIP-1559 and other popular auction formats. Chung and Shi [CS23] introduce the SCP collusion-resistance notion and show related properties, most importantly the impossibility of DSIC+1-SCP mechanisms.
Wu, Shi, and Chung [WSC23] further explore the design of TFMs when assuming honesty of most or some of the bidders. They show a very general impossibility of achieving non-negligible miner revenue, even when altogether using cryptographic primitives, Bayesian assumptions, approximate incentive-compatibility, and infinite block size, and match it with mechanisms that achieve this miner revenue. Shi, Chung, and Wu [SCW23] present the cryptographic MPC-assisted TFM model and show we can only achieve θ(ϵ) miner revenue given ϵ-approximate notions of incentive-compatibility and SCP. Gafni and Yaish [GY23] show we can achieve a OCA-proof, MMIC and Bayesian incentivecompatible (BIC) mechanism given i.i.d. bidders. Chen et al. [CSZZ23] show a BIC and SCP mechanism. While the focus of these works is in finding what relaxing assumptions and tools may allow feasibility of collusion-resistant mechanisms, we shine a light on matters still unresolved in the plain model, and focus on fully characterizing it.
Other works focus on reducing fees for bidders [BEOS23; DPG24], and some empirical works analyze the systemic effects of introducing EIP-1559 in Ethereuem [LLNZZZ22; RSMLSP21].
Extending the valuation framework
Bahrani, Garimidi, and Roughgarden [BGR23a] consider a setting where a miner has preferences over which transactions are included in the block, aside from it wishing to receive high revenue in fees. They show an impossibility for DSIC + MMIC mechanisms in this more general setting. Nourbakhsh, Hao, and Jhumka [NHJ24] consider a setting where users have preferences over the ordering of transactions in a block, and show that there is no deterministic DSIC + OCA-proof in this general order-sensitive setting. Bahrani, Garimidi, and Roughgarden [BGR23b] consider singleitem auctions where each “bidding agent” is in fact a decentralized autonomous organization (DAO). The agents treat the item as a public excludable good, and distribute the payment for it among them. The authors show that it is then impossible to achieve an efficient two-level mechanism, and show a tight θ(log n) bound on the efficiency that can be achieved, where n is the largest number of bidders in a DAO. Milionis et al. [MHAG22] study single-item NFT auctions. Although different from TFMs, they analyze them through similar lens, and find that it is impossible to achieve incentive-compatibility together with collusion-resistance.
The Dynamic Setting
While we, and the previously mentioned papers, focus on the setting of a single block, it is interesting to consider the dynamic setting, as the blockchain TFM operates repeatedly within short periods of time. The dynamic setting is not yet well-consolidated, and many different approaches exist to its modeling and operation. Different works study dynamic posted pricing [FMPS21], dynamic manipulation on EIP-1559 [AGHH23], analysis of the effects of dynamics on price and efficiency [KKLP23; Nis23; LRMP23], and the implications of having farsighted users and miners [GY23; HP23].
Random vs. Deterministic Mechanisms
Generally, in the mechanism design literature, randomized mechanisms can achieve better results than deterministic ones. For example, Dobzinski and Dughmi [DD13] show that randomized mechanisms can arbitrarily approximate the welfare of multi-unit auctions, while Lavi, Mu’alem, and Nisan [LMN03] show that deterministic mechanisms may achieve at most an approximation of 2. Nisan and Ronen [NR01] show a randomized/deterministic gap for the problem of task scheduling. In the context of TFMs, Chung and Shi [CS23] consider a notion where the miner is punished for introducing fake transactions (since they may need to end up paying for the fake transactions in future blocks). Given this notion, they show a randomized mechanism (the burning second-price auction) that achieves good properties, while they show that no deterministic mechanism can achieve it.
Despite the game-theoretic advantages of randomized mechanisms, “good” sources of randomness, also known as randomness beacons, are hard to come by in the blockchain setting [BGB17; CMB23], making deterministic mechanisms simpler to implement. Ideal randomness beacons should periodically generate random values such that no actor should be able to predict or bias future random values. Both properties may be vital for random mechanisms: For example, predictable beacons could allow users to account for future randomness when creating transactions so to increase their allocation probability, while miners may manipulate beacons susceptible to bias in order to increase their profits. In particular, Ethereum’s RANDAO is known to be vulnerable to biasing manipulations that allow even small agents (i.e., proposers with a small fraction of the stake) to risklessly increase their expected number of blocks to some small extent [AR20; Edg23]. Incorporating randomness into the transaction allocation process can increase the profitability of such manipulations, where several randomness beacon designs are known to be secure only when the potential profits from manipulations are limited [CMB23]. This is not only a theoretical threat as miners have been observed to manipulate cryptocurrency mechanisms in the wild [YSZ23], and the potential profits from manipulations can be large [ZXECWWQWSG23].
While we only show impossibility results for both deterministic and randomized mechanisms, our results for deterministic mechanisms are more conclusive, and it remains possible that a randomized mechanism may achieve the TFM incentive-compatibility and OCA-proof desiderata.
The Economic Literature on Collusion
There is vast economic literature discussing collusion, especially concerning industrial cartels. The focus of that literature is mostly on user-user collusion[2], i.e., bidders cooperating without the auctioneer. This is in contrast to miner-user collusion, where the coalition necessarily includes the miner, as in the OCA and SCP notions of [Rou21; CS23]. This focus on user-user collusion can perhaps be explained by US government auctions being the prime example of this auction setting. Early on, the seminal work of Stigler [Sti64] identified many caveats that stand in the way of successful collusion.
Different works focus on particular types of collusion. The seminal work of Ausubel and Milgrom [AM02] studies core-selecting auctions. This captures the fact that in combinatorial auctions with complements (rather than substitutes), VCG may charge low payments, such that some of the losing bidders may be willing to pay. Thus, for an outcome to be stable, it must be in the core of the underlying coalitional game. Goeree and Lien [GL16] show an impossibility of truthful efficient core-selecting auctions, which is somewhat analogous to the DSIC + 1-SCP impossibility [CS23]. Another prominent notion of collusion is that of bribing [FPR23; ES04; Rac14; Rac15].
Che and Kim [CK09] show how to construct optimal revenue collusion-proof single-item auctions, i.e., how to implement the Myerson auction allocation rule in a way that is collusion-resistant. Notice, however, that they assume knowledge of the identity of the colluding bidders. An interesting emphasis in the work is that beliefs and strategies are updated in case a possible member declines participating in a bidding ring. The bidder is then aware of the existence of the bidding ring, and may also be punished by the bidders upon its rejection of participation.[3] Valiant and Micali [VM07] provide a characterization of what revenue benchmark can be achieved for general collusion-proof combinatorial auctions, and provide a mechanism that guarantees a revenue which is a logarithmic approximation of the welfare of all but the “highest” bidder, in a sense they define.
McAfee and McMillan [MM92] provide a characterization of the optimal collusion against secondprice auctions with and without transfers between the colluders. Importantly, they emphasize the bargaining aspect of the collusion, where different bidders may prefer different collusion agreements. Bachrach [Bac10] studies this problem as a coalitional game, and shows that the Shapley value of the bidders (w.r.t. the collusion) is in the core of the game.
Authors:
(1) Yotam Gafni, Weizmann Institute ([email protected]);
(2) Aviv Yaish, The Hebrew University, Jerusalem ([email protected]).
This paper is
[2] See, e.g., [GL79; DM17; LST00; GH05]
[3] Rachmilevitch [Rac14] also emphasizes, in the case of bribing in first-price auctions, how rejecting a bribe influences the beliefs and behavior of bidders subsequently.