Linde Institute/Social and Information Sciences Laboratory (SISL) Seminar

Monday December 2, 2013 12:00 PM

Simple Prices for Complex Markets

Speaker: Nicole Immorlica, Theoretical Computer Science, Northwestern University
Location: Baxter 127

A vendor has multiple products for sale and a single buyer to sell them to.  What pricing strategies should the vendor employ to maximize revenue?  Should he set a separate take-it-or-leave-it price on each item, offer to sell all the items together at a special bundle price, or something even more complex?  Such multi-dimensional mechanism design problems are notorious for being poorly understood.  Consider the following setting, which is perhaps the simplest imaginable beyond selling a single item: the buyer has additive value across items, and the value for each of the items is independently distributed.  Hart and Nisan (2012) showed that, even this extremely simple setting is highly complex: neither selling each item separately nor selling only the bundle of all items (at their respectively optimal prices) can guarantee a constant fraction of the revenue of the optimal deterministic mechanism.

In this talk I will show that, for all instances, either selling each item separately *or* selling the grand bundle always achieves a constant fraction of the optimal revenue obtainable by a deterministic mechanism.  Such a pricing strategies can be very easily computed from the value distributions.  We conjecture that this guarantee also holds against all randomized mechanisms, as well.

Joint work with Moshe Babaioff, Brendan Lucier, and Matt Weinberg.

Series Linde Institute/Social and Information Sciences Laboratory Seminar Series (SISL)

Contact: Jenny Niese at Ext. 6010