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

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.