CS Events


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


Download as iCal file

Wednesday, February 19, 2020, 11:00am - 12:00pm


Rutgers/DIMACS Theory of Computing Seminar

Speaker: Ariel Schvartzman (Princeton)

Location : CoRE A 301

Event Type: Seminar

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 .99-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 .99-approximation for unbounded valuations that are subadditive over independent items to achieving a .99-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 .99 factor with a menu of efficient-linear symmetric menu complexity.Joint work with Pravesh Kothari (CMU), Divyarthi Mohan, Sahil Singla and S. Matthew Weinberg (Princeton).