论文标题
关于主要策略机制设计的硬度
On the Hardness of Dominant Strategy Mechanism Design
论文作者
论文摘要
我们研究组合拍卖的主要战略实施的沟通复杂性。我们从通常被认为是“简单”的两个领域开始：多单元拍卖，边际价值和组合拍卖量降低，并具有总替代价值。对于这两个域，我们都有快速的算法，这些算法可以找到福利最大化的分配，并具有输入大小中多同源性的通信复杂性。这立即暗示，可以通过使用VCG付款，在没有明显的沟通成本的情况下，可以在没有明显的沟通成本的情况下实现福利最大化。相比之下，我们表明，在两个领域中，实现最佳福利的任何主要策略实施的通信复杂性在输入大小中都是多项式的。 然后，我们继续研究通过主导策略机制可实现的近似比。对于降低边缘值的多单元拍卖，我们提供了主要的策略通信fptas。对于与一般估值的组合拍卖，我们表明，没有使用$ poly（m，n）$ communitass的近似值比$ m^{1-ε} $更好的近似值，其中$ m $是项目的数量，$ n $是投标人的数量。相比之下，以$ o（\ sqrt m）$近似$ poly（m，n）$通信实现了\ emph {随机}的主要策略机制。这证明了计算有效的确定性主导策略机制与随机策略之间的第一个差距。 在途中，我们回答了一个关于两个以上参与者实施主导战略机制的沟通成本的公开问题，还解决了同时组合拍卖领域的一些开放问题。
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 than $m^{1-ε}$ that uses $poly(m,n)$ bits of communication, where $m$ is the number of items and $n$ is the number of bidders. In contrast, a \emph{randomized} dominant strategy mechanism that achieves an $O(\sqrt m)$ approximation with $poly(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.
