Collusion-proof Auction Design using Side Information

Sukanya Kudva and Anil Aswani

Papers from arXiv.org

Abstract: We study the problem of auction design in the presence of bidder collusion. Specifically, 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. While the classical Vickrey-Clarke-Groves (VCG) mechanism achieves efficient and truthful outcomes, it is highly vulnerable to collusion. In contrast, fully collusion-proof mechanisms are limited to posted-price formats, which fail to guarantee even approximate efficiency. This paper aims to bridge this gap by designing auctions that achieve good welfare and revenue guarantees even when some bidders collude. We first characterize the strategic behavior of colluding bidders under VCG and prove that such bidders optimally bid shade: they never overbid or take additional items, but instead reduce the auction price. This characterization enables a Bulow-Klemperer type result: adding colluding bidders can only improve welfare and revenue relative to running VCG on the non-colluding group alone. We then propose a Hybrid VCG (H-VCG) mechanism that combines VCG applied to non-colluding bidders with a posted-price mechanism for colluding bidders, assuming access to a black-box collusion detection algorithm. We show that H-VCG is ex-post dominant-strategy incentive compatible (DSIC) and derive probabilistic guarantees on expected welfare and revenue under both known and unknown valuation distributions. Numerical experiments across several distributions demonstrate that H-VCG 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, offering a step toward collusion-resistant auctions.

Date: 2025-11
New Economics Papers: this item is included in nep-com, nep-des, nep-inv, nep-mic and nep-reg
References: Add references at CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2511.12456 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2511.12456

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().