Approximate Revenue Maximization with Multiple Items
Sergiu Hart and Noam Nisan
(*) Correction:
-
Page 341, footnote 39: should be "... is in fact the largest
function ..."
Abstract
Maximizing the revenue from selling imore than one good (or item) to a
single buyer is a notoriously difficult problem, in stark contrast to
the one-good case. For two goods, we show that simple "one-dimensional"
mechanisms, such as selling the 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.
For the case of k>2 independent goods, we show that selling them
separately guarantees at least a c/log²k fraction of the optimal
revenue; and, for independent and identically distributed goods, we show
that selling them as one bundle guarantees at least a c/log k fraction
of the optimal revenue.
Additional results compare the revenues from the two simple
mechanisms of selling the goods separately and bundled, identify
situations where bundling is optimal, and extend the analysis to
multiple buyers.
Last modified:
© Sergiu Hart