Combinatorial Auctions via Posted Prices

Michal Feldman, Nick Gravin, Brendan Lucier

TL;DR

This paper proves that simple, non-discriminatory posted prices can achieve at least 50% of the maximum possible social welfare in complex combinatorial auctions. By setting item prices based on their expected contribution to the optimal allocation, the authors provide the first computationally efficient and incentive-compatible mechanism for a wide class of buyer preferences (XOS valuations).

What Problem Does This Paper Address?

In market design, the "holy grail" is an auction that is efficient (allocates goods to those who value them most), computationally tractable, and easy for participants to understand. Combinatorial auctions—where buyers want bundles of different items (like spectrum licenses or cloud computing slots)—are notoriously difficult.

The gold standard for truthfulness, the VCG mechanism, is often computationally impossible to run. Conversely, simple "posted price" mechanisms (like a grocery store where you just see a price and decide what to buy) are easy to use and inherently "truthful," but they were long thought to be highly inefficient when buyers have complex, overlapping preferences and the seller doesn't know exactly how much each buyer values the items (the Bayesian setting).

The authors ask: Can we use simple, anonymous posted prices to approximate the optimal social welfare in these complex settings?

Methods

The authors focus on a Bayesian framework where the seller knows the distribution of buyer valuations but not the actual values. They propose a mechanism with four stages:

  1. Pricing: The seller sets a price for each item.
  2. Ordering: Buyers arrive in an arbitrary (even adversarial) order.
  3. Realization: Buyers learn their own private values.
  4. Consumption: Each buyer takes their favorite bundle of remaining items, paying the posted prices.

The core technical innovation is the Price Computation Algorithm. Inspired by "prophet inequalities" from optimal stopping theory, the authors suggest setting the price of an item to roughly half of its expected contribution to the optimal social welfare.

To make this practical, they show that if you have "black-box" access to an algorithm that can solve the underlying allocation problem (even approximately) and can sample from the valuation distributions, you can compute these prices in polynomial time.

Datasets

As a theoretical paper in computer science and economics, this work does not use empirical datasets. Instead, it provides mathematical proofs and algorithmic analysis that hold across any probability distributions that satisfy certain structural properties (like submodularity or XOS).

Key Insights and Ideas

  • Sequentiality is Robust: Unlike Walrasian equilibrium models that require everyone to buy simultaneously (which often fails to exist for complex valuations), this model uses sequential arrivals. This "first-come, first-served" approach makes the market much more stable.
  • The "Half-Optimal" Magic Number: The insight that setting prices to 50% of expected value balances two risks: setting prices too high (leaving items unsold) and setting them too low (selling items to the "wrong" people early on).
  • Order Independence: Remarkably, the 1/2-approximation guarantee holds regardless of the order in which buyers arrive. Even if an adversary picks the worst possible sequence, the welfare remains high.
  • Handling Complements: While the best results are for "complement-free" valuations (where items don't become more valuable just because you have another specific item), the authors extend their work to the MPH (Maximum over Positive Hypergraphs) hierarchy. This allows them to handle goods that are complements, with the efficiency guarantee degrading gracefully as the complexity of those complements increases.

Key Results

  • XOS Valuations: For fractionally subadditive (XOS) valuations—a broad class that includes all submodular functions—the mechanism achieves at least 1/2 of the optimal expected social welfare.
  • Computational Efficiency: The mechanism is "truly polytime," meaning its running time depends only on the number of items ($m$) and buyers ($n$), not on the size of the buyers' possible preference sets (which can be exponential).
  • Incentive Compatibility: The mechanism is Dominant Strategy Incentive Compatible (DSIC). Because prices are fixed, a buyer's best move is always to simply buy the bundle they like most—there is no benefit to "gaming" the system.
  • General Valuations: For valuations with a complementarity level of $k$, the mechanism achieves a $1/4k$ approximation.

Limitations and Future Work

  • Demand Oracles: The "direct" version of their mechanism assumes the seller can simulate buyer behavior, which requires a "demand oracle." For some very complex valuations, answering "what is your favorite bundle at these prices?" is itself an NP-hard problem.
  • Sample Access: The seller must be able to sample from the buyers' valuation distributions. In real-world markets, these distributions might be unknown or non-stationary.
  • The Gap for Subadditive Valuations: While XOS valuations are well-handled, the paper leaves open whether a constant-factor approximation is possible for the even broader class of subadditive valuations (where the value of a whole is simply less than or equal to the sum of its parts). Currently, only a logarithmic approximation is known for that class.
  • Identical Items: The authors suggest that future work could explore how efficiency changes if there are multiple identical copies of items, which might allow for even better approximation factors.

Summary updated

Abstract

We study anonymous posted price mechanisms for combinatorial auctions in a Bayesian framework. In a posted price mechanism, item prices are posted, then the consumers approach the seller sequentially in an arbitrary order, each purchasing her favorite bundle from among the unsold items at the posted prices. These mechanisms are simple, transparent and trivially dominant strategy incentive compatible (DSIC). We show that when agent preferences are fractionally subadditive (which includes all submodular functions), there always exist prices that, in expectation, obtain at least half of the optimal welfare. Our result is constructive: given black-box access to a combinatorial auction algorithm A, sample access to the prior distribution, and appropriate query access to the sampled valuations, one can compute, in polytime, prices that guarantee at least half of the expected welfare of A. As a corollary, we obtain the first polytime (in n and m) constant-factor DSIC mechanism for Bayesian submodular combinatorial auctions, given access to demand query oracles. Our results also extend to valuations with complements, where the approximation factor degrades linearly with the level of complementarity.
BibTeX
@inproceedings{feldman2015combinatorial,
  author = {Michal Feldman and Nick Gravin and Brendan Lucier},
  title = {{Combinatorial Auctions via Posted Prices}},
  booktitle = {SODA},
  year = {2015},
  url = {https://openreview.net/forum?id=l0TEg_hVz7},
}

Loading related content...

Figure