Optimal Multi-Dimensional Mechanisms are not Locally-Implementable
Optimal Multi-Dimensional Mechanisms are not Locally-Implementable
复制标题
最佳多维机制无法在本地实现
DOI：
10.1145/3490486.3538334
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Zhou, Zixin
中科院分区：
文献类型：
--
作者：
Weinberg, S. Matthew;Zhou, Zixin
我们引入局部性：多投标人拍卖的一个新的属性，正式分离的最优单维多投标人拍卖的简单性从最优多维多投标人拍卖的复杂性。具体来说，考虑收入最优的贝叶斯激励兼容拍卖，买家的估值来自D->：=xi Di，其中每个分布都有支持大小n。该拍卖将估价简档v->作为输入，并产生物品的分配和要收取的价格作为输出，选项D->（v->）。当每个Di是一维时，该映射是局部可实现的：定义每个输入vi需要Θ（log n）位，并且可以仅使用来自每个Di的Θ（log n）位来完全确定Opt D->（v->）。这直接遵循迈尔森的虚值理论[36]。我们的主要结果建立了最佳多维机制不是局部可实现的：为了确定一个特定输入v->上的输出Opt D->（v->），人们仍然需要知道（本质上）整个分布D->。形式上，来自每个Di的Ω（n）位是必要的：（基本上）足以完全描述Di，并且指数地大于定义输入vi所需的Θ（log n）。我们表明，这种现象已经发生只有两个投标人，即使当一个投标人是一维的，甚至当其他投标人几乎是多维的。更具体地说，多维投标人是“跨维”从联邦快递设置只有两天[28]。我们的技术是相当强大的：我们还建立了最佳机制，为单维买家的预算限制是不能本地实施。即使只有两个投标人，即使其中一个没有预算限制，即使另一个的预算是公开的，这种情况也会发生。
We introduce locality: a new property of multi-bidder auctions that formally separates the simplicity of optimal single-dimensional multi-bidder auctions from the complexity of optimal multi-dimensional multi-bidder auctions. Specifically, consider the revenue-optimal, Bayesian Incentive Compatible auction for buyers with valuations drawn from D-> :=xi Di, where each distribution has support-size n. This auction takes as input a valuation profile v-> and produces as output an allocation of the items and prices to charge, Opt D-> (v->). When each Di is single-dimensional, this mapping is locally-implementable: defining each input vi requires Θ(log n) bits, and Opt D-> (v->) can be fully determined using just Θ(log n) bits from each Di. This follows immediately from Myerson's virtual value theory [36].Our main result establishes that optimal multi-dimensional mechanisms are not locally-implementable: in order to determine the output Opt D-> (v->) on one particular input v->, one still needs to know (essentially) the entire distribution D->. Formally, Ω(n) bits from each Di is necessary: (essentially) enough to fully describe Di, and exponentially more than the Θ(log n) needed to define the input vi. We show that this phenomenon already occurs with just two bidders, even when one bidder is single-dimensional, and even when the other bidder is barely multi-dimensional. More specifically, the multi-dimensional bidder is "inter-dimensional" from the FedEx setting with just two days [28].Our techniques are fairly robust: we additionally establish that optimal mechanisms for single-dimensional buyers with budget constraints are not locally-implementable. This again occurs even with just two bidders, even when one has no budget constraint, and even when the other's budget is public.
登录
查看更多内容
主导策略与贝叶斯多项目拍卖：最大收入确定和比较
DOI：
10.1145/3033274.3085120
发表时间：
2017
期刊：
Proceedings of the 2017 ACM Conference on Economics and Computation
影响因子：
--
作者：
A. Yao
通讯作者：
A. Yao
DOI：
10.1145/3406325.3451127
发表时间：
2021
期刊：
ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Rubinstein, Aviad;Saxena, Raghuvansh R.;Thomas, Clayton;Weinberg, S. Matthew;Zhao, Junyao
通讯作者：
Zhao, Junyao
DOI：
10.1109/focs.2013.73
发表时间：
2012
期刊：
2013 IEEE 54th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
S. Alaei;Hu Fu;Nima Haghpanah;Jason D. Hartline
通讯作者：
Jason D. Hartline
DOI：
--
发表时间：
2009
期刊：
Journal of Economics Theory
影响因子：
--
作者：
R. Fadel;I. Segal
通讯作者：
I. Segal
满足私人需求的最优多单元机制
DOI：
--
发表时间：
2017
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
Nikhil R. Devanur;Nima Haghpanah;Alexandros Psomas
通讯作者：
Alexandros Psomas