The communication burden of payment determination

• 成果类型: Article
• 署名作者: Babaioff, Moshe; Blumrosen, Liad; Schapira, Michael
• 署名单位: Hebrew University of Jerusalem; Hebrew University of Jerusalem; Hebrew University of Jerusalem
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2012.08.007
• 发表日期: 2013
• 页码: 153-167
• 关键词: Implementation; mechanism design; communication complexity; revelation principle

摘要

In the presence of self-interested parties, mechanism designers typically aim to implement some social-choice function in an equilibrium. This paper studies the cost of such equilibrium requirements in terms of communication. While a certain amount of information x needs to be communicated just for computing the outcome of a certain social-choice function, an additional amount of communication may be required for computing the equilibrium-supporting payments (if exist). Our main result shows that the total amount of information required for this task can be greater than x by a factor linear in the number of players n, i.e., n . x (under a common normalization assumption). This is the first known lower bound for this problem. In fact, we show that this result holds even in single-parameter domains. On the positive side, we show that certain classic economic domains, namely, single-item auctions and public-good mechanisms, only entail a small overhead. (c) 2012 Elsevier Inc. All rights reserved.