  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)=\Theta(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.
