Collusion-proof Auction Design using Side Information
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915990218997760 |
|---|---|
| author | Kudva, Sukanya Dowling, Edward Aswani, Anil |
| author_facet | Kudva, Sukanya Dowling, Edward Aswani, Anil |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_12456 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Collusion-proof Auction Design using Side Information Kudva, Sukanya Dowling, Edward Aswani, Anil Computer Science and Game Theory Theoretical Economics 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. |
| title | Collusion-proof Auction Design using Side Information |
| topic | Computer Science and Game Theory Theoretical Economics |
| url | https://arxiv.org/abs/2511.12456 |