  We study the communication complexity of dominant strategy implementations of
combinatorial auctions. We start with two domains that are generally considered
"easy": multi-unit auctions with decreasing marginal values and combinatorial
auctions with gross substitutes valuations. For both domains we have fast
algorithms that find the welfare-maximizing allocation with communication
complexity that is poly-logarithmic in the input size. This immediately implies
that welfare maximization can be achieved in ex-post equilibrium with no
significant communication cost, by using VCG payments. In contrast, we show
that in both domains the communication complexity of any dominant strategy
implementation that achieves the optimal welfare is polynomial in the input
size.
  We then move on to studying the approximation ratios achievable by dominant
strategy mechanisms. For multi-unit auctions with decreasing marginal values,
we provide a dominant-strategy communication FPTAS. For combinatorial auctions
with general valuations, we show that there is no dominant strategy mechanism
that achieves an approximation ratio better than $m^{1-\epsilon}$ that uses
$poly(m,n)$ bits of communication, where $m$ is the number of items and $n$ is
the number of bidders. In contrast, a \emph{randomized} dominant strategy
mechanism that achieves an $O(\sqrt m)$ approximation with $poly(m,n)$
communication is known. This proves the first gap between computationally
efficient deterministic dominant strategy mechanisms and randomized ones.
  En route, we answer an open question on the communication cost of
implementing dominant strategy mechanisms for more than two players, and also
solve some open problems in the area of simultaneous combinatorial auctions.
