How Good Are Simple Mechanisms for Selling Multiple Goods?

Sergiu Hart and Noam Nisan


   
(Acrobat PDF files)


Abstract

Maximizing the revenue from selling two goods (or items) is a notoriously difficult problem, in stark contrast to the single-good case. We show that simple "one-dimensional" mechanisms, such as selling the two goods separately, guarantee at least 73% of the optimal revenue when the valuations of the two goods are independent and identically distributed, and at least 50% when they are independent. However, in the general case where the valuations may be correlated, simple mechanisms cannot guarantee any positive fraction of the optimal revenue. We also introduce a "measure of complexity" for mechanisms—the menu size—and show that it is naturally related to the fraction of the optimal revenue that can be guaranteed.

Based on results from the two working papers Hart and Nisan 2012 and Hart and Nisan 2013


   

Last modified:
© Sergiu Hart