  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)$.
