Skip to main content

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

Author(s): Kothari, Pravesh; Singla, Sahil; Mohan, Divyarthi; Schvartzman, Ariel; Weinberg, S Matthew

To refer to this page use:
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.
Publication Date: 2019
Citation: Kothari, Pravesh, Sahil Singla, Divyarthi Mohan, Ariel Schvartzman, and S. Matthew Weinberg. "Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries." In IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (2019): pp. 220-232. doi:10.1109/FOCS.2019.00023
DOI: 10.1109/FOCS.2019.00023
ISSN: 1523-8288
EISSN: 2575-8454
Pages: 220 - 232
Type of Material: Conference Article
Journal/Proceeding Title: IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
Version: Author's manuscript

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