Revenue Maximization for Selling Multiple Correlated Items
Venue
23rd Annual European Symposium on Algorithms (ESA), Springer-Verlag (2015)
Publication Year
2015
Authors
Mohammadhossein Bateni, Sina Dehghani, MohammadTaghi Hajiaghayi, Saeed Seddighin
BibTeX
Abstract
We study the problem of selling $n$ items to a single buyer with an additive
valuation function. We consider the valuation of the items to be correlated, i.e.,
desirabilities of the buyer for the items are not drawn independently. Ideally, the
goal is to design a mechanism to maximize the revenue. However, it has been shown
that a revenue optimal mechanism might be very complicated and as a result
inapplicable to real-world auctions. Therefore, our focus is on designing a simple
mechanism that achieves a constant fraction of the optimal revenue. Babaioff et al.
(FOCS'14) propose a simple mechanism that achieves a constant fraction of the
optimal revenue for independent setting with a single additive buyer. However, they
leave the following problem as an open question: "Is there a simple, approximately
optimal mechanism for a single additive buyer whose value for $n$ items is sampled
from a common base-value distribution?" Babaioff et al. show a constant
approximation factor of the optimal revenue can be achieved by either selling the
items separately or as a whole bundle in the independent setting. We show a similar
result for the correlated setting when the desirabilities of the buyer are drawn
from a common base-value distribution. It is worth mentioning that the core
decomposition lemma which is mainly the heart of the proofs for efficiency of the
mechanisms does not hold for correlated settings. Therefore we propose a modified
version of this lemma which is applicable to the correlated settings as well.
Although we apply this technique to show the proposed mechanism can guarantee a
constant fraction of the optimal revenue in a very weak correlation, this method
alone can not directly show the efficiency of the mechanism in stronger
correlations. Therefore, via a combinatorial approach we reduce the problem to an
auction with a weak correlation to which the core decomposition technique is
applicable. In addition, we introduce a generalized model of correlation for items
and show the proposed mechanism achieves an $O(\log k)$ approximation factor of the
optimal revenue in that setting.
