Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

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

Ariel Schvartzman (Princeton):

Location:  Core 301
Date & time: Wednesday, 19 February 2020 at 11:00AM - 12:00PM

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

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.