Research map / Learning theory and algorithms / Submodular and game algorithms
Weakest Bidder Types and New Core-Selecting Combinatorial Auctions
Siddharth Prasad, Maria Florina Balcan, Tuomas Sandholm
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BPS formulation instead of BO formulation for WT computation (ablation) | constraint generation for WT · CATS, 64 goods/250 bids | run-time GM (s): 7.3 -> 4.0 | Improved |
| use BPS formulation instead of BO formulation for WT computation (ablation) | constraint generation for WT · CATS, 128 goods/500 bids | run-time GM (s): 110.6 -> 46.9 | Improved |
| use BPS formulation instead of BO formulation for WT computation (ablation) | constraint generation for WT · CATS, 128 goods/500 bids | CG iterations GM: 164.2 -> 59.8 | Improved |
| use BPS formulation instead of BO formulation for WT computation (ablation) | constraint generation for WT · CATS, 64 goods/500 bids | CG iterations GM: 102.5 -> 45.8 | Improved |
| increase type space constraint density beta from 0.2 to 0.8 (ablation) | WT computation (BPS) · CATS, K=8 | run-time GM (s): 9.9 -> 15.3 | Hurt |
| increase type space constraint density beta from 0.2 to 0.8 (ablation) | WT computation (BPS) · CATS, K=8 | CG iterations GM: 32.0 -> 75.3 | Hurt |
| vary number of type space constraints K (ablation) | WT computation · CATS | run-time and CG iterations: 19.7 seconds and 42.7 iterations (GM over all K) | No clear effect |
| compute MRC around WT price (WT nearest) instead of around VCG price (vanilla VCG nearest) (ablation) | core-selecting payment rule · CATS, K=8 | run-time GM (s): 1.7 -> 1.0 | Improved |
| increase number of type space constraints K from 1 to 16 (ablation) | WT in the core · CATS | fraction WT in core but VCG not (%): 2.00% -> 4.18% | Improved |
| use WT-based MRC rules (more type space constraints, K up to 16) instead of vanilla MRC (ablation) | MRC(p^WT)-selecting rules · CATS | revenue: nearly closing half the gap between MRC revenue and efficient social welfare at K=16 | Improved |
| use MRC(p^WT) instead of vanilla MRC when K<=8 (ablation) | MRC(p^WT)-selecting rules · CATS | revenue | No clear effect |
| add type space constraints (larger K) to MRC(p^WT) rules (ablation) | MRC(p^WT)-selecting rules · CATS | sum of incentives to deviate | Improved |
Closest papers by meaning
- Machine Learning-Powered Combinatorial Clock Auction (AAAI 2024 · similarity 0.88)
- Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All (ICML 2025 · similarity 0.87)
- Increasing Revenue in Efficient Combinatorial Auctions by Learning to Generate Artificial Competition (AAAI 2025 · similarity 0.87)
- Sample Complexity of Posted Pricing for a Single Item (NeurIPS 2024 · similarity 0.85)
- Procurement Auctions via Approximately Optimal Submodular Optimization (ICML 2025 · similarity 0.85)
- Optimal Auction Design for Mixed Bidders (AAAI 2025 · similarity 0.85)
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.
