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.
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%.
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