On the hardness of dominant strategy mechanism design
On the hardness of dominant strategy mechanism design
复制标题
论优势策略机制设计的硬度
DOI：
10.1145/3519935.3520013
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Vondrák, Jan
中科院分区：
文献类型：
--
作者：
Dobzinski, Shahar;Ron, Shiri;Vondrák, Jan
研究了组合拍卖中优势策略实现的通信复杂度。我们从两个通常被认为“容易”的领域开始：边际价值递减的多单位拍卖和总替代估价的组合拍卖。对于这两个领域，我们都有快速的算法来找到具有输入大小多对数的通信复杂性的福利最大化分配。这立即意味着福利最大化可以在事后平衡中实现，而不需要显著的沟通成本，通过使用VCG支付。相反，我们表明，在这两个领域中，任何实现最优福利的优势策略的通信复杂性都是输入大小的多项式。然后，我们继续研究优势策略机制可实现的近似比率。对于边际价值递减的多单元拍卖，我们提供了一种优势策略通信FPTAS。对于具有一般估值的组合拍卖，我们表明没有优势策略机制可以实现比m1 - єthat更好的近似比率，使用poly（m,n）通信位，其中为物品数量，为投标人数量。相比之下，已知一种随机优势策略机制可以在poly（m,n）通信中实现anO（√m）近似。这证明了计算效率高的确定性优势策略机制与随机策略机制之间的第一个差距。在此过程中，我们回答了两个以上参与者实施优势策略机制的通信成本的开放性问题，并解决了同时组合拍卖领域的一些开放性问题。
We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered “easy”: multi-unit auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfare-maximizing allocation with communication complexity that is poly-logarithmic in the input size. This immediately implies that welfare maximization can be achieved in ex-post equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size.We then move on to studying the approximation ratios achievable by dominant strategy mechanisms. For multi-unit auctions with decreasing marginal values, we provide a dominant-strategy communication FPTAS. For combinatorial auctions with general valuations, we show that there is no dominant strategy mechanism that achieves an approximation ratio better thanm1−єthat usespoly(m,n) bits of communication, wheremis the number of items andnis the number of bidders. In contrast, a randomized dominant strategy mechanism that achieves anO(√m) approximation withpoly(m,n) communication is known. This proves the first gap between computationally efficient deterministic dominant strategy mechanisms and randomized ones.En route, we answer an open question on the communication cost of implementing dominant strategy mechanisms for more than two players, and also solve some open problems in the area of simultaneous combinatorial auctions.
登录
查看更多内容
区分真实和非真实组合拍卖的通信复杂性
DOI：
10.1145/3357713.3384267
发表时间：
2020
期刊：
Symposium on Theory of Computing
影响因子：
--
作者：
Assadi, Sepehr;Khandeparkar, Hrishikesh;Saxena, Raghuvansh R.;Weinberg, S. Matthew
通讯作者：
Weinberg, S. Matthew
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
影响因子：
8.2
作者：
N. Nisan
通讯作者：
N. Nisan
DOI：
--
发表时间：
2016
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Shahar Dobzinski
通讯作者：
Shahar Dobzinski
改进的次加性组合拍卖的真实机制：打破对数障碍
DOI：
10.1137/1.9781611976465.40
发表时间：
2020
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Sepehr Assadi;Thomas Kesselheim;Sahil Singla
通讯作者：
Sahil Singla