Buy-Many Mechanisms for Many Unit-Demand Buyers
Buy-Many Mechanisms for Many Unit-Demand Buyers
复制标题
为众多单位需求买家提供多买机制
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Christos Tzamos
中科院分区：
文献类型：
--
作者：
Shuchi Chawla;Rojin Rezvan;Yifeng Teng;Christos Tzamos
最近的一项研究为设计近似收益最优的多项目机制建立了一个新的理想条件，即买多约束。在此约束下，由该机制做出的不同分配的价格必须是次相加的，这意味着一束产品的价格不能超过它所包含的单个产品的价格总和。这一自然约束使得在多项目机制设计中绕过公认的不可能结果获得了若干积极结果。我们的工作解决了本文献中主要的开放问题，即将买多约束扩展到多个买方设置并开发近似。我们提出了一个新的多买家机制的收入基准，通过事前放松，捕获了几种不同的方式，将买多约束扩展到多买家设置。我们的主要结果是，当所有买家对m个商品都有单位需求或附加偏好时，一个具有买家特定价格的简单顺序商品定价机制可以实现对该收入基准的0 （log m）美元近似。这是最好的可能，因为它直接匹配之前的单一买家设置的结果，没有简单的机制可以获得更好的近似。从技术角度来看，我们做出了两项新的贡献。首先，我们开发了一个单一买家的多买近似的供应约束版本。其次，我们为单位需求买家开发了一个多维在线争用解决方案，这可能是机制设计中独立的兴趣。
A recent line of research has established a novel desideratum for designing approximately-revenue-optimal multi-item mechanisms, namely the buy-many constraint. Under this constraint, prices for different allocations made by the mechanism must be subadditive, implying that the price of a bundle cannot exceed the sum of prices of individual items it contains. This natural constraint has enabled several positive results in multi-item mechanism design bypassing well-established impossibility results. Our work addresses the main open question from this literature of extending the buy-many constraint to multiple buyer settings and developing an approximation. We propose a new revenue benchmark for multi-buyer mechanisms via an ex-ante relaxation that captures several different ways of extending the buy-many constraint to the multi-buyer setting. Our main result is that a simple sequential item pricing mechanism with buyer-specific prices can achieve an $O(log m)$ approximation to this revenue benchmark when all buyers have unit-demand or additive preferences over m items. This is the best possible as it directly matches the previous results for the single-buyer setting where no simple mechanism can obtain a better approximation. From a technical viewpoint we make two novel contributions. First, we develop a supply-constrained version of buy-many approximation for a single buyer. Second, we develop a multi-dimensional online contention resolution scheme for unit-demand buyers that may be of independent interest in mechanism design.
为订购的商品定价
DOI：
10.1145/3519935.3520065
发表时间：
2022
期刊：
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Chawla, Shuchi;Rezvan, Rojin;Teng, Yifeng;Tzamos, Christos
通讯作者：
Tzamos, Christos