Research map / Learning theory and algorithms / Submodular and game algorithms
Efficiency of the First-Price Auction in the Autobidding World
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.
Gives tight price-of-anarchy bounds for first-price auctions when bidders are autobidders (value maximizers), mixed with utility maximizers, and with machine-learned reserves, showing PoA of 1/2 for full autobidding and about 0.457 for mixed settings.
Problem
Efficiency (price of anarchy) of first-price auctions when some or all bidders are ROI-constrained value maximizers (autobidders) rather than quasi-linear utility maximizers.
Approach
Proves PoA of first-price auctions is exactly 1/2 under full autobidding via a proxy-truthful-bid argument over randomized equilibria, and exactly min_t (1+t ln t)/(2-t+t ln t) ≈ 0.457 in mixed settings by combining a local value-payment tradeoff for utility maximizers with a welfare decomposition; machine-learned reserves with accuracy γ raise the bound smoothly toward 1.
Key results
- Full autobidding first-price auction PoA is exactly 1/2 (Theorem 1).
- Mixed autobidding first-price PoA is exactly min_t (1+t ln t)/(2-t+t ln t) ≈ 0.457 (Theorem 2), matched by a 2-bidder, 2-auction instance.
- With machine-learned reserves of accuracy γ, PoA lower bound rises from about 0.457 at γ=0 to 1 at γ=1, approximately linearly (Theorem 3).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a first-price auction instead of a second-price auction | Auctions with mixed autobidders and utility maximizers · Mixed autobidding | price of anarchy: 1/2 -> min_{t∈[0,1]} (1+t ln t)/(2−t+t ln t) ≈ 0.457 | Hurt |
| Use a first-price auction instead of a second-price auction | Auctions with value maximizers only · Full autobidding | price of anarchy: 1/2 -> 1/2 | No clear effect |
| Use machine-learned advice with increasing accuracy to set first-price reserves | First-price auction · Full and mixed autobidding | price of anarchy: about 0.457 to 1 | Helped |
Surprising findings
- In the mixed setting the first-price auction is strictly less efficient than the second-price auction (which has PoA 1/2 with autobidders and 1 with utility maximizers only), the mixed PoA dropping to ≈0.457.
Limitations
- Results are for single-slot auctions with additive values, and the ROI threshold normalized to 1.
- Analysis assumes no restrictions on equilibrium behavior (no no-overbidding), and welfare is liquid welfare benchmark.
- Machine-learned signal model assumes it never overestimates the max value.
Experimental setup
Metrics: price of anarchy
Baselines: Liaw et al. 2022 (deterministic-equilibrium PoA 1/2) Jin and Lu 2022 (1-1/e^2) Balseiro et al. 2021b second-price with reserves
Builds on: Aggarwal et al. 2019 autobidding PoA Jin and Lu 2022 first-price PoA Balseiro et al. 2021b machine-learned reserves Liaw et al. 2022
Closest papers by meaning
- Autobidder's Dilemma: Why More Sophisticated Autobidders Lead to Worse Auction Efficiency (NeurIPS 2024 · similarity 0.93)
- Sample Complexity of Automated Mechanism Design (NeurIPS 2016 · similarity 0.85)
- No-Regret Online Autobidding Algorithms in First-price Auctions (NeurIPS 2025 · similarity 0.85)
- Increasing Revenue in Efficient Combinatorial Auctions by Learning to Generate Artificial Competition (AAAI 2025 · similarity 0.84)
- Optimal Auction Design for Mixed Bidders (AAAI 2025 · similarity 0.84)
- Sample Complexity of Posted Pricing for a Single Item (NeurIPS 2024 · 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.