论文标题
细颗粒的买入机制并没有比捆绑好得多
Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling
论文作者
论文摘要
已知多个项目的收入最佳机制非常复杂，通常为买家提供随机的商品彩票。在标准的购买模型中，众所周知，最佳机制可以无限地产生比任何“简单”机制的收入高，即项目数量中的多项式机制的收入 - 即使只有两个项目和一个单一买家（Briest等人，2015年，Hart和Nisan 2017）。 我们介绍了一种新的参数化机制，即买入$ K $机制，该机制在经典的购买机制和最近研究的买入机制之间平稳插值（Chawla等，2019； Chawla等，2020，Chawla等，Chawla etal。2022）。买入 - $ k $机制使买家最多可购买$ k $许多菜单选项。我们表明，将卖方限制在购买类别的类别中，兼容激励兼容的机制足以克服购买型模型的奇异，无限的收入属性。我们的主要结果是，关于捆绑的收入差距是一种非常简单的机制，对于任何任意相关的分布$ \ Mathcal {d} $ by $ o（n^2）$限制了$ n $ n $ toss the Adghitive Buyter的情况。我们的技术还使我们能够证明与任意单调估值相似的上限，尽管在近似中具有指数因素。 在负面方面，我们表明，即使我们将基准削弱到最佳的买入 - $ K $确定性机制时，允许买家购买少量菜单选项也不足以保证次指定近似值。如果仅允许添加剂购买$ k =θ（n^{1/2- \ varepsilon}）$许多菜单选项，则收入最佳的确定性确定性买入 - $ k $机制与捆绑之间的差距可以在$ n $中指数。特别是，这意味着没有“简单”机制可以在此制度中获得次指数近似。
Multi-item revenue-optimal mechanisms are known to be extremely complex, often offering buyers randomized lotteries of goods. In the standard buy-one model, it is known that optimal mechanisms can yield revenue infinitely higher than that of any "simple" mechanism -- the ones with size polynomial in the number of items -- even with just two items and a single buyer (Briest et al. 2015, Hart and Nisan 2017). We introduce a new parameterized class of mechanisms, buy-$k$ mechanisms, which smoothly interpolate between the classical buy-one mechanisms and the recently studied buy-many mechanisms (Chawla et al. 2019, Chawla et al. 2020, Chawla et al. 2022). Buy-$k$ mechanisms allow the buyer to buy up to $k$ many menu options. We show that restricting the seller to the class of buy-$n$ incentive-compatible mechanisms suffices to overcome the bizarre, infinite revenue properties of the buy-one model. Our main result is that the revenue gap with respect to bundling, an extremely simple mechanism, is bounded by $O(n^2)$ for any arbitrarily correlated distribution $\mathcal{D}$ over $n$ items for the case of an additive buyer. Our techniques also allow us to prove similar upper bounds for arbitrary monotone valuations, albeit with an exponential factor in the approximation. On the negative side, we show that allowing the buyer to purchase a small number of menu options does not suffice to guarantee sub-exponential approximations, even when we weaken the benchmark to the optimal buy-$k$ deterministic mechanism. If an additive buyer is only allowed to buy $k = Θ(n^{1/2-\varepsilon})$ many menu options, the gap between the revenue-optimal deterministic buy-$k$ mechanism and bundling may be exponential in $n$. In particular, this implies that no "simple" mechanism can obtain a sub-exponential approximation in this regime.
