On-chain Sybil-proofness and Collusion Resistance
Problem Statement
Due to their permissionless nature, on-chain mechanisms operate in a much more adversarial environment than traditional mechanism design. This makes concerns around sybil-proofness and collusion resistance a first-order concern for on-chain mechanisms. This RFP looks to increase our understanding of how requiring sybil-proofness and collusion-resistance influences the set of mechanisms we can use and the set of problems we can address in a permissionless manner. A proposal could take one of many forms:
- A SOK on the the different notions of sybil-proofness and collusion resistance defined in theory and how those notions relate to mechanisms that are used in practice
- A theoretical result showing reductions between different notions and/or results on how efficient mechanisms can be in different regimes
- New definitions that adapt previous notions in traditional mechanism design that are more tractable and applicable for a Defi context
Background
Sybil-Proofness
A mechanism is sybil-proof if agents don’t have an incentive to submit bids under multiple identities. This notion was first introduced as “false-name proofness” in (Yoko 2000) where they studied how sybils affect combinatorial auctions. It turns out the ability of agents to sybil breaks many of the guarantees of traditional strategy-proof mechanisms for combinatorial auctions, and they further shows the inability of any sybil-proof mechanism to achieve good efficiency for certain instances. We note there is a distinction between agents being allowed to have multiple identities and the auctioneer themselves submitting fake bids. A mechanism might be resistant to the agents sybiling but not the auctioneer sybiling. This for instance is the case for second-price auctions. We distinguish a mechanism that is resistant against the auctioneer from benefiting by submitting bids from fake identities as being shill-proof. One question of interest is under what conditions shill-proofness implies sybil-proofness and vice versa. Broadly we seek to understand under what conditions it is possible to implement a sybil-proof mechanism. For cases where it is not possible, are there ways to weaken the definition of sybil-proofness to make those instances tractable?
Of separate interest is considering the power of sybils when the auction has a maximum capacity of bidders it can support. This has come up recently in Solana where rather than directly competing in the auction for transaction inclusion, agents have been sybiling to fill up the queue of bids to be considered. This can be used by these agents to decrease the competitiveness of the auction since the auction doesn’t charge for their losing bids. This raises the question of how to address these types of attacks. One option is to impose entry fees to submit bids to the auction, although this too can reduce the competitiveness of the auction. We consider the best mechanism design for addressing these kind of attacks an interesting open problem.
Collusion-Resistance
The traditional notions of collusion resistance in the mechanism design literature are weak group strategyproofness (WGSP) and strong group strategyproofness (SGSP). For a mechanism to be WGSP, no coalition of agents can deviate from truthful bidding and have every member of the coalition receive strictly greater value than what they would have received bidding truthfully. SGSP is stronger and requires that no coalition of agents can deviate from truthful bidding while having that at least one agent receives strictly greater value and the other agents receive at least as much value as they would have received biding truthfully. Intuitively these notions capture a mechanism being resistant to agents profiting from collusion while requiring no transfers (WGSP) or only a small amount of transfers (SGSP) between themselves after interacting with the mechanism. Mechanisms that are SGSP are also WGSP which are in turn DSIC. As one might imagine, this makes these notions quite strong, and in general few mechanisms satisfy these properties.
Blockchains allow for easier ways of collusion than in traditional mechanism design, so notions such as offchain agreement proof (OCA-proof) and side contract proofness (SCP) have been proposed that at a high level require there be no way for the joint utility of colluding agents and the auctioneer be higher than bidding truthfully. These notions are generally more restrictive than WGSP and SGSP as they allow the auctioneer to also be part of the colluding coalition and instead of requiring pointwise increases in agent utilities, they allow for agent utilities to potentially be lower when directly interacting with the mechanism but higher with transfers ex-post. While these notions fully capture the range of collusion amongst agents, there are also very few mechanisms that satisfy these conditions. Thus it is interesting whether there are ways to weaken these notions while having mechanisms that are still robust against collusion in practice.
While sybil-proofness and collusion resistance are interesting in their own right, we are particularly interested in when it is possible to achieve both simultaneously. Sybil-proofness looks similar to collusion resistance since it effectively requires that there is no way for an agent to profit by colluding with value 0 bidders. We seek to understand how precise we can make this connection, e.g. are there conditions under which sybil-proofness is equivalent to WGSP?
Related Papers
Here is a sampling of the flavor of paper we seek for this RFP and places to draw inspiration from:
Collusive bidder behavior at single-object second-price and english auctions
The Cost of Sybils, Credible Commitments, and False-Name Proof Mechanisms
The effect of false-name bids in combinatorial auctions: new fraud in internet auctions
