Research map / Learning theory and algorithms / Submodular and game algorithms
Machine Learning-Powered Combinatorial Clock Auction
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.
Proposes ML-CCA, an iterative combinatorial auction that uses multiset MVNNs trained only on demand-query responses and a gradient-based price update minimizing a clearing objective, outperforming the CCA in efficiency and clearing rate on SATS spectrum domains.
Problem
Iterative combinatorial auctions commonly rely on value queries, which are cognitively impractical; prior ML-based demand-query designs are computationally intractable in medium domains and discard information from demand responses.
Approach
Train per-bidder multiset monotone-value neural networks (mMVNNs) on demand-query data with a loss based on predicted utility differences, then choose next linear prices by gradient descent on a convex clearing objective W = R(p) + sum_i U(p, v_i), whose minimizers are clearing prices and efficient allocations when linear clearing prices exist.
Key results
- In GSVM, ML-CCA clock-phase efficiency is 98.23% vs 90.40% for CCA, and it clears markets in 56% of instances vs 3% for CCA.
- In LSVM, ML-CCA clock efficiency is 91.64% vs 82.56% for CCA, with clearing in 26% vs 0% of instances.
- In MRVM, ML-CCA outperforms CCA in all three bidding heuristics, though neither mechanism clears the market because linear clearing prices never exist.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace CCA with ML-CCA | clock-bids mechanism · GSVM | efficiency (%): 90.40 -> 98.23 | Helped |
| Replace CCA with ML-CCA | raised-clock-bids mechanism · GSVM | efficiency (%): 93.59 -> 98.93 | Helped |
| Replace CCA with ML-CCA | clock-bids mechanism · LSVM | efficiency (%): 82.56 -> 91.64 | Helped |
| Replace CCA with ML-CCA | raised-clock-bids mechanism · LSVM | efficiency (%): 91.60 -> 96.39 | Helped |
| Replace CCA with ML-CCA | clock-bids mechanism · SRVM | efficiency (%): 99.63 -> 99.59 | Hurt |
| Replace CCA with ML-CCA | raised-clock-bids mechanism · SRVM | efficiency (%): 99.81 -> 99.93 | Helped |
| Replace CCA with ML-CCA | clock-bids mechanism · MRVM | efficiency (%): 92.44 -> 93.04 | Helped |
| Replace CCA with ML-CCA | raised-clock-bids mechanism · MRVM | efficiency (%): 92.62 -> 93.31 | Helped |
| Replace CCA with ML-CCA | mechanism · GSVM | instances with clearing prices (%): 3 -> 56 | Helped |
| Replace CCA with ML-CCA | mechanism · LSVM | instances with clearing prices (%): 0 -> 26 | Helped |
| Replace CCA with ML-CCA | mechanism · SRVM | instances with clearing prices (%): 8 -> 13 | Helped |
| Replace CCA with ML-CCA | mechanism · MRVM | instances with clearing prices (%): 0 -> 0 | No clear effect |
Surprising findings
- In MRVM, linear clearing prices never exist, so neither ML-CCA nor CCA can clear the market, yet ML-CCA still achieves higher efficiency.
Limitations
- Assumes myopic best-response (truthful) bidding; the mechanism is not strategyproof and incentive issues are treated as orthogonal.
- Per-round computation is substantial (up to ~45 minutes on 8 CPU cores) because next-price generation requires solving MILPs and is not GPU-implementable.
- Linear clearing prices may not exist (as in MRVM), so the market cannot clear in such domains.
Experimental setup
Datasets: SATS spectrum auction test suite (GSVM, LSVM, SRVM, MRVM) synthetic instances
Benchmarks: SATS GSVM SATS LSVM SATS SRVM SATS MRVM
Metrics: efficiency (clock bids) efficiency (raised clock bids) efficiency (profit max bids) clearing rate
Baselines: CCA CCA with raised clock bids CCA with profit max bids
Builds on: MVNN combinatorial clock auction Brero et al. ML-based demand query design SATS spectrum auction test suite
Closest papers by meaning
- Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All (ICML 2025 · similarity 0.95)
- Increasing Revenue in Efficient Combinatorial Auctions by Learning to Generate Artificial Competition (AAAI 2025 · similarity 0.87)
- BundleFlow: Deep Menus for Combinatorial Auctions by Diffusion-Based Optimization (NeurIPS 2025 · similarity 0.86)
- AuctionNet: A Novel Benchmark for Decision-Making in Large-Scale Games (NeurIPS 2024 · similarity 0.85)
- Predicting Real-World Penny Auction Durations by Integrating Game Theory and Machine Learning (AAAI 2024 · similarity 0.84)
- Learning Optimal Auctions with Correlated Value Distributions (AAAI 2025 · similarity 0.84)
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.