Simple mechanisms for a subadditive buyer and applications to revenue monotonicity

Aviad Rubinstein, Seth Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

38 Scopus citations

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 downwards-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 [Li and Yao 2013; Babaioff et al. 2014]. In the second part of the paper, 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 [Hart and Reny 2012]. 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.

Original languageEnglish (US)
Title of host publicationEC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages377-394
Number of pages18
ISBN (Electronic)9781450334105
DOIs
StatePublished - Jun 15 2015
Event16th ACM Conference on Economics and Computation, EC 2015 - Portland, United States
Duration: Jun 15 2015Jun 19 2015

Publication series

NameEC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation

Other

Other16th ACM Conference on Economics and Computation, EC 2015
CountryUnited States
CityPortland
Period6/15/156/19/15

All Science Journal Classification (ASJC) codes

  • Economics and Econometrics
  • Statistics and Probability
  • Computer Science (miscellaneous)
  • Computational Mathematics
  • Marketing

Fingerprint Dive into the research topics of 'Simple mechanisms for a subadditive buyer and applications to revenue monotonicity'. Together they form a unique fingerprint.

  • Cite this

    Rubinstein, A., & Weinberg, S. M. (2015). Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. In EC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation (pp. 377-394). (EC 2015 - Proceedings of the 2015 ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/2764468.2764510