Revenue Maximization for Selling Multiple Correlated Items
Revenue Maximization for Selling Multiple Correlated Items
复制标题
销售多个相关商品的收入最大化
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Saeed Seddighin
中科院分区：
文献类型：
--
作者：
M. Bateni;Sina Dehghani;M. Hajiaghayi;Saeed Seddighin
我们将n个项目销售给具有额外的价值功能的问题。然而，一种最大化收入的机制。达到最佳收入的机制。问题：“对于单个添加剂的购买者，n个项目的价值是从共同的基础价值分布中采样的，这是一个简单的最佳机制？”可以通过单独出售商品或在独立环境中的整个捆绑物来实现最佳收入的近似因素。值得一提的是，核心分解引理主要是证明机制效率的核心，因此我们提出了一个修改后的版本。同样适用于相应设置的引理。因此，通过组合方法，我们将问题减少到核心分解技术的弱相关性。项目的广义相关模型，并显示所提出的机制在该环境中达到了最佳收入的O（LOGK）近似因素。
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. [3] 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(logk) approximation factor of the optimal revenue in that setting.