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

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr13r8d
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKothari, Pravesh-
dc.contributor.authorSingla, Sahil-
dc.contributor.authorMohan, Divyarthi-
dc.contributor.authorSchvartzman, Ariel-
dc.contributor.authorWeinberg, S Matthew-
dc.date.accessioned2021-10-08T19:47:57Z-
dc.date.available2021-10-08T19:47:57Z-
dc.date.issued2019en_US
dc.identifier.citationKothari, 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.00023en_US
dc.identifier.issn1523-8288-
dc.identifier.urihttps://arxiv.org/pdf/1905.05231.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr13r8d-
dc.description.abstractWe 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.en_US
dc.format.extent220 - 232en_US
dc.language.isoen_USen_US
dc.relation.ispartofIEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)en_US
dc.rightsAuthor's manuscripten_US
dc.titleApproximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetriesen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1109/FOCS.2019.00023-
dc.identifier.eissn2575-8454-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
ApproximationUnitDemandBuyerIndependentItems.pdf616.36 kBAdobe PDFView/Download


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