  We study the necessity of interaction for obtaining efficient allocations in
subadditive combinatorial auctions. This problem was originally introduced by
Dobzinski, Nisan, and Oren (STOC'14) as the following simple market scenario:
$m$ items are to be allocated among $n$ bidders in a distributed setting where
bidders valuations are private and hence communication is needed to obtain an
efficient allocation. The communication happens in rounds: in each round, each
bidder, simultaneously with others, broadcasts a message to all parties
involved and the central planner computes an allocation solely based on the
communicated messages. Dobzinski et.al. showed that no non-interactive
($1$-round) protocol with polynomial communication (in the number of items and
bidders) can achieve approximation ratio better than $\Omega(m^{{1}/{4}})$,
while for any $r \geq 1$, there exists $r$-round protocols that achieve
$\widetilde{O}(r \cdot m^{{1}/{r+1}})$ approximation with polynomial
communication; in particular, $O(\log{m})$ rounds of interaction suffice to
obtain an (almost) efficient allocation.
  A natural question at this point is to identify the "right" level of
interaction (i.e., number of rounds) necessary to obtain an efficient
allocation. In this paper, we resolve this question by providing an almost
tight round-approximation tradeoff for this problem: we show that for any $r
\geq 1$, any $r$-round protocol that uses polynomial communication can only
approximate the social welfare up to a factor of $\Omega(\frac{1}{r} \cdot
m^{{1}/{2r+1}})$. This in particular implies that
$\Omega(\frac{\log{m}}{\log\log{m}})$ rounds of interaction are necessary for
obtaining any efficient allocation in these markets. Our work builds on the
recent multi-party round-elimination technique of Alon, Nisan, Raz, and
Weinstein (FOCS'15) and settles an open question posed by Dobzinski et.al. and
Alon et. al.
