Research map / Learning theory and algorithms / Submodular and game algorithms
Procurement Auctions with Predictions: Improved Frugality for Facility Location
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.
Shows VCG has frugality ratio exactly 3 for strategic uncapacitated facility location, and designs learning-augmented truthful auctions (PredictedLimits, ErrorTolerant) with consistency 1+epsilon and bounded robustness.
Problem
Designing truthful procurement auctions for strategic uncapacitated facility location that minimize frugality ratio (total payments plus connection cost relative to the second-best solution), with and without predictions of owners' private opening costs.
Approach
Tight analysis of VCG frugality via a rerouting argument, then a learning-augmented auction that scales up reported costs for the predicted optimal set (and per-facility inflation when bids exceed predictions), so payments are reduced when predictions are accurate while staying robust otherwise; an error-tolerant variant downscales the predicted solution under bounded error.
Key results
- VCG has frugality ratio exactly 3 for metric UFL (previous best upper bound was 4, lower bound 3 - 6/(|L|+1) on tree metrics).
- PredictedLimits is truthful, (1+epsilon)-consistent and max{5, 3+2/epsilon}-robust for epsilon in (0,2].
- ErrorTolerant achieves eta(1+lambda)+2epsilon frugality when prediction error eta <= lambda, and max{2lambda^4+3lambda^2, 3+2/epsilon} otherwise.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Tighten the VCG frugality analysis and establish a matching lower bound | VCG for metric UFL · Metric UFL | frugality ratio: 4 -> 3 | Helped |
| Use accurate cost predictions to scale up costs in the predicted optimal set | PredictedLimits · Metric UFL, accurate predictions | frugality ratio: 1+\epsilon | Helped |
| Use predictions to scale up costs in the predicted optimal set | PredictedLimits · Metric UFL, arbitrary prediction errors | frugality ratio: \max\left\{5, 3 + \frac{2}{\epsilon}\right\} | Helped |
| Add error-tolerance parameter \lambda and whole-solution downscaling | ErrorTolerant · Metric UFL, prediction error \eta \le \lambda | frugality ratio: \eta(1+\lambda)+2\epsilon | Helped |
| Add error-tolerance parameter \lambda and whole-solution downscaling | ErrorTolerant · Metric UFL, prediction error \eta > \lambda | frugality ratio: \max\left\{\,2\lambda^4+3\lambda^2,\;3+\tfrac{2}{\epsilon}\right\} | Helped |
Surprising findings
- Scaling up (rather than down) the predicted optimal solution's costs is used deliberately, to limit overbidding and thus payments, contrary to standard prediction-based scaling.
Experimental setup
Metrics: frugality ratio consistency robustness
Baselines: VCG auction
Builds on: VCG auction Myerson's lemma algorithms with predictions
Closest papers by meaning
- Procurement Auctions via Approximately Optimal Submodular Optimization (ICML 2025 · similarity 0.87)
- Randomized Strategic Facility Location with Predictions (NeurIPS 2024 · similarity 0.85)
- Learning-Augmented Online Bidding in Stochastic Settings (NeurIPS 2025 · similarity 0.85)
- Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games (AAAI 2025 · similarity 0.84)
- Safely Learning Optimal Auctions: A Testable Learning Framework for Mechanism Design (ICML 2025 · similarity 0.84)
- Increasing Revenue in Efficient Combinatorial Auctions by Learning to Generate Artificial Competition (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.