Collusion-proof Auction Design using Side Information

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.