Pricing ordered items
Pricing ordered items
复制标题
为订购的商品定价
DOI：
10.1145/3519935.3520065
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Tzamos, Christos
中科院分区：
文献类型：
--
作者：
Chawla, Shuchi;Rezvan, Rojin;Teng, Yifeng;Tzamos, Christos
我们研究了项目定价的收益保证和近似性。最近的工作表明，与nheterogeneous项目，项目定价保证一个O（logn）近似的最佳收入可实现的任何（买多）机制，即使买家任意组合的估值。然而，找到好的项目价格是具有挑战性的-它是已知的，即使在单位需求估值，这是NP-难找到的项目价格近似的最优项目定价的收入优于O（n）。我们的工作提供了一个更细粒度的分析的收入保证和计算复杂性的项目的数量“类别”，这可能是显着少于坦恩n。我们假设的项目被划分inkcategories，使一个类别内的项目是全有序的和买方的价值捆绑只取决于最好的项目包含从每个category.We项目定价保证一个O（logk）近似的最佳（多买）的收入，并提供了一个PTAS计算最优项目定价时，是常数。我们还提供了一个匹配的下界，表明即使当k =1时，问题也是（强）NP-困难的。我们的结果自然延伸到项目只是部分排序的情况下，在这种情况下，收入保证和计算复杂性取决于部分排序的宽度，即最大的一组，其中没有两个项目是可比的。
We study the revenue guarantees and approximability of item pricing. Recent work shows that withnheterogeneous items, item-pricing guarantees anO(logn) approximation to the optimal revenue achievable by any (buy-many) mechanism, even when buyers have arbitrarily combinatorial valuations. However, finding good item prices is challenging – it is known that even under unit-demand valuations, it is NP-hard to find item prices that approximate the revenue of the optimal item pricing better thanO(√n).Our work provides a more fine-grained analysis of the revenue guarantees and computational complexity in terms of the number of item “categories” which may be significantly fewer thann. We assume the items are partitioned inkcategories so that items within a category are totally-ordered and a buyer’s value for a bundle depends only on the best item contained from every category.We show that item-pricing guarantees anO(logk) approximation to the optimal (buy-many) revenue and provide a PTAS for computing the optimal item-pricing whenkis constant. We also provide a matching lower bound showing that the problem is (strongly) NP-hard even whenk=1. Our results naturally extend to the case where items are only partially ordered, in which case the revenue guarantees and computational complexity depend on the width of the partial ordering, i.e. the largest set for which no two items are comparable.
登录
查看更多内容
关于销售多个独立分布的商品的收入最大化
DOI：
--
发表时间：
2013
影响因子：
11.1
作者：
Xinye Li;A. Yao
通讯作者：
A. Yao
次加法组合拍卖的 O(log log m) 预言不等式
DOI：
--
发表时间：
2020
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Paul Dütting;Thomas Kesselheim;Brendan Lucier
通讯作者：
Brendan Lucier
DOI：
--
发表时间：
2011
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Yang Cai;C. Daskalakis
通讯作者：
C. Daskalakis
论单一投标人定价项目的硬度
DOI：
--
发表时间：
2009
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
R. Khandekar;T. Kimbrel;K. Makarychev;M. Sviridenko
通讯作者：
M. Sviridenko
影响因子：
1.3
作者：
ROCHET, JC
通讯作者：
ROCHET, JC