# Efficiency Guarantees in Auctions with Budgets

arXiv: https://arxiv.org/abs/1304.7048 · HTML: https://mlsanity.com/paper/1304.7048/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2013.

## Built on by (most cited first, 5 of 5)

- [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Robust Allocations with Diversity Constraints](https://mlsanity.com/paper/2109.15015/) (2021)
- [Model Monotonicity in Autobidding Auctions: When Do Better Predictions Lead to Better Outcomes?](https://mlsanity.com/paper/2605.31036/) (2026)
- [An Algorithmic Introduction to Savings Circles](https://mlsanity.com/paper/2203.12486/) (2022)

## Abstract (arXiv)

In settings where players have a limited access to liquidity, represented in the form of budget constraints, efficiency maximization has proven to be a challenging goal. In particular, the social welfare cannot be approximated by a better factor then the number of players. Therefore, the literature has mainly resorted to Pareto-efficiency as a way to achieve efficiency in such settings. While successful in some important scenarios, in many settings it is known that either exactly one incentive-compatible auction that always outputs a Pareto-efficient solution, or that no truthful mechanism can always guarantee a Pareto-efficient outcome. Traditionally, impossibility results can be avoided by considering approximations. However, Pareto-efficiency is a binary property (is either satisfied or not), which does not allow for approximations. In this paper we propose a new notion of efficiency, called liquid welfare. This is the maximum amount of revenue an omniscient seller would be able to extract from a certain instance. We explain the intuition behind this objective function and show that it can be 2-approximated by two different auctions. Moreover, we show that no truthful algorithm can guarantee an approximation factor better than 4/3 with respect to the liquid welfare, and provide a truthful auction that attains this bound in a special case. Importantly, the liquid welfare benchmark also overcomes impossibilities for some settings. While it is impossible to design Pareto-efficient auctions for multi-unit auctions where players have decreasing marginal values, we give a deterministic O(log n)-approximation for the liquid welfare in this setting.