Welfare Maximization with Limited Interaction

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model where agent’s valuations are unknown to the central planner, and therefore commu-nication is required to determine an efficient allocation. Dobzinski, Nisan and Oren (STOC’14) showed that if the market size is n, then r rounds of interaction (with logarithmic bandwidth) suffice to obtain an n1/(r+1)-approximation to the optimal social welfare. In particular, this implies that such markets converge to a stable state (constant approximation) in time logarithmic in the market size. We obtain the first multi-round lower bound for this setup. We show that even if the allowable per-round bandwidth of each agent is nε(r), the approximation ratio of any r-round (randomized) protocol is no better than Ω(n1/5 r+1), implying an Ω(log logn) lower bound on the rate of convergence of the market to equilibrium. Our construction and technique may be of interest to round-communication tradeoffs in the more general setting of combinatorial auctions, for which the only known lower bound is for simultaneous (r = 1) protocols [DNO14]