p.997

Virtual Implementation in Nash Equilibrium

Dilip Abreu
Arunava Sen

Abstract

Reformulate the classical implementation problem a la Maskin (1977) as follows. Think of a social choice correspondence as a mapping from preference profiles to lotteries over some finite set of alternative. Say that a soical choice function $f$ is virtually implementable in Nash equilibrium if for all $\epsilon > 0$ there exists a game from $G$ such that for all preference profiles $\theta, G$ has a unique equilibrium outcome $x(\theta)$, and $x(\theta)$ is $\epsilon$-close to $f(\theta)$. (This definition may be directly extended to social choice correspondences.) Then (under mild domain restrictions) the following result is true: In societies with at least three individuals all social choice correspondences are virtually implementable in Nash equilibrium. This proposition should be contrasted with Maskin's (1977) classic characterization, according to which the nontrivial requirement of monotonicity is a necessary condition for exact implementation in Nash equilibrium. The two-person case needs to be considered separately. We provide a complete characterization of virtually implementable two-person social choice functions. While not all two-person social choice functions are virtually implementable, our necessary and sufficient condition is simple. This contrasts with the rather complex necessary and sufficient conditions for exact implementation. We show how our results can be extended to implementation in strict Nash equilibrium and coalition-proof Nash equilibrium, to social choice correspondences which map from cardinal preference profiles to lotteries, and to environments with a continuum of pure alternatives.