TY - GEN

T1 - Welfare Maximization with Limited Interaction

AU - Alon, Noga

AU - Nisan, Noam

AU - Raz, Ran

AU - Weinstein, Omri

PY - 2015/12/11

Y1 - 2015/12/11

N2 - 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 communication 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 n(1/(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 Omega(n(exp(-r)), implying an Omega(log log n) 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].

AB - 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 communication 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 n(1/(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 Omega(n(exp(-r)), implying an Omega(log log n) 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].

KW - Distributed matchings

KW - Information theory

KW - Multiparty Communication complexity

KW - Welfare maximization

UR - http://www.scopus.com/inward/record.url?scp=84960350016&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84960350016&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2015.95

DO - 10.1109/FOCS.2015.95

M3 - Conference contribution

AN - SCOPUS:84960350016

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 1499

EP - 1512

BT - Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015

PB - IEEE Computer Society

T2 - 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015

Y2 - 17 October 2015 through 20 October 2015

ER -