论文标题
自私概念之间的指数沟通分离
Exponential Communication Separations between Notions of Selfishness
论文作者
论文摘要
我们考虑了在多个玩家之间实现固定的社交选择功能的问题（将每个播放器的输入$ t_i $从每个播放器$ i $中取出，并输出结果$ f（t_1，\ ldots，t_n）$），其中必须激励每个玩家遵循协议。特别是，我们研究了一项协议的沟通要求：（a）实现$ f $的$ f $，计算付款，使其遵守该协议，并使其实现$ f $（EPIC）遵守协议，并且（c）实现$ f $并以一种使其以某种方式计算付款，从而使其占主导地位的强度易变的概括（DSIC）以遵循该协议（DSIC）。 我们显示了所有这三个数量之间的指数分离，仅针对两个玩家。也就是说，我们首先构建了$ f $，以便可以在通信$ c $中实现$ f $，但是任何EPIC实施$ f $（任何付款选择）都需要通信$ \ exp（c）$。这回答了[FS09，BBS13]的公开问题。其次，我们构建了一个$ f $，以便Epic协议将$ f $与通信$ c $实现，但是所有DSIC实现$ f $都需要通信$ \ exp（c）$。
We consider the problem of implementing a fixed social choice function between multiple players (which takes as input a type $t_i$ from each player $i$ and outputs an outcome $f(t_1,\ldots, t_n)$), in which each player must be incentivized to follow the protocol. In particular, we study the communication requirements of a protocol which: (a) implements $f$, (b) implements $f$ and computes payments that make it ex-post incentive compatible (EPIC) to follow the protocol, and (c) implements $f$ and computes payments in a way that makes it dominant-strategy incentive compatible (DSIC) to follow the protocol. We show exponential separations between all three of these quantities, already for just two players. That is, we first construct an $f$ such that $f$ can be implemented in communication $c$, but any EPIC implementation of $f$ (with any choice of payments) requires communication $\exp(c)$. This answers an open question of [FS09, BBS13]. Second, we construct an $f$ such that an EPIC protocol implements $f$ with communication $C$, but all DSIC implementations of $f$ require communication $\exp(C)$.
