Simultaneous 2nd Price Item Auctions with No-Underbidding

Michal Feldman, Galia ShabtaiAAAI 2021 · DOI

Introduction

Simultaneous item auctions, where multiple items are sold concurrently and bidders submit independent bids for each, are widely used due to their simplicity. However, analyzing their efficiency is complex because these auctions are non-truthful; bidders must strategically coordinate their bids across multiple items. The standard metric for evaluating such mechanisms is the Price of Anarchy (PoA), which compares the social welfare of the worst-case equilibrium to the theoretical optimum.

Historically, Simultaneous Second-Price Auctions (S2PA) were considered inferior to their First-Price counterparts (S1PA). Under the standard "No-Overbidding" (NOB) assumption—where bidders do not bid more than their total value for a set—the PoA for S2PA was capped at 1/2 for many common valuation classes. This paper revitalizes the study of S2PA by introducing a realistic behavioral assumption: No-Underbidding (NUB).

The No-Underbidding Assumption

The authors argue that the traditional analysis of S2PA is overly pessimistic because it allows for equilibria where bidders bid significantly below their marginal values. In a second-price auction, bidding below one's marginal value is "weakly dominated," meaning it rarely benefits the bidder and often hurts them. Empirical evidence suggests that real-world participants seldom engage in such behavior.

The paper defines two levels of this assumption:

  1. Item No-Underbidding (iNUB): Bidders do not bid less than their marginal value for items they would win in an optimal allocation.
  2. Set No-Underbidding (sNUB): A stronger condition where the sum of bids on any set of items must at least equal the marginal value of that set.

To analyze these conditions, the authors develop a new framework of $(\gamma, \delta)$-revenue guaranteed auctions. This generalizes the "smoothness" framework in algorithmic game theory, allowing researchers to derive efficiency bounds by relating auction revenue to optimal welfare.

Key Insights: The S2PA vs. S1PA Flip

A major contribution of this work is shifting the perceived hierarchy between auction types. For years, S1PA was favored in theoretical literature because it achieved a PoA of $1 - 1/e \approx 0.63$ for submodular valuations, while S2PA appeared stuck at $0.5$. By incorporating the NUB assumption, the authors demonstrate that S2PA actually achieves a PoA of $2/3 \approx 0.66$, reclaiming its status as a highly efficient mechanism.

Comparison of PoA bounds across different auction formats and assumptions.

The intuition behind this improvement is that NUB naturally drives prices upward. Higher prices act as a barrier to "low-value" bidders, ensuring that items are more likely to be allocated to "high-value" bidders, thereby increasing total social welfare.

Key Results and Valuation Classes

The paper establishes new, often tight, bounds for the Bayesian Price of Anarchy (BPoA) across various valuation classes:

  • Submodular (SM) and XOS Valuations: Under the combined NOB and sNUB assumptions, the PoA improves from $1/2$ to $2/3$.
  • Monotone (MON) Valuations: For the most general class of valuations, the PoA is shown to be at least $1/2$ under sNUB. This is a significant breakthrough, as previous models suggested the PoA could vanish toward zero as the number of items increased.
  • Equilibrium Existence: The authors prove that for XOS valuations, a Pure Nash Equilibrium is guaranteed to exist under these refined conditions.
Detailed PoA bounds for S2PA under various No-Underbidding (NUB) conditions.

Furthermore, the $(\gamma, \delta)$ framework ensures these results are robust, holding even when bidders' values are correlated—a scenario where many previous results failed.

Limitations and Future Directions

While the NUB assumption is theoretically grounded in weak dominance, its practical application assumes bidders can accurately calculate their marginal values. In complex combinatorial settings, this calculation itself may be computationally taxing. Additionally, while the paper provides strong bounds for subadditive valuations, the existence of Pure Nash Equilibria in that class remains a challenge. Future research may explore how these no-underbidding dynamics play out in sequential or iterative auction formats.

Summary updated

BibTeX
@inproceedings{feldman2021simultaneous,
  author = {Michal Feldman and Galia Shabtai},
  title = {{Simultaneous 2nd Price Item Auctions with No-Underbidding}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16679},
}
Figure