99% Revenue with Constant Enhanced Competition

Linda Cai, Raghuvansh R. Saxena

Abstract

Designing optimal multi-item auctions is a central challenge in algorithmic game theory, often hindered by the mathematical complexity and computational intractability of optimal mechanisms. This paper addresses the "enhanced competition" paradigm: determining how many additional bidders are required for a simple auction to match the revenue of an optimal auction. We prove that for any auction selling $m$ items to $n$ bidders, a simple auction with $O(n)$ bidders can capture at least a $(1 - \epsilon)$ fraction of the optimal revenue. Crucially, this result is independent of the number of items $m$, resolving a long-standing open problem where previous bounds scaled with $\log m$. Our approach utilizes a novel duality-based benchmark and a "ghost bidder" technique to maintain statistical independence in virtual value calculations.

Introduction

In 1981, Roger Myerson solved the problem of revenue-optimal auctions for a single item. However, when an auctioneer seeks to sell multiple items to multiple bidders, the problem becomes significantly more difficult. Optimal multi-item auctions often require complex randomization, exhibit non-monotonic behaviors, and are generally impractical for real-world implementation.

To bridge the gap between theoretical optimality and practical simplicity, researchers study "enhanced competition." This paradigm, popularized by Bulow and Klemperer (1996), asks: How many extra bidders must be invited to a simple auction to ensure its revenue meets or exceeds that of an optimal auction with the original number of bidders? While it was known that a single extra bidder suffices for single-item auctions, multi-item scenarios with $n > 1$ bidders previously required the number of extra bidders to scale with the number of items ($m$). This paper demonstrates that the number of items is irrelevant to the competition requirement, proving that a constant factor of extra bidders relative to $n$ is sufficient.

Methodology: Bypassing the Core-Tail Decomposition

Previous attempts to bound multi-bidder revenue relied on "core-tail decomposition," a technique that separates bidders' valuations into high and low ranges. However, this method fails for $n > 1$ because the distribution of the "core" becomes dependent on the total number of bidders, which breaks the statistical independence required for robust mathematical proofs.

The Independent Utilities (IU) Benchmark

To overcome this, the authors develop a new duality-based revenue benchmark called Independent Utilities (IU). This framework allows for a more granular analysis of revenue without the dependencies introduced by traditional decomposition.

The Ghost Bidder Technique

To ensure that virtual value calculations remain independent of the total number of participants ($n'$), the authors introduce "ghost bidders." For every real bidder in the auction, the mechanism samples a set of imaginary ghost bidders and simulates a second-price auction. By calculating virtual values based on a bidder’s performance against these ghosts rather than the actual competitors, the authors decouple the valuation distributions from the auction size. This maintains the strict independence properties necessary to prove revenue bounds that do not scale with $m$.

Key Insights

  1. Independence as a Bottleneck: The primary obstacle in multi-bidder auction theory was the coupling of virtual welfare and participant count. The ghost bidder technique serves as an elegant mathematical "hack" to restore independence.
  2. The Power of Simple Auctions: The research reveals a surprising dichotomy. In scenarios with $O(n)$ bidders, either a standard VCG auction captures nearly all (99%) of the optimal revenue, or a simple mechanism (such as selling items separately or implementing an entry fee) actually outperforms the optimal $n$-bidder auction.
  3. Prior-Independence: For "regular" distributions, the authors show that the auctioneer does not need to know the buyers' valuation distributions beforehand. By using the bids of a single "special" bidder to estimate market conditions, the mechanism can set near-optimal prices for the remaining participants.

Results

  • Theorem 1.1 (Main Result): For any auction selling $m$ items to $n$ bidders, an auctioneer can capture at least a $(1 - \epsilon)$ fraction of the optimal revenue by running a simple auction with $n' = O(n/\epsilon)$ bidders. This requirement is entirely independent of $m$.
  • Theorem 1.2 (Prior-Independent Guarantee): If item distributions are regular, a prior-independent VCG auction with an entry fee using $O(n/\epsilon)$ bidders will match or exceed the optimal $n$-bidder revenue.

Limitations and Future Directions

While the theoretical results are robust, the constant factor $O(n/\epsilon)$ can be large. For instance, achieving 99% revenue might require a multiplier of $20n/\epsilon$, which could translate to thousands of bidders in practice. Additionally, while prior-independence is achieved for regular distributions, the mechanism for irregular distributions still requires knowledge of the prior. Future work may focus on extending these prior-independent results to broader classes of irregular distributions by integrating the IU-benchmark with emerging techniques in mechanism design.

Summary updated

Abstract

The enhanced competition paradigm is an attempt at bridging the gap between simple and optimal auctions. In this line of work, given an auction setting with m items and n bidders, the goal is to find the smallest n' ≥ n such that selling the items to n' bidders through a simple auction generates (almost) the same revenue as the optimal auction. Recently, Feldman, Friedler, and Rubinstein [EC, 2018] showed that an arbitrarily large constant fraction of the optimal revenue from selling m items to single bidder can be obtained via simple auctions with a constant number of bidders. However, their techniques break down even for two bidders, and can only show a bound of n' = O(n · łog m/n).Our main result is that n' = O(n) bidders suffices for all values of m and n. That is, we show that, for all m and n, an arbitrarily large constant fraction of the optimal revenue from selling m items to n bidders can be obtained via simple auctions with O(n) bidders. Moreover, when the items are regular, we can achieve the same result through auctions that are prior-independent, i.e., they do not depend on the distribution from which the bidders' valuations are sampled.
BibTeX
@inproceedings{cai2021revenue,
  author = {Linda Cai and Raghuvansh R. Saxena},
  title = {{99\% Revenue with Constant Enhanced Competition}},
  booktitle = {EC},
  year = {2021},
  url = {https://openreview.net/forum?id=Q7ldmZwWBB},
}
Figure