  We study the communication complexity of welfare maximization in
combinatorial auctions with $m$ items and two subadditive bidders. A
$\frac{1}{2}$-approximation can be guaranteed by a trivial randomized protocol
with zero communication, or a trivial deterministic protocol with $O(1)$
communication. We show that outperforming these trivial protocols requires
exponential communication, settling an open question of [DobzinskiNS10,
Feige09].
  Specifically, we show that any (randomized) protocol guaranteeing a
$(\frac{1}{2}+\frac{6}{\log_2 m})$-approximation requires communication
exponential in $m$. This is tight even up to lower-order terms: we further
present a $(\frac{1}{2}+\frac{1}{O(\log m)})$-approximation in poly($m$)
communication.
  To derive our results, we introduce a new class of subadditive functions that
are "far from" fractionally subadditive functions, and may be of independent
interest for future works. Beyond our main result, we consider the spectrum of
valuations between fractionally-subadditive and subadditive via the MPH
hierarchy. Finally, we discuss the implications of our results towards
combinatorial auctions with strategic bidders.
