Perfect Implementation

Privacy and trust a effect our strategic thinking, yet they 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 re...

Full description

Bibliographic Details
Main Authors: Izmalkov, Sergei, Lepinski, Matt, Micali, Silvio
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:en_US
Published: Elsevier 2010
Online Access:http://hdl.handle.net/1721.1/50634
https://orcid.org/0000-0002-0816-4064
_version_ 1826217649384718336
author Izmalkov, Sergei
Lepinski, Matt
Micali, Silvio
author2 Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
author_facet Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Izmalkov, Sergei
Lepinski, Matt
Micali, Silvio
author_sort Izmalkov, Sergei
collection MIT
description Privacy and trust a effect our strategic thinking, yet they 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 a trusted mediator or violating the privacy of the players. We prove that any normal-form mechanism can be perfectly implemented by a verifiable mediator using envelopes and an envelope-randomizing device (i.e., the same tools used for running fair lotteries or tallying secret votes). 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.
first_indexed 2024-09-23T17:07:02Z
format Article
id mit-1721.1/50634
institution Massachusetts Institute of Technology
language en_US
last_indexed 2024-09-23T17:07:02Z
publishDate 2010
publisher Elsevier
record_format dspace
spelling mit-1721.1/506342022-10-03T10:30:11Z Perfect Implementation Izmalkov, Sergei Lepinski, Matt Micali, Silvio Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Micali, Silvio Izmalkov, Sergei Micali, Silvio Privacy and trust a effect our strategic thinking, yet they 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 a trusted mediator or violating the privacy of the players. We prove that any normal-form mechanism can be perfectly implemented by a verifiable mediator using envelopes and an envelope-randomizing device (i.e., the same tools used for running fair lotteries or tallying secret votes). 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. National Science Foundation 2010-01-08T15:31:05Z 2010-01-08T15:31:05Z 2010-05 2008-05 Article http://purl.org/eprint/type/SubmittedJournalArticle 0899-8256 http://hdl.handle.net/1721.1/50634 Izmalkov, Sergei, Matt Lepinski, and Silvio Micali. "Perfect Implementation." Games and Economic Behavior, Elsevier, vol. 71(1), pages 121-140. https://orcid.org/0000-0002-0816-4064 en_US http://dx.doi.org/10.1016/j.geb.2010.05.003 Games and Economic Behavior Attribution-Noncommercial-Share Alike 3.0 Unported http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Elsevier Silvio Micali
spellingShingle Izmalkov, Sergei
Lepinski, Matt
Micali, Silvio
Perfect Implementation
title Perfect Implementation
title_full Perfect Implementation
title_fullStr Perfect Implementation
title_full_unstemmed Perfect Implementation
title_short Perfect Implementation
title_sort perfect implementation
url http://hdl.handle.net/1721.1/50634
https://orcid.org/0000-0002-0816-4064
work_keys_str_mv AT izmalkovsergei perfectimplementation
AT lepinskimatt perfectimplementation
AT micalisilvio perfectimplementation