Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries

Pravesh Kothari, Sahil Singla, Divyarthi Mohan, Ariel Schvartzman, S. Matthew Weinberg

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

4 Scopus citations

Abstract

We consider a revenue-maximizing seller with n items facing a single buyer. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distinct options the buyer may purchase, up to permutations of the items. Our main result is that a mechanism of quasi-polynomial symmetric menu complexity suffices to guarantee a (1-epsilon )-Approximation when the buyer is unit-demand over independent items, even when the value distribution is unbounded, and that this mechanism can be found in quasi-polynomial time. Our key technical result is a polynomial-Time, (symmetric) menu-complexity-preserving black-box reduction from achieving a (1-epsilon )-Approximation for unbounded valuations that are subadditive over independent items to achieving a (1-O(epsilon ))-Approximation when the values are bounded (and still subadditive over independent items). We further apply this reduction to deduce approximation schemes for a suite of valuation classes beyond our main result. Finally, we show that selling separately (which has exponential menu complexity) can be approximated up to a (1-epsilon ) factor with a menu of efficient-linear (f (epsilon) · n) symmetric menu complexity.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PublisherIEEE Computer Society
Pages220-232
Number of pages13
ISBN (Electronic)9781728149523
DOIs
StatePublished - Nov 2019
Event60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 - Baltimore, United States
Duration: Nov 9 2019Nov 12 2019

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2019-November
ISSN (Print)0272-5428

Conference

Conference60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
CountryUnited States
CityBaltimore
Period11/9/1911/12/19

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries'. Together they form a unique fingerprint.

Cite this