Deterring A Small Collusion is All You Need

Transaction Fee Mechanisms (TFMs) study auction design in the Blockchain context, and emphasize robustness against miner and user collusion, moreso than traditional auction theory. [8] introduce the notion of a mechanism being 𝑐-Side-Contract-Proof (𝑐-SCP), i.e., robust to a collusion of the miner and 𝑐 users. Later work [7, 18] shows a gap between the 1-SCP and 2-SCP classes. We show that the class of 2-SCP mechanisms equals that of any 𝑐-SCP with 𝑐 ≥ 2, under a relatively minor assumption of consistent tie-breaking. In essence, this implies that any mechanism vulnerable to collusion, is also vulnerable to a small collusion. CCS Concepts: • Theory of computation → Computational pricing and auctions; Algorithmic mechanism design; Solution concepts in game theory.