Combinatorial Auctions Do Need Modest Interaction

Author: Sepehr Assadi.
Conference: The 18th ACM Conference on Economics and Computation (EC'17).
This paper resolves an open question raised originally by Dobzinski, Nisan, and Oren [DNO'14] (STOC'14) and subsequently by Alon, Nisan, Raz, and Weinstein [ANRW'15] (FOCS'15).
Abstract: We study the necessity of interaction for obtaining (approximately) efficient allocations in combinatorial auctions with subadditive bidders. 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 effcient allocation. The communication happens in rounds: in each round, each bidder, simultaneously with others, broadcasts a message to all parties involved. At the end, the central planner computes an allocation solely based on the communicated messages. Dobzinski et al. showed that (at least some) interaction is necessary for obtaining any effcient allocation: no non-interactive (1-round) protocol with polynomial communication can achieve approximation ratio better than Ω(m^{1/4}), while for any r ≥ 1, there exists r-round protocols that achieve O(r · m^{1/(r+1)}) approximation; in particular, O(log m) rounds of interaction suffices 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 ≥ 1, any r-round protocol that uses poly(m,n) bits of communication can only approximate the social welfare up to a factor of Ω((1/r) · m^{1/(2r+1)}). This in particular implies that Ω(log{m}/loglog{m}) rounds of interaction are necessary for obtaining an efficient allocation in these markets. Our work builds on the recent multi-party round-elimination technique of Alon, Nisan, Raz, and Weinstein (FOCS’15) – used to prove similar-in-spirit lower bounds for round-approximation tradeoff in unit-demand (matching) markets – and settles an open question posed initially by Dobzinski et al., and subsequently by Alon et al.
Conference version: [PDF]
Full version: [arXiv]