论文标题
付款计算的沟通复杂性
The Communication Complexity of Payment Computation
论文作者
论文摘要
令$（f，p）$是一种激励兼容机制，其中$ f $是社交选择功能，而$ p $是付款功能。在许多重要的环境中，$ f $唯一地决定$ p $（最高为常数），因此，一种常见的方法是专注于$ f $的设计并忽略了付款功能的作用。 Fadel和Segal [Jet，2009]通过采用通信复杂性的镜头来询问这种方法：是否可以使实现$ f $的激励兼容机制的通信复杂性（即，计算出产出和付款）比计算输出的沟通复杂性大得多？即，可以是$ cc_ {ic}（f）>> cc（f）$吗？ FADEL和SEGAL表明，对于每个$ f $，$ cc_ {ic}（f）\ leq exp（cc（f））$。他们还表明，完全计算激励兼容机制比仅计算输出要困难：存在社交选择功能$ f $，以便$ cc_ {ic}（f）= cc（f）+1 $。在后续工作中，Babaioff，Blumrosen，Naor和Schapira [EC'08]提供了一个社交选择功能$ F $，使得$ cc_ {ic}（f）=θ（n \ cdot cc（f））$，其中$ n $是播放器的数量。 Fadel和Segal的指数上限是否紧密的问题保持开放。在本文中，我们通过明确提供$ f $来解决这个问题，以便$ cc_ {ic}（f）= exp（cc（f））$。实际上，我们通过两个截然不同的证据来确定这一点。相反，我们表明，如果玩家是中立的，并且我们可以在随机真实的期望实现（而不是确定性的事后实施）上妥协，则只要$ f $ f $ of $ f $ f $ of $ f $ contex contex untex contex norment contex normains of a contex normains nockain noff $ f $ cc_ {tie}（tie}（f）= poly（n，cc（f）$）我们还提供有效的算法来确定几个重要领域的付款。
Let $(f,P)$ be an incentive compatible mechanism where $f$ is the social choice function and $P$ is the payment function. In many important settings, $f$ uniquely determines $P$ (up to a constant) and therefore a common approach is to focus on the design of $f$ and neglect the role of the payment function. Fadel and Segal [JET, 2009] question this approach by taking the lenses of communication complexity: can it be that the communication complexity of an incentive compatible mechanism that implements $f$ (that is, computes both the output and the payments) is much larger than the communication complexity of computing the output? I.e., can it be that $cc_{IC}(f)>>cc(f)$? Fadel and Segal show that for every $f$, $cc_{IC}(f)\leq exp(cc(f))$. They also show that fully computing the incentive compatible mechanism is strictly harder than computing only the output: there exists a social choice function $f$ such that $cc_{IC}(f)=cc(f)+1$. In a follow-up work, Babaioff, Blumrosen, Naor, and Schapira [EC'08] provide a social choice function $f$ such that $cc_{IC}(f)=Θ(n\cdot cc(f))$, where $n$ is the number of players. The question of whether the exponential upper bound of Fadel and Segal is tight remained wide open. In this paper we solve this question by explicitly providing an $f$ such that $cc_{IC}(f)= exp(cc(f))$. In fact, we establish this via two very different proofs. In contrast, we show that if the players are risk-neutral and we can compromise on a randomized truthful-in-expectation implementation (and not on deterministic ex-post implementation) gives that $cc_{TIE}(f)=poly(n,cc(f))$ for every function $f$, as long as the domain of $f$ is single parameter or a convex multi-parameter domain. We also provide efficient algorithms for deterministic computation of payments in several important domains.
