TY - GEN

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

AU - Kothari, Pravesh

AU - Singla, Sahil

AU - Mohan, Divyarthi

AU - Schvartzman, Ariel

AU - Weinberg, S. Matthew

PY - 2019/11

Y1 - 2019/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85078476146&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85078476146&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2019.00023

DO - 10.1109/FOCS.2019.00023

M3 - Conference contribution

AN - SCOPUS:85078476146

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 220

EP - 232

BT - Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019

PB - IEEE Computer Society

T2 - 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019

Y2 - 9 November 2019 through 12 November 2019

ER -