Strengthening Bulow-Klemperer-Style Results for Multi-Unit Auctions

Moshe Babaioff, Yiding Feng, Zihan Luo

Abstract

The classic result of Bulow and Klemperer (1996) shows that in multi-unit auctions with $m$ units and $n \geq m$ buyers whose values are sampled i.i.d. from a regular distribution, the revenue of the VCG auction with $m$ additional buyers is at least as large as the optimal revenue. Unfortunately, for regular distributions, adding $m$ additional buyers is sometimes indeed necessary, so the "competition complexity" of the VCG auction is $m$. We seek proving better competition complexity results in two dimensions. First, under stronger distributional assumptions, the competition complexity of VCG auction drops dramatically. In balanced markets (where $m=n$) with MHR distributions, it is sufficient to only add $(e^{1/e} - 1 + o(1))n \approx 0.4447n$ additional buyers to match the optimal revenue—less than half the number that is necessary under regularity—and this bound is asymptotically tight. Second, we analyze a supply-limiting variant of VCG auction that caps the number of units sold in a prior-independent way. Whenever the goal is to achieve almost the optimal revenue, this mechanism strictly improves upon standard VCG auction, requiring significantly fewer additional buyers.

Introduction

In auction theory, revenue maximization typically requires the seller to have precise knowledge of the buyers' valuation distributions to set optimal reserve prices. The Bulow-Klemperer (BK) theorem provides a powerful alternative: "competition is better than optimization." It states that in a market with $m$ units, a standard, prior-independent VCG auction with $m$ additional buyers will outperform the optimal mechanism run on the original set of buyers.

While elegant, this $m$-buyer requirement is a worst-case bound for the broad class of regular distributions. In many practical scenarios, doubling the number of buyers is impractical. This research explores how stronger distributional assumptions and simple mechanism refinements can reduce this "competition complexity."

Methods and Technical Approach

The authors move beyond general regular distributions to focus on Monotone Hazard Rate (MHR) distributions (e.g., Normal, Exponential) and $\lambda$-regular distributions. They also introduce the Supply-Limiting VCG auction, which caps the number of units sold at $s \le m$ based only on market size, maintaining prior-independence while mimicking the supply-withholding behavior of optimal mechanisms.

Central to the analysis is a unified worst-case reduction. The authors prove that for any market size and regularity level, the most challenging distribution for the auctioneer belongs to the family of truncated $\lambda$-generalized Pareto distributions. This reduction allows for both precise numerical calculations for finite markets and closed-form asymptotic formulas.

Key Results

Impact of Distributional Assumptions

Under MHR assumptions, the competition complexity drops significantly. In a balanced market ($m=n$), the number of extra buyers needed is reduced from $n$ to approximately $0.4447n$. As the market becomes more imbalanced (fewer units relative to buyers), the gains become even more pronounced.

Asymptotic competition complexity (CC) as a function of market imbalance $\alpha = m/n$ for different distribution classes. The black line represents regular distributions, while the grey lines show the reduced complexity for $\lambda$-regular and MHR distributions.

The Power of Supply-Limiting VCG

Standard VCG is often "too efficient," selling all units even when withholding supply would increase revenue. The Supply-Limiting VCG auction addresses this by strategically capping supply. This refinement is particularly powerful when the goal is to achieve a high fraction (e.g., 95%) of optimal revenue rather than 100%.

Comparison of competition complexity between standard VCG (solid lines) and supply-limiting VCG (dashed lines) for varying target revenue fractions $\Gamma$. The dashed lines show a significant reduction in the required number of additional buyers to reach near-optimal revenue.

As shown in the figure above, to achieve 80% of optimal revenue in a balanced MHR market, standard VCG requires 34.2% extra buyers, whereas Supply-Limiting VCG requires only 15.6%.

Conclusion

This work demonstrates that the classic Bulow-Klemperer bounds are often overly pessimistic. By accounting for more realistic distributional properties like MHR or by implementing a simple supply cap, sellers can achieve near-optimal revenue with far less additional competition than previously thought. Future work may extend these results to non-identical distributions or more complex combinatorial auction settings.

Summary updated

Abstract

The classic result of Bulow and Klemperer (1996) shows that in multi-unit auctions with $m$ units and $n\geq m$ buyers whose values are sampled i.i.d. from a regular distribution, the revenue of the VCG auction with $m$ additional buyers is at least as large as the optimal revenue. Unfortunately, for regular distributions, adding $m$ additional buyers is sometimes indeed necessary, so the "competition complexity" of the VCG auction is $m$. We seek proving better competition complexity results in two dimensions. First, under stronger distributional assumptions, the competition complexity of VCG auction drops dramatically. In balanced markets (where $m=n$) with MHR distributions, it is sufficient to only add $(e^{1/e} - 1 + o(1))n \approx 0.4447n$ additional buyers to match the optimal revenue -- less than half the number that is necessary under regularity -- and this bound is asymptotically tight. We provide both exact finite-market results for small value of $n$, and closed-form asymptotic formulas for general market with any $m\leq n$, and any target fraction of the optimal revenue. Second, we analyze a supply-limiting variant of VCG auction that caps the number of units sold in a prior-independent way. Whenever the goal is to achieve almost the optimal revenue, this mechanism strictly improves upon standard VCG auction, requiring significantly fewer additional buyers. Together, our results show that both stronger distributional assumptions, as well as a simple prior-independent refinement to the VCG auction, can each substantially reduce the number of additional buyers that is sufficient to achieve (near-)optimal revenue. Our analysis hinges on a unified worst-case reduction to truncated generalized Pareto distributions, enabling both numerical computation and analytical tractability.
BibTeX
@misc{babaioff2026strengthening,
  author = {Moshe Babaioff and Yiding Feng and Zihan Luo},
  title = {{Strengthening Bulow-Klemperer-Style Results for Multi-Unit Auctions}},
  year = {2026},
  eprint = {2602.11959},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.11959},
}
Figure