Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity
Simple Mechanisms for a Subadditive Buyer and Applications to Revenue Monotonicity
复制标题
次加法买家的简单机制及其对收入单调性的应用
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Weinberg
中科院分区：
文献类型：
--
作者：
A. Rubinstein;S. Weinberg
研究了一个具有n个异质商品的卖方向一个单一买方销售的收益最大化问题，该买方对商品集的估价函数是未知的，并且来自于某个分布D。我们表明，如果D是一个分布在次可加估值与独立的项目，那么更好的定价每个项目单独或定价只有大捆绑实现了一个常数因子近似的最优机制的收入。这包括k-需求的买家，可加到拟阵约束的买家，或可加到任何下闭集系统的约束的买家（并且其单个项目的值是独立采样的），以及具有独立绘制的项目乘数的分数次可加买家。我们的证明利用了在以前的工作中开发的核心-尾部分解框架，对于显着更简单的添加剂买家类显示出类似的结果。在文章的第二部分中，我们建立了近似最优简单机制和近似收入单调性之间的联系。收益非单调性是指有时严格增加每个集合的购买者价值会严格减少最优机制的收益的现象。使用我们的主要结果，我们得出了一个如何坏这种退化的界限（和配音这样一个界的近似收入单调性的证明），我们进一步表明，更好的近似单调性的界限意味着我们的简单机制更好的分析。
We study the revenue maximization problem of a seller with n heterogeneous items for sale to a single buyer whose valuation function for sets of items is unknown and drawn from some distribution D. We show that if D is a distribution over subadditive valuations with independent items, then the better of pricing each item separately or pricing only the grand bundle achieves a constant-factor approximation to the revenue of the optimal mechanism. This includes buyers who are k-demand, additive up to a matroid constraint, or additive up to constraints of any downward-closed set system (and whose values for the individual items are sampled independently), as well as buyers who are fractionally subadditive with item multipliers drawn independently. Our proof makes use of the core-tail decomposition framework developed in prior work showing similar results for the significantly simpler class of additive buyers. In the second part of the article, we develop a connection between approximately optimal simple mechanisms and approximate revenue monotonicity with respect to buyers’ valuations. Revenue non-monotonicity is the phenomenon that sometimes strictly increasing buyers’ values for every set can strictly decrease the revenue of the optimal mechanism. Using our main result, we derive a bound on how bad this degradation can be (and dub such a bound a proof of approximate revenue monotonicity); we further show that better bounds on approximate monotonicity imply a better analysis of our simple mechanisms.