Winner-Pays-Bid Auctions Minimize Variance

R. Preston McAfee, Renato Paes Leme, Balasubramanian Sivan, Sergei Vassilvitskii

Abstract

While the Revenue Equivalence Theorem (RET) states that many auction formats yield the same expected revenue, their volatility can differ significantly. This paper proves that while "winner-pays-bid" (first-price) auctions are often the most stable choice, they are not always optimal. The authors characterize new mechanisms that further reduce—and in some cases completely eliminate—revenue variance in asymmetric and multi-item markets.

Introduction

In auction theory, the Revenue Equivalence Theorem (RET) is a cornerstone: it suggests that under certain conditions (like independent private values and risk-neutral bidders), different auction formats—like First-Price, Second-Price, or All-Pay—all result in the same expected revenue for the seller.

However, "expected revenue" is just an average. In the real world, sellers (such as governments selling oil leases or digital platforms selling ads) care deeply about revenue risk. High variance in revenue can lead to budget shortfalls or cash flow volatility. While previous research established that the first-price (winner-pays-bid) auction minimizes variance for single-item sales where losers pay nothing (ex-post individual rationality), this paper asks if that optimality holds when we change the rules: What if losers can be charged (as long as they break even on average), or what if we are selling multiple items?

Revenue distributions for Second Price, First Price, and All Pay auctions showing identical means but varying levels of dispersion.

Methodology

The authors employ several sophisticated mathematical tools to move beyond standard single-item models:

  • Revenue Decomposition: They developed a new technique to split the revenue function into two parts: one depending only on a specific bidder’s type and another that vanishes when that bidder makes a payment. This allows them to analyze variance without the restrictive "losers pay nothing" assumption.
  • Fixed-Point Theory: To prove that an optimal payment rule exists for asymmetric bidders (where bidders aren't identical), they used the Schauder fixed-point theorem on a space of probability measures.
  • Differential Equations: For multi-item auctions, they characterized the optimal payment rule as the solution to a first-order linear ordinary differential equation (ODE).
  • Convex Risk Measures: Rather than just looking at variance, they generalized their results to any convex risk measure, making the findings applicable to a wide range of risk-averse seller preferences.

As a theoretical economics paper, the authors evaluate their models using synthetic distributions like Uniform $[0, 1]$ and power distributions ($F(v) = v^2$) to provide concrete examples of variance reduction. For multi-item settings where analytical solutions are difficult, they discretized the uniform distribution and solved a quadratic program to find the variance-minimizing payment rule.

Key Insights and Ideas

The Fragility of the First-Price Auction

The "optimality" of the first-price auction is surprisingly fragile. If bidders are asymmetric (e.g., one bidder's values are generally higher than another's), the first-price auction is no longer the most stable format.

The Power of Negative Correlation

In multi-item auctions, the seller can reduce variance by introducing negative correlation between the payments of different winners. By making one winner pay more when another pays less, the total revenue stays more consistent.

Zero Variance is Possible

One of the most striking findings is that in symmetric multi-item settings, if you allow for interim individual rationality (meaning bidders might lose money in some specific outcomes but expect to profit overall), you can design a mechanism with zero revenue variance. The seller gets the exact same check every time, regardless of the bids.

Key Results

  • Single-Item i.i.d. Stability: The authors confirmed that for identical bidders, the winner-pays-bid format remains optimal for any convex risk measure, even when relaxing participation constraints.
  • Asymmetric Optimality: They characterized a novel auction format for asymmetric bidders that spreads payments across more states of the world to "smooth out" the seller's revenue.
  • The Zero-Variance Mechanism: For $k$ items and $n$ bidders, they constructed a specific payment rule (Theorem 4.2) that implements an efficient allocation while guaranteeing a constant revenue $\bar{R}$ for every auction instance.
  • Numerical Gains: In a 3-bidder, 2-item simulation, they showed that while a standard first-price auction had a second moment of revenue $\approx 0.264$, their optimized mechanism reduced it to $\approx 0.255$.

Limitations and Future Work

While the theoretical results are robust, implementation hurdles remain. The zero-variance mechanism requires bidders to be okay with potentially negative profits in some scenarios (interim IR). In practice, cash-constrained bidders might find this unacceptable. Additionally, while they characterized the multi-item optimal mechanism numerically, a closed-form analytical solution for the ex-post IR case remains elusive.

Future research could explore "position auctions" (like Google Search ads) where the items have different values, and further study how these variance-minimizing rules compare to the famous Vickrey-Clarke-Groves (VCG) mechanism across different risk measures.

Summary updated

BibTeX
@misc{mcafee2024winner,
  author = {R. Preston McAfee and Renato Paes Leme and Balasubramanian Sivan and Sergei Vassilvitskii},
  title = {{Winner-Pays-Bid Auctions Minimize Variance}},
  year = {2024},
  eprint = {2403.04856},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.04856},
}
Figure