Skip to main content

Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity

Author(s): Rubinstein, Aviad; Weinberg, S Matthew

To refer to this page use:
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.
Publication Date: Oct-2018
Citation: Rubinstein, Aviad, and S. Matthew Weinberg. "Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity." ACM Transactions on Economics and Computation 6, no. 3-4 (2018): 19:1-19:25. doi:10.1145/3105448
DOI: 10.1145/3105448
ISSN: 2167-8375
EISSN: 2167-8383
Pages: 19:1-19:25
Type of Material: Journal Article
Journal/Proceeding Title: ACM Transactions on Economics and Computation
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.