On the (in-)approximability of Bayesian Revenue Maximization for a Combinatorial Buyer

Natalie Collina, S. Matthew Weinberg

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

Abstract

We consider a revenue-maximizing single seller with mitems for sale to a single buyer whose value v(·) for the items is drawn from a known distribution Dof support k. A series of works by Cai et al. establishes that when each v(·) in the support of Dis additive or unit-demand (or c-demand), the revenue-optimal auction can be found in poly(m,k) time. We show that going barely beyond this, even to matroid-based valuations (a proper subset of Gross Substitutes), results in strong hardness of approximation. Specifically, even on instances with mitems and k ≤ m valuations in the support of D, it is not possible to achieve a 1/m1-ϵ-approximation for any ϵ>0 to the revenue-optimal mechanism for matroid-based valuations in (randomized) poly-time unless NP ĝ† RP (note that a $1/k$-approximation is trivial). Cai et al.'s main technical contribution is a black-box reduction from revenue maximization for valuations in class V to optimizing the difference between two values in class V. Our main technical contribution is a black-box reduction in the other direction (for a wide class of valuation classes), establishing that their reduction is essentially tight.

Original languageEnglish (US)
Title of host publicationEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages477-497
Number of pages21
ISBN (Electronic)9781450379755
DOIs
StatePublished - Jul 13 2020
Event21st ACM Conference on Economics and Computation, EC 2020 - Virtual, Online, Hungary
Duration: Jul 13 2020Jul 17 2020

Publication series

NameEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation

Conference

Conference21st ACM Conference on Economics and Computation, EC 2020
CountryHungary
CityVirtual, Online
Period7/13/207/17/20

All Science Journal Classification (ASJC) codes

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

Keywords

  • gross substitutes
  • optimal mechanism design
  • reductions
  • revenue

Fingerprint Dive into the research topics of 'On the (in-)approximability of Bayesian Revenue Maximization for a Combinatorial Buyer'. Together they form a unique fingerprint.

  • Cite this

    Collina, N., & Weinberg, S. M. (2020). On the (in-)approximability of Bayesian Revenue Maximization for a Combinatorial Buyer. In EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation (pp. 477-497). [3399496] (EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/3391403.3399496