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 Ω(n 1/5 r+1 ), implying an Ω(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]. This paper studies the tradeoff between the amount of communication and the number of rounds of interaction required to find an (approximately) optimal matching in a bipartite graph. In our model there are n "players" and m "items". Each player initially knows a subset of the items to which it may be matched (i.e. m bits of information). The players communicate in rounds: in each round each player writes a message on a shared blackboard. The message can only depend on what the player knows at that stage: his initial input and all the messages by all other players that were written on the blackboard in previous rounds. This problem was recently introduced by [DNO14] as a simple market scenario: the players are unit-demand 1 bidders and our goal is to find an (approximately) welfare-maximizing allocation of the items to players. The classic auction of [DGS86] -that may be viewed as a simple Walrasian-like market process for this setting -can be implemented as to find an approximately optimal allocation where each player needs only send O(log n) bits of communication (on the average). The question considered by [DNO14] was whether such a low communication burden suffices without using multiple rounds of interaction. As a lower bound, they proved that a non-interactive protocol, i.e. one that uses a single round of communication, cannot get a n 1/2− -factor approximation (for any fixed > 0) with n o(1) bits of communication per player. As upper bounds they exhibited (I) an O(log n)-round protocol, where each player sends O(log n) bits per round, that gets a 1 1−δ -factor approximation (for any fixed δ > 0) and (II) for any fixed r ≥ 1, an r-round protocol, where each player sends O(log n) bits per round, that gets an O(n 1/(r+1) )-approximation. 2 Besides of the fact that the lower bound in [GO13] applies only for testing exact matchings and not approximate matchings, their model consists of a small number of parties (constant or logarithmic in n) who are communicating in some fixed number of sequential rounds (not simultaneous). The input itself of each player is therefore super-linear in the number of nodes of the input graph (n), and indeed they prove a super-linear communication lower bound, which is clearly impossible in our model. The [GO13] model was motivated by streaming lower bounds and does not seem to capture the economic scenario we attempt to model in this paper (i.e., that of private-valuations) and therefore this result is incomparable to ours, as also evidenced by the distinct proof-techniques. 3 In which the graph edges are distributed among only two players. can be trivially achieved by one of the two players). Certainly, as the two-party model is stronger, no better lower bounds are known. There are many open problems related to our work. Let us mention a few of the most natural ones. Our first open problem is closing the gap between our lower bound and the upper bound: We show that r = Ω(log log n) rounds of communication are required to achieve constant approximation ratio using poly-logarithmic bits per player, while the upper bound is r = O(log n). We believe that the upper bound is in fact tight, and improving the lower bound is left as our first and direct open problem. Another interesting direction is trying to extend our lower bound technique to obtain similar-in-spirit roundcommunication tradeoffs for the more general setup of combinatorial auctions, also studied by [DNO14] . From a communication complexity perspective, lower bounds in this setup are more compelling, since player valuations require exponentially many bits to encode, hence interaction has the potential to reduce the overall communication (required to obtain efficient allocations) from exponential to polynomial. Indeed, it is shown in [DNO14] that, in the case of sub-additive bidders, there is an r-round randomized protocol that obtains anÕ(r ·m 1/(r+1) )-approximation to the optimal social welfare, where in each round each player sends poly(m, n) bits. Once again, an (exponential in m) lower bound on the communication was given only for the case of simultaneous protocols (r = 1) and the natural question is to extend it to multiple rounds as well. A more general open problem advocated by [DNO14] is to analyze the communication complexity of finding an exact optimal matching. One may naturally conjecture that n Ω(1) rounds of interaction are required for this if each player only sends n o(1) bits in each round, but no super-logarithmic bound is known. The communication complexity of the problem without any limitation on the number of rounds is also open: no significantly super linear, ω(n log n), lower bound is known, while the best upper bound known isÕ(n 3/2 ).
In a follow-up work, Alon et al. REF obtained the first non-trivial lower bound on the number of rounds for general randomized protocols.
Welfare Maximization with Limited Interaction
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
Mathematics Computer Science