The communication requirements of efficient allocations and supporting prices |
| |
Authors: | Noam Nisan |
| |
Institution: | a Institute of Computer Science, Hebrew University, Jerusalem, Israel b Department of Economics, Stanford University, Stanford, CA 94305, USA |
| |
Abstract: | We show that any communication finding a value-maximizing allocation in a private-information economy must also discover supporting prices (in general personalized and nonlinear). In particular, to allocate L indivisible items between two agents, a price must be revealed for each of the 2L-1 bundles. We prove that all monotonic prices for an agent must be used, hence exponential communication in L is needed. Furthermore, exponential communication is needed just to ensure a higher share of surplus than that realized by auctioning all items as a bundle, or even a higher expected surplus (for some probability distribution over valuations). When the utilities are submodular, efficiency still requires exponential communication (and fully polynomial approximation is impossible). When the items are identical, arbitrarily good approximation is obtained with exponentially less communication than exact efficiency. |
| |
Keywords: | C61 D02 D44 |
本文献已被 ScienceDirect 等数据库收录! |
|