The communication cost of selfishness

• 成果类型: Article
• 署名作者: Fadel, Ronald; Segal, Ilya
• 署名单位: Stanford University
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2007.09.015
• 发表日期: 2009
• 页码: 1895-1920
• 关键词: Communication complexity; Algorithmic mechanism design; Bayesian incentive compatibility; ex post incentive compatibility; Sequential and simultaneous communication protocols; Information sets

摘要

We consider how many bits need to be exchanged to implement a given decision rule when the mechanism must be ex post or Bayesian incentive compatible. For ex post incentive compatibility, the communication protocol must reveal enough information to calculate monetary transfers to the agents to motivate them to be truthful (agents' payoffs are assumed to be quasilinear in such transfers). For Bayesian incentive compatibility, the protocol may need to hide some information from the agents to prevent deviations contingent on the information. In both settings with selfish agents, the communication cost can be higher than in the case in which the agents are honest and can be relied upon to report truthfully. The increase is the communication cost of selfishness. We provide an exponential upper bound on the increase. We show that the bound is tight in the Bayesian setting, but we do not know this in the ex post setting. We describe some cases where the communication cost of selfishness proves to be very low. (C) 2009 Elsevier Inc. All rights reserved.