Perfect implementation

• 成果类型: Article
• 署名作者: Izmalkov, Sergei; Lepinski, Matt; Micali, Silvio
• 署名单位: Massachusetts Institute of Technology (MIT); RTX Corporation; Raytheon BBN Technologies; New Economic School
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2010.05.003
• 发表日期: 2011
• 页码: 121-140
• 关键词: Mechanism design; trust; privacy

摘要

Privacy and trust affect our strategic thinking, yet have not been precisely modeled in mechanism design. In settings of incomplete information, traditional implementations of a normal-form mechanism by disregarding the players' privacy, or assuming trust in a mediator may fail to reach the mechanism's objectives. We thus investigate implementations of a new type. We put forward the notion of a perfect implementation of a normal-form mechanism M: in essence, a concrete extensive-form mechanism exactly preserving all strategic properties of M, without relying on trusted mediators or violating the players' privacy. We prove that any normal-form mechanism can be perfectly implemented by a verifiable mediator using envelopes and an envelope-randomizing device. Differently from a trusted mediator, a verifiable one only performs prescribed public actions, so that everyone can verify that he is acting properly, and that he never learns any information that should remain private. (C) 2010 Elsevier Inc. All rights reserved.