Incentive-compatible Collusion-resistance via Posted Prices

Mathues V.X. Ferreira, Yotam Gafni, Max Resnick · 2024

Read Incentive-compatible Collusion-resistance via Posted Prices by Mathues V.X. Ferreira, Yotam Gafni, Max Resnick (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-20853.txt.

Description

A 2024 arXiv research paper by Mathues V.X. Ferreira, Yotam Gafni, Max Resnick. We consider a refinement to the notions of collusion-resistance in transaction fee mechanisms. In particular, we require that the collusion is by itself incentive-compatible and individually rational to all of its participants. We then study the structural properties of these notions, and importantly, characterize the class of collusion-resistant and incentive-compatible transaction fee mechanisms in the single bidder case, and show that this is exactly the class of posted-price where the price is not too prohibitive.

Catalog record

CREATORMathues V.X. Ferreira, Yotam Gafni, Max Resnick
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-20853

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Incentive-compatible Collusion-resistance via Posted Prices Mathues V.X. Ferreira, Yotam Gafni, Max Resnick Abstract We consider a refinement to the notions of collusion-resistance in transaction fee mechanisms. In particular, we require that the collusion is by itself incentive-compatible and individually rational to all of its participants. We then study the structural properties of these notions, and importantly, characterize the class of collusion-resistant and incentive-compatible transaction fee mechanisms in the single bidder case, and show that this is exactly the class of posted-price where the price is not too prohibitive. We analyze welfare and revenue implications, as well as the shape of the solution space, for both regular and non-regular distributions. \glsxtrnewsymbol [description= An auction. ]auction A \glsxtrnewsymbol [description= A transaction. ]tx tx \glsxtrnewsymbol [description= Payment rule. ]pay p \glsxtrnewsymbol [description= Burning rule. ]burn \beta \glsxtrnewsymbol [description= Update rule. ]update \upsilon \glsxtrnewsymbol [description= time to live (TTL)of a transaction. ]ttl t \glsxtrnewsymbol [description= Reserve price of an auction. ]reserve r \glsxtrnewsymbol [description= TTLof past transactions. ]mempoolSymb \mu \glsxtrnewsymbol [description= Immediacy ratio for our non-myopic allocation rule. ]imratio \ell \glsxtrnewsymbol [description= Transaction schedule function. ]adversary \psi \glsxtrnewsymbol [description= Allocation function. ]allocation x \glsxtrnewsymbol [description= Transaction fee of some transaction, in tokens. ]fee b \glsxtrnewsymbol [description= Maximal TTLof transactions in the blockchain, in blocks. ]maxttl d \glsxtrnewsymbol [description= Predefined maximal block-size, in bytes. ]blocksize \mathcal{B} \glsxtrnewsymbol [description= Miner’s relative mining power, as a fraction. ]minerRatio \alpha \glsxtrnewsymbol [description= Miner discount factor. ]discount \lambda \glsxtrnewsymbol [description= Miner planning horizon. ]horizon T \glsxtrnewsymbol [description= Miner revenue. ]revenue u \glsxtrnewsymbol [description= Number of all bids with b_{i}\geq{} . ]bidsMoreReserve S_{\geq{}} 1 Introduction Collusion-resistance is a long studied problem in the economic literature [ 17 ] . Recently, it has also gained importance as a primitive in Blockchain mechanism design [ 14 , 6 ] , in particular the design of transaction fee mechanisms. Roughgarden [ 14 ] defines the notion of an off-chain agreement (OCA), and shows that being OCA-proof is equivalent to maximizing the joint utility of the winning coalition together with the miner. The work then presents a main axiomatic question, of whether it is possible to arrive at a mechanism which is incentive-compatible for users (DSIC), incentive-compatible for miners (MMIC), and OCA-proof. This has recently been answered in the negative [ 7 , 3 ] . Chung & Shi [ 4 ] discuss a collusion notion they call c -SCP (side-contract proof), which means that no coalition of c users and the miner can benefit from deviation. They show that DSIC+ 1 -SCP is only achieved by the trivial mechanism, and in particular the revenue to the miner must be 0 . Gafni & Yaish [ 7 ] show that OCA and SCP are different notions, where SCP is strictly stronger. This paints a picture where it is impossible to achieve collusion resistance in transaction fee mechanisms, and is exacerbated by further results under relaxing assumptions [ 15 , 2 ] . Our main conceptual observation is that the collusion notions (OCA, SCP) are too strict in their current form. Most importantly, they assume complete trust between the colluders, in the sense that the colluders do not deviate or misuse the established collusion itself. This can may be best demonstrated by the example of avoiding a reserve price. Example 1.1 (A motivating example I, informal) Consider a seller that sells an item to a single buyer. Let us assume that it is defined by the protocol that the item needs to be sold for 10 USD. However, the buyer only values it at 5 USD. Then, the seller and buyer could collude against the protocol in the following fashion: The buyer would declare that its value for the item is 10 USD and buy the item. Then, the seller would “cashback” the buyer for 6 USD. The seller ends up with a revenue of 4 , and the buyer with a utility of 1 , instead of 0 in the original situation where the protocol does not let the purchase go through. However, now consider a user with a value of 20 USD. They know the seller’s proclivity to cashbacks, and so decide to declare that they only have a value of 4 USD for the item. Since the miner has no way to differentiate this buyer from the buyer who truly only has a value of 5 , they go forward with the same cashback scheme, i.e., selling the item for effectively 4 USD. The seller has a revenue of 4 , the buyer a utility of 16 , whereas in the original situation both have a utility of 10 . Thus, the collusion was exploitable by users of some type, and we say it is not incentive-compatible. Example 1.2 (A motivating example II, informal) Consider a seller that sells an item through the “tipless mechanism” [ 14 ] , i.e., for some constant price and burn. A disadvantage of the tipless mechanism is that the item is not guaranteed to go to the bidder that values it the most. To mitigate that, the seller decides to hold a second-price auction among all the bidders with bid higher than the posted price. However, the miner can exploit the collusion by submitting additional fake bids, thus raising the payment of the winning colluder. We thus say this suggested collusion is not incentive-compatible (in this case, for the miner). Both examples are captured by our Definitions 2.9 , 2.10 . By imposing the incentive-compatibility restrictions, we require that the collusion is somehow well-designed, or complete, and does not leave out “holes” that can be exploited by the parties to the collusion. However, even an incentive-compatible collusion can be infeasible, as we demonstrate in our final example. Example 1.3 (A motivating example I, revisited) Consider a seller that sells an item to a single buyer. Let us assume that it is defined by a protocol that the item needs to be sold for 10 USD. We want to define an incentive-compatible collusion that allows a buyer with a value of 5 USD for the item to buy it. The format we suggest is the following: Any bidder bids her true value when setting up the collusion mechanism. If the value is 5 USD or more, the bidder bids 10 USD in the actual TFM. The item is then allocated to her (as per the protocol), and the miner cashes her back 5 USD. Unlike Example 1.1 , this collusion mechanism is incentive-compatible because bidders such as the 20 USD value bidder do not need to “fake” their way into the collusion, but they are already incorporated into it. Moreover, we can observe that the collusion in fact maps an incentive-compatible TFM (posted price at 10 USD) into another incentive-compatible TFM (posted price at 5 USD). However, it is still not necessarily a feasible collusion. For the user, it is definitely better to buy the item for 5 USD instead of 10 USD. For the miner, it can sometimes be better, if 5 USD is a better price that allows for higher demand, enough so to compensate for the lower price, but it can also sometimes be worse. This can be decided given a Bayesian distribution over

Read the complete text