Research map / Learning theory and algorithms / Submodular and game algorithms
Procurement Auctions via Approximately Optimal Submodular Optimization
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 distorted greedy achieves (1-e^{-β}, β+o(1)) bi-criteria welfare guarantees for all β and converts submodular optimization algorithms into IC, IR, NAS procurement mechanisms (sealed-bid, online, and descending auctions), evaluated on a SNAP coverage problem.
Problem
Designing computationally efficient procurement auctions that maximize welfare f(S) minus total seller cost while being incentive compatible, individually rational, and running non-negative auctioneer surplus, for monotone submodular valuations.
Approach
Improves the analysis of distorted greedy to hold simultaneously for all β, and provides a general payment-rule framework that turns any submodular-maximization scoring rule satisfying mild monotonicity assumptions into an IC, IR, NAS mechanism, extended to online posted-price mechanisms and adversarial descending auctions.
Key results
- Distorted greedy achieves (1-e^{-β}, β+o(1)) bi-criteria welfare guarantee simultaneously for all β in [0,1], matching the known Pareto frontier up to o(1).
- Descending auction with a cost-scaled greedy demand oracle achieves (1/2, 1) bi-criteria welfare approximation even in the adversarial setting, whereas an exact demand oracle can be arbitrarily worse (O(1/L) of optimum).
- In experiments on coverage instances with up to 4000 sellers, direct implementations outperform their descending-auction variants, with ordering Greedy-margin > Greedy-rate > Cost-scaled Greedy > Distorted Greedy in welfare.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use direct implementations instead of descending-auction variants | Greedy-margin, Greedy-rate, Cost-scaled Greedy, and Distorted Greedy · SNAP wiki-Vote coverage instances | welfare | Helped |
| Use the optimal demand oracle instead of approximation-algorithm oracles | Descending Auction · SNAP wiki-Vote coverage instances where feasible | welfare | Helped |
| Use Greedy-margin rather than Greedy-rate | Direct greedy mechanisms · SNAP wiki-Vote coverage instances | welfare | Helped |
| Use Greedy-rate rather than Cost-scaled Greedy | Direct greedy mechanisms · SNAP wiki-Vote coverage instances | welfare | Helped |
| Use Cost-scaled Greedy rather than Distorted Greedy | Direct greedy mechanisms · SNAP wiki-Vote coverage instances | welfare | Helped |
| Use a cost-scaled-greedy demand oracle instead of an exact demand oracle | Descending Auction in the adversarial setting · Submodular procurement instances | welfare: < 1; >= L/2 - 1 | Mixed |
| Use distorted greedy with the parameterized analysis for all β instead of the prior stated guarantee | Distorted Greedy · Regularized submodular maximization | bi-criteria welfare guarantee: (1-1/e,1) -> (1-e^{-β}, β + o(1) | Helped |
| Use the stochastic distorted-greedy implementation | Stochastic Distorted Greedy · Regularized submodular maximization | oracle calls | Helped |
| Use the stochastic distorted-greedy implementation instead of deterministic distorted greedy | Distorted Greedy · Regularized submodular maximization | bi-criteria welfare guarantee | No clear effect |
| Use cost-scaled greedy rather than an exact demand oracle | Descending Auction in the adversarial setting · Submodular procurement instances | bi-criteria welfare guarantee: (1, 1) -> (1/2, 1) | Helped |
| Use greedy-based algorithms rather than VCG, Descending Auction, or Optimal Welfare MIP implementations | Procurement mechanisms · SNAP wiki-Vote coverage instances | running time | Helped |
| Use Distorted Greedy rather than other greedy-based algorithms | Distorted Greedy · SNAP wiki-Vote coverage instances | running time | Hurt |
Surprising findings
- With an exact demand oracle, descending auctions in the adversarial setting can perform arbitrarily worse than with a cost-scaled greedy oracle.
- Distorted Greedy has the worst welfare among the tested approximation algorithms despite its stronger worst-case guarantee.
Limitations
- Descending auction with exact oracle has arbitrarily bad worst-case welfare in adversarial setting.
- Assumptions on the scoring rule (monotone in bid, bid-threshold, bid-independence) must hold for the framework to apply.
- Whether online submodular algorithms can achieve bi-criteria (alpha,1) with alpha > 1/2 is left open.
Experimental setup
Datasets: SNAP wiki-Vote
Benchmarks: SNAP wiki-Vote-derived coverage instances
Metrics: welfare running time
Baselines: VCG Optimal Welfare Descending Auction with optimal oracle Greedy-margin Greedy-rate Cost-scaled Greedy
Builds on: distorted greedy VCG cost-scaled greedy stochastic distorted greedy
Closest papers by meaning
- Budget-Feasible Mechanisms for Submodular Welfare Maximization in Procurement Auctions (ICML 2026 · similarity 0.92)
- Procurement Auctions with Predictions: Improved Frugality for Facility Location (NeurIPS 2025 · similarity 0.87)
- Mechanism Design via the Interim Relaxation (NeurIPS 2025 · similarity 0.86)
- Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits (NeurIPS 2024 · similarity 0.86)
- Sample Complexity of Posted Pricing for a Single Item (NeurIPS 2024 · similarity 0.85)
- Increasing Revenue in Efficient Combinatorial Auctions by Learning to Generate Artificial Competition (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.