Perfect Implementation of Normal-Form Mechanisms

Tuesday, December 5, 2006 - 4:30pm
Skiles 255
Sergei Izmalkov
Department of Economics, MIT

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).