Collusion-proof Auction Design using Side Information
This addresses auction design under collusion, a key issue in economics and AI, by providing a framework that integrates collusion detection, though it is incremental in combining existing mechanisms with detection algorithms.
The paper tackles the problem of designing collusion-proof auctions for multi-unit items by leveraging side information about colluding bidders, resulting in a VCG Posted Price (V-PoP) mechanism that improves welfare and revenue, with numerical experiments showing it outperforms baseline methods and approaches ideal performance.
We consider a multi-unit auction of identical items with single-minded bidders, where a subset of bidders may collude by coordinating bids and transferring payments and items among themselves. Classical collusion-proof mechanisms are largely restricted to posted-price formats, which fail to guarantee even approximate efficiency. We therefore adopt a learning-augmented approach to leverage side information about which bidders are colluding and obtain improved welfare and revenue guarantees. In our setting, colluding bidders optimally shade their bids to suppress prices. Using this characterization, we establish a Bulow-Klemperer type result showing that recruiting more honest bidders is better than the best collusion-proof auction mechanism. We then consider a setting in which a black-box collusion detection algorithm labels bidders as colluding or non-colluding, and propose a VCG Posted Price (V-PoP) mechanism that applies VCG to non-colluding bidders and posted prices to colluding bidders. We show that V-PoP is ex-post dominant-strategy incentive compatible (DSIC) even when it uses select bidder information to calculate an optimal split of items between the subgroups. Additionally, we derive probabilistic guarantees on expected welfare and revenue under both known and unknown valuation distributions, and analyze the robustness of V-PoP to bidder misclassification errors. Numerical experiments across several distributions demonstrate that V-PoP consistently outperforms VCG restricted to non-colluding bidders and approaches the performance of the ideal VCG mechanism assuming universal truthfulness. Our results provide a principled framework for incorporating collusion detection into mechanism design, advancing the theory of auctions under collusion.