Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity

Aviad Rubinstein, S. Matthew Weinberg

TL;DR

This paper introduces simple, constant-factor approximation mechanisms for revenue maximization in settings with complex buyer valuations (subadditive over independent items). It shows that a basic strategy of either pricing items individually or selling them as a single bundle is surprisingly effective, bridging a gap between theoretical optimality and practical implementation. The work also connects these simple mechanisms to the concept of revenue monotonicity, offering bounds on how much revenue can be lost due to non-monotonic buyer preferences.

What Problem Does This Paper Address?

The core problem is how a seller can maximize revenue when selling multiple distinct items to a single buyer whose preferences are complex and unknown. While the optimal selling strategy for a single item is well-understood (Myerson's auction), the multi-item case is notoriously difficult. Optimal mechanisms can be computationally intractable, non-monotonic (meaning increasing a buyer's value for items can paradoxically decrease revenue), and generally hard to design. This paper tackles this by asking: can we achieve a good approximation of the optimal revenue using simple selling strategies, even when buyers have "subadditive" valuations over independent items? Subadditive valuations are more general than simple additive ones, allowing for some complementarities or diminishing marginal returns.

Methods

The authors leverage a powerful technique called "core-tail decomposition," previously used for simpler additive valuations. This framework breaks down the problem into two parts:

  1. Tail: Items a buyer highly values.
  2. Core: Items a buyer values less.

They adapt this framework to subadditive valuations by:

  • Approximate Core Decomposition Lemma: A key technical contribution that extends the core-tail decomposition to handle subadditive buyers, overcoming the challenge that their valuations aren't simply separable. This involves using ideas from "e-truthful" mechanisms.
  • Bounding Contributions: They then bound the revenue obtainable from the "tail" using individual item pricing (SREV) and the revenue from the "core" using a combination of individual item pricing and grand bundle pricing (max{SREV, BREV}).
  • Revenue Monotonicity Connection: The paper also explores how their results relate to revenue non-monotonicity. They show that their findings provide bounds on how much revenue can be lost due to non-monotonicity and, conversely, that improvements in understanding revenue monotonicity could lead to better approximation guarantees.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and general distributions of buyer valuations, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Simplicity Wins (Approximately): The most striking insight is that for a broad class of complex buyer valuations (subadditive over independent items), a very simple strategy—either pricing each item individually or selling them all as a single bundle—achieves a constant-factor approximation to the theoretically optimal revenue. This is a significant result because optimal mechanisms are often impractical.
  • Core-Tail Decomposition is Robust: The paper demonstrates the power and adaptability of the core-tail decomposition framework, showing it can be extended beyond additive valuations to more complex subadditive settings.
  • Revenue Monotonicity is Quantifiable: The work provides a formal way to bound the "damage" caused by revenue non-monotonicity, offering a measure of how much revenue can be lost when buyer preferences behave counter-intuitively.
  • Interplay Between Simplicity and Monotonicity: The paper highlights a fascinating duality: better understanding of revenue monotonicity can lead to improved simple mechanisms, and vice-versa.

Key Results

  • Constant-Factor Approximation: The main theorem states that for subadditive buyers with independent items, the revenue from the better of individual item pricing (SREV) or grand bundle pricing (BREV) is at least a constant fraction (specifically, shown to be at least 1/314) of the optimal revenue.
  • Efficient Computation: The mechanisms that achieve these guarantees are computationally efficient.
  • Approximate Revenue Monotonicity Bounds: The paper derives bounds on revenue degradation due to non-monotonicity for subadditive buyers. For instance, it shows that subadditive valuations over independent items are approximately revenue monotone with a factor of 338.

Limitations and Future Work

  • Multiple Buyers: The current results primarily focus on a single buyer. Extending these simple mechanisms and approximation guarantees to multiple buyers with subadditive valuations is identified as a major open question.
  • Correlated Valuations: The paper notes that for certain types of correlated valuations (specifically, additive valuations for two items), the gap between simple and optimal mechanisms can be infinite, meaning the current approach doesn't directly apply.
  • Practicality of Bounds: While the theoretical bounds are constant-factor, the constants themselves can be large (e.g., 338). Future work might aim to tighten these constants for more practical implications.
  • General Combinatorial Valuations: The paper deals with subadditive valuations over independent items. Extending the results to more general combinatorial valuation settings remains an area for future research.

Summary updated

Abstract

We study the revenue maximization problem of a seller with n heterogeneous items for sale to a single buyer whose valuation function for sets of items is unknown and drawn from some distribution D. We show that if D is a distribution over subadditive valuations with independent items, then the better of pricing each item separately or pricing only the grand bundle achieves a constant-factor approximation to the revenue of the optimal mechanism. This includes buyers who are k-demand, additive up to a matroid constraint, or additive up to constraints of any downward-closed set system (and whose values for the individual items are sampled independently), as well as buyers who are fractionally subadditive with item multipliers drawn independently. Our proof makes use of the core-tail decomposition framework developed in prior work showing similar results for the significantly simpler class of additive buyers. In the second part of the article, we develop a connection between approximately optimal simple mechanisms and approximate revenue monotonicity with respect to buyers’ valuations. Revenue non-monotonicity is the phenomenon that sometimes strictly increasing buyers’ values for every set can strictly decrease the revenue of the optimal mechanism. Using our main result, we derive a bound on how bad this degradation can be (and dub such a bound a proof of approximate revenue monotonicity); we further show that better bounds on approximate monotonicity imply a better analysis of our simple mechanisms.
BibTeX
@inproceedings{rubinstein2015simple,
  author = {Aviad Rubinstein and S. Matthew Weinberg},
  title = {{Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity}},
  booktitle = {EC},
  year = {2015},
  doi = {10.1145/2764468.2764510},
}

Loading related content...

Figure