The communication requirements of efficient allocations and supporting prices

By Noam Nisan, Ilya Segal. Journal of Economics Theory, 2006

328 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

A Unified Continuous Greedy Algorithm for Submodular Maximization (2011, background): “Most notable is the well studied Submodular Welfare problem (refer to [7], [8], [13]– [15], [17], [18], [30], [38], [44], [47], [48] for previous results on Submodular Welfare and additional closely related variants of the problem).”
Beyond set disjointness: the communication complexity of finding the intersection (2014, background): “We study the minimum number of bits the parties need to communicate in order to compute the intersection set S ∩ T , given a certain number r of messages that are allowed to be exchanged.”
Truthful and near-optimal mechanism design via linear programming (2005, background): “Demand queries are very natural from an economic perspective and are known to be strictly more powerful than value queries [22, 5].”
A Short Introduction to Computational Social Choice (2007, background): “Nisan and Segal [71] have shown this, and the communication requirement remains exponential when all valuations are submodular.”
Combinatorial auctions (2007, unknown): “Besides, (Nisan and Segal, 2006) showed that, in the worst case, identifying an optimal allocation requires an exponential amount of communication in the number of auctioned items.”