How Good Are Simple Mechanisms for Selling Multiple Goods?

Authors: 
Sergiu Hart
Noam Nisan
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.

Date: 
May, 2014
Number: 
666