Perfect Implementation of Normal-Form Mechanisms
Privacy and trust affect 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 not be re...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Published: |
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/38208 |
| _version_ | 1811096372687929344 |
|---|---|
| author | Izmalkov, Sergei Lepinski, Matt Micali, Silvio |
| author2 | Silvio Micali |
| author_facet | Silvio Micali Izmalkov, Sergei Lepinski, Matt Micali, Silvio |
| author_sort | Izmalkov, Sergei |
| collection | MIT |
| description | Privacy and trust affect 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 not be realistic and 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, an extensive-form mechanism exactly preserving all strategic properties of M, without relying on a trusted party or violating the privacy of the players.We prove that ANY normal-form mechanism can be perfectly implemented via envelopes and an envelope-randomizing device (i.e., the same tools used for running fair lotteries or tallying secret votes). |
| first_indexed | 2024-09-23T16:42:47Z |
| id | mit-1721.1/38208 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:42:47Z |
| publishDate | 2007 |
| record_format | dspace |
| spelling | mit-1721.1/382082019-04-12T08:38:33Z Perfect Implementation of Normal-Form Mechanisms Izmalkov, Sergei Lepinski, Matt Micali, Silvio Silvio Micali Theory of Computation Mechanism Design Privacy Privacy Equivalence Strategic Equivalence Perfect Implementation Privacy and trust affect 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 not be realistic and 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, an extensive-form mechanism exactly preserving all strategic properties of M, without relying on a trusted party or violating the privacy of the players.We prove that ANY normal-form mechanism can be perfectly implemented via envelopes and an envelope-randomizing device (i.e., the same tools used for running fair lotteries or tallying secret votes). 2007-07-30T16:01:48Z 2007-07-30T16:01:48Z 2005 MIT-CSAIL-TR-2007-040 http://hdl.handle.net/1721.1/38208 Ealier Version in 46th Foundation of Computer Science Conference Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 51 p. application/pdf application/postscript |
| spellingShingle | Mechanism Design Privacy Privacy Equivalence Strategic Equivalence Perfect Implementation Izmalkov, Sergei Lepinski, Matt Micali, Silvio Perfect Implementation of Normal-Form Mechanisms |
| title | Perfect Implementation of Normal-Form Mechanisms |
| title_full | Perfect Implementation of Normal-Form Mechanisms |
| title_fullStr | Perfect Implementation of Normal-Form Mechanisms |
| title_full_unstemmed | Perfect Implementation of Normal-Form Mechanisms |
| title_short | Perfect Implementation of Normal-Form Mechanisms |
| title_sort | perfect implementation of normal form mechanisms |
| topic | Mechanism Design Privacy Privacy Equivalence Strategic Equivalence Perfect Implementation |
| url | http://hdl.handle.net/1721.1/38208 |
| work_keys_str_mv | AT izmalkovsergei perfectimplementationofnormalformmechanisms AT lepinskimatt perfectimplementationofnormalformmechanisms AT micalisilvio perfectimplementationofnormalformmechanisms |