Research map / Learning theory and algorithms / Submodular and game algorithms
Increasing Revenue in Efficient Combinatorial Auctions by Learning to Generate Artificial Competition
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces f-VCG auctions that inject artificial competitors into efficient combinatorial auctions to boost revenue under a relaxed (pi, kappa)-IR model, deriving revenue-optimal designs under distributional and quantile knowledge and sample-efficient learning algorithms from bidder data.
Problem
Efficient (welfare-maximizing) combinatorial auctions such as VCG generate very low revenue; the paper asks how an auctioneer can add competition to raise revenue while keeping efficiency, incentive compatibility, and a relaxed individual rationality.
Approach
A new f-VCG auction family prices each bidder against an auctioneer-specified artificial competitor that may depend on other bidders' bids; under a bidder model allowing small overcharges accepted with some probability, the paper derives revenue-optimal efficient designs and instance-adaptive learning algorithms.
Key results
- Under the (pi, kappa)-IR relaxation, the derived revenue-optimal efficient auction keeps efficiency and IC while exceeding WCVCG revenue, with 99% of bidder types unaffected when pi=0.99.
- The Bayesian weakest-competitor auction of Krishna and Perry overcharges bidders with 50% probability in a two-item, two-bidder example, versus the chosen competitor which can cap overcharge frequency at 1-pi.
- Learning algorithms achieve sample complexity O(H^2/epsilon^2 (|B_i| log |B_i| + ln(n/delta))) and produce nearly revenue-optimal auctions with (pi - 2epsilon, kappa)-IR guarantees.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an f-VCG auction with artificial competitors under (π, κ)-IR instead of requiring standard IR | Efficient combinatorial auctions with known bidder value distributions · Bidder value distributions | revenue | Helped |
| Choose artificial competitors using bidder value quantiles | Efficient f-VCG auctions · Bidder value quantiles | revenue | Helped |
| Learn instance-adaptive competitors from historical bidder data | f-VCG auctions with acceptable overcharges · Historical bidder data | revenue | Helped |
| Allow overcharges while requiring bidders to accept them | Efficient f-VCG auctions · Bidders who do not accept overcharges | efficiency | Mixed |
| Use the Bayesian weakest-competitor auction rather than a competitor chosen after seeing other bidders' bids | Two-bidder, two-item example · Example 3.5 | overcharge probability: 50% | Hurt |
Surprising findings
- Bayesian-IR revenue-optimal auctions can overcharge bidders with high frequency (50% in the example), which motivates the frequency-capped IR notion.
Limitations
- Bidder overcharge acceptance model is stylized and assumes acceptance depends only on overcharge amount.
- Learning guarantees assume independent bidder types; correlated types can leave historical data uninformative.
- Revenue optimality holds for acceptable overcharges within f-VCG; general overcharges yield only near-optimal results within the class.
Experimental setup
Metrics: revenue efficiency overcharge frequency
Baselines: VCG WCVCG Bayesian WCVCG
Builds on: VCG auction weakest-competitor VCG Bayesian weakest-competitor VCG (Krishna and Perry 1998) data-driven auction design
Closest papers by meaning
- Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All (ICML 2025 · similarity 0.89)
- Auctionformer: A Unified Deep Learning Algorithm for Solving Equilibrium Strategies in Auction Games (ICML 2024 · similarity 0.88)
- AuctionNet: A Novel Benchmark for Decision-Making in Large-Scale Games (NeurIPS 2024 · similarity 0.88)
- Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response (ICML 2025 · similarity 0.87)
- Machine Learning-Powered Combinatorial Clock Auction (AAAI 2024 · similarity 0.87)
- Learning Optimal Auctions with Correlated Value Distributions (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.