{"ID":2840908,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.12456","arxiv_id":"2511.12456","title":"Collusion-proof Auction Design using Side Information","abstract":"Existing auction mechanisms are vulnerable to bidder collusion, which substantially degrades revenue and non-colluder welfare. To design truthful mechanisms resilient to collusion, we introduce a novel approach that leverages a machine learning classifier to predict (even imprecisely) which bidders are colluding. We first establish a Bulow-Klemperer-type result for multi-unit auctions with single-minded bidders, demonstrating that collusion significantly harms existing mechanisms only when the colluding coalition is large. Consequently, we focus our design on settings with many colluders. Building on the welfare-optimal Vickrey-Clarke-Groves (VCG) mechanism, we propose two novel truthful mechanisms: VCG-Posted Price (V-PoP) and Conditional-Posted Price (C-PoP). V-PoP applies VCG to non-colluding bidders and posted prices to colluding ones, and ensuring truthfulness is non-trivial because we must dynamically split the quantity of items between these groups based on the values of the non-colluder bids. C-PoP further advances this by computing a posted price conditioned on non-colluder bids, and ensuring truthfulness is non-obvious because the posted price is chosen using the values of the non-colluder bids. Because real-world classifiers make errors, we provide theoretical lower bounds on the auction price of V-PoP and C-PoP under misclassification, which theory shows acts as a proxy for welfare and revenue. Crucially, our bounds yield actionable insights for classifier design, revealing that false negatives (misclassifying colluders as non-colluders) are preferable to false positives (misclassifying non-colluders as colluders). Numerical experiments demonstrate that our mechanisms achieve high welfare and revenue against collusion, even when utilizing simple, low-cost classifiers.","short_abstract":"Existing auction mechanisms are vulnerable to bidder collusion, which substantially degrades revenue and non-colluder welfare. To design truthful mechanisms resilient to collusion, we introduce a novel approach that leverages a machine learning classifier to predict (even imprecisely) which bidders are colluding. We fi...","url_abs":"https://arxiv.org/abs/2511.12456","url_pdf":"https://arxiv.org/pdf/2511.12456v4","authors":"[\"Sukanya Kudva\",\"Edward Dowling\",\"Anil Aswani\"]","published":"2025-11-16T04:57:20Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"econ.TH\"]","methods":"[]","has_code":false}