Item pricing for revenue maximization
Item pricing for revenue maximization
复制标题
DOI：
10.1145/1386790.1386802
复制
发表时间：
2008-07
期刊：
影响因子：
--
通讯作者：
Maria-Florina Balcan;Avrim Blum;Y. Mansour
中科院分区：
文献类型：
--
作者：
Maria-Florina Balcan;Avrim Blum;Y. Mansour
我们考虑的问题，定价n个项目，以最大限度地提高收入时，面对一系列的未知买家复杂的偏好，并表明，一个简单的定价方案实现了令人惊讶的强有力的保证。我们表明，在无限供给设置，一个随机的单一价格达到预期收入的对数因子的总社会福利的客户一般的价值函数，这可能不一定是单调的。这概括了Guruswami等人的工作。al [18]，他们只在专一和单位需求客户的特殊情况下显示对数因子。在有限供给的情况下，我们证明了对于次可加估值，随机单一价格在总社会福利的20（log n loglog n）倍内实现收入，即，即使卖方可以对每个买方的每捆产品定价不同，卖方也希望获得最佳收入。这是已知的最佳近似值，适用于任何次加性（甚至次模化）估值的项目定价方案，即使使用多个价格。我们用一个下界来补充这个结果，这个下界表示一个次可加（实际上是XOS）购买者序列，对于这个序列，任何单一价格的近似比都是2Ω（log 1/4 n），从而表明单一价格方案不能实现多对数比。这个下限表明了在这种情况下收入最大化和社会福利最大化之间的明显区别，[12，10]表明固定价格在XOS [12]和更一般的次可加性[10]客户的情况下实现了对数近似。我们还考虑了[1111]在社会福利背景下研究的多单位情况，并表明只要没有买家需要超过1 - ε的物品，随机单一价格实际上在最大社会福利的O（log n）因子内实现收入。
We consider the problem of pricing n items to maximize revenue when faced with a series of unknown buyers with complex preferences, and show that a simple pricing scheme achieves surprisingly strong guarantees. We show that in the unlimited supply setting, a random single price achieves expected revenue within a logarithmic factor of the total social welfare for customers with general valuation functions, which may not even necessarily be monotone. This generalizes work of Guruswami et. al [18], who show a logarithmic factor for only the special cases of single-minded and unit-demand customers. In the limited supply setting, we show that for subadditive valuations, a random single price achieves revenue within a factor of 2O(√(log n loglog n) of the total social welfare, i.e., the optimal revenue the seller could hope to extract even if the seller could price each bundle differently for every buyer. This is the best approximation known for any item pricing scheme for subadditive (or even submodular) valuations, even using multiple prices. We complement this result with a lower bound showing a sequence of subadditive (in fact, XOS) buyers for which any single price has approximation ratio 2Ω(log1/4 n), thus showing that single price schemes cannot achieve a polylogarithmic ratio. This lower bound demonstrates a clear distinction between revenue maximization and social welfare maximization in this setting, for which [12,10] show that a fixed price achieves a logarithmic approximation in the case of XOS [12], and more generally subadditive [10], customers. We also consider the multi-unit case examined by [1111] in the context of social welfare, and show that so long as no buyer requires more than a 1 -- ε fraction of the items, a random single price now does in fact achieve revenue within an O(log n) factor of the maximum social welfare.