Pricing randomized allocations
Pricing randomized allocations
复制标题
随机分配定价
DOI：
10.1137/1.9781611973075.49
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Foundation Fellowship
中科院分区：
文献类型：
--
作者：
Patrick Briest;Shuchi Chawla;Robert D. Kleinberg;S. Weinberg;A. P. Sloan;Foundation Fellowship
随机机制，将一组出价映射到结果的概率分布，而不是单个结果，是计算机制设计的一个重要但鲜为人知的领域。我们在一个基本的和典型的多参数机制设计问题的背景下研究随机结果（以下简称“彩票”）的作用：向单位需求投标人出售异质物品。卖家在多大程度上可以通过对彩票而不是商品定价来提高收入？这种问题的修改是否会影响其计算可追溯性？我们的研究结果表明，这些问题的答案取决于消费者是只购买一种彩票（买一模型），还是购买任何一套彩票并从每一套彩票中获得一个独立的样本（买多模型）。在买一模型中，有一个多项式时间算法来计算收益最大化的无嫉妒价格（从而克服了相应的物品定价问题的不可逼近性），只要物品类型的数量至少为4，最优彩票系统的收益可以超过最优物品定价的收益一个无限大的因子。在有n种产品类型的买多模型中，彩票定价所获得的利润可以超过产品定价Θ（log n）倍，但不能更大；对于某些ε >0，最优彩票定价不能在0 （nε）倍内近似，除非NP∧∩Δ>0 BPTIME（20 （nΔ））。我们的下界依赖于几何和代数技术的混合，而上界使用一种新颖的四舍五入方案，将具有随机结果的机制转换为具有确定性结果的机制，同时只损失有限的收入。
Randomized mechanisms, which map a set of bids to a probability distribution over outcomes rather than a single outcome, are an important but ill-understood area of computational mechanism design. We investigate the role of randomized outcomes (henceforth, "lotteries") in the context of a fundamental and archetypical multi-parameter mechanism design problem: selling heterogeneous items to unit-demand bidders. To what extent can a seller improve her revenue by pricing lotteries rather than items, and does this modification of the problem affect its computational tractability? Our results show that the answers to these questions hinge on whether consumers can purchase only one lottery (the buy-one model) or purchase any set of lotteries and receive an independent sample from each (the buy-many model). In the buy-one model, there is a polynomial-time algorithm to compute the revenue-maximizing envy-free prices (thus overcoming the inapproximability of the corresponding item pricing problem) and the revenue of the optimal lottery system can exceed the revenue of the optimal item pricing by an unbounded factor as long as the number of item types is at least 4. In the buy-many model with n item types, the profit achieved by lottery pricing can exceed item pricing by a factor of Θ(log n) but not more, and optimal lottery pricing cannot be approximated within a factor of O(nε) for some ε > 0, unless NP ⊆ ∩Δ>0 BPTIME(2O(nΔ)). Our lower bounds rely on a mixture of geometric and algebraic techniques, whereas the upper bounds use a novel rounding scheme to transform a mechanism with randomized outcomes into one with deterministic outcomes while losing only a bounded amount of revenue.