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...
Main Authors: | , , |
---|---|
Other Authors: | |
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 |