Computational Efficiency Requires Simple Taxation
Computational Efficiency Requires Simple Taxation
复制标题
计算效率需要简单的税收
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Shahar Dobzinski
中科院分区：
文献类型：
--
作者：
Shahar Dobzinski
我们表征了真实机制的沟通复杂性。我们的出发点是众所周知的税收原则。税收原则断言，每种真实的机制都可以解释为以下方式：每个玩家都有一个由每个捆绑包的价格组成的菜单（价格仅取决于其他玩家的估值）。每个玩家都会根据此菜单分配一个捆绑包，从而最大程度地利用他的利润。我们将真实机制的税收复杂性定义为可能显示给玩家的最大菜单数量的对数。我们的主要发现是，总体而言，税收复杂性本质上等于沟通的复杂性。证明由两个主要步骤组成。首先，我们证明，对于足够丰富的领域，税收复杂性最多是沟通复杂性。然后，我们证明税收复杂性仅比“病理”案件中的沟通复杂性要小得多，并对这些极端情况进行了正式描述。接下来，我们研究仅通过价值查询访问估值的机制。在这种情况下，我们确定菜单复杂性 - 在几个不同情况下已经研究的概念 - 表征了该机制以与税收复杂性表征通信复杂性完全相同的方式所产生的价值查询数量。我们的方法产生了几种应用，包括通过低沟通开销来加强解决方案概念，价格快速计算以及通过计算有效的真实机制来实现近似的硬度。
We characterize the communication complexity of truthful mechanisms. Our departure point is the well known taxation principle. The taxation principle asserts that every truthful mechanism can be interpreted as follows: every player is presented with a menu that consists of a price for each bundle (the prices depend only on the valuations of the other players). Each player is allocated a bundle that maximizes his profit according to this menu. We define the taxation complexity of a truthful mechanism to be the logarithm of the maximum number of menus that may be presented to a player. Our main finding is that in general the taxation complexity essentially equals the communication complexity. The proof consists of two main steps. First, we prove that for rich enough domains the taxation complexity is at most the communication complexity. We then show that the taxation complexity is much smaller than the communication complexity only in "pathological" cases and provide a formal description of these extreme cases. Next, we study mechanisms that access the valuations via value queries only. In this setting we establish that the menu complexity - a notion that was already studied in several different contexts - characterizes the number of value queries that the mechanism makes in exactly the same way that the taxation complexity characterizes the communication complexity. Our approach yields several applications, including strengthening the solution concept with low communication overhead, fast computation of prices, and hardness of approximation by computationally efficient truthful mechanisms.