The communication requirements of efficient allocations and supporting prices

• 成果类型: Article
• 署名作者: Nisan, Noam; Segal, Ilya
• 署名单位: Stanford University; Hebrew University of Jerusalem
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2004.10.007
• 发表日期: 2006
• 页码: 192-224
• 关键词: Communication complexity; message space dimension; Preference elicitation; informational efficiency of prices; combinatorial auctions; submodular valuations; substitutable items; homogenous items; approximation; distributional complexity

摘要

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 2(L) - 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. (c) 2005 Elsevier Inc. All rights reserved.