skip to main content
Caltech

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

Monday, December 2, 2013
12:00pm to 1:00pm
Add to Cal
Baxter 127
Simple Prices for Complex Markets
Nicole Immorlica, Assistant Professor, Theoretical Computer Science, Northwestern University,

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.

For more information, please contact Jenny Niese by phone at Ext. 6010 or by email at [email protected].