  Multi-unit auctions are a paradigmatic model, where a seller brings multiple
units of a good, while several buyers bring monetary endowments. It is well
known that Walrasian equilibria do not always exist in this model, however
compelling relaxations such as (Walrasian) envy-free pricing do. In this paper
we design an optimal envy-free mechanism for multi-unit auctions with budgets.
When the market is even mildly competitive, the approximation ratios of this
mechanism are small constants for both the revenue and welfare objectives, and
in fact for welfare the approximation converges to 1 as the market becomes
fully competitive. We also give an impossibility theorem, showing that
truthfulness requires discarding resources and, in particular, is incompatible
with (Pareto) efficiency.

Computer Science and Game Theory