p.993

Virtual Implementation in Iteratively Undominated Strategies: Complete Information

Dilip Abreu
Hitoshi Matsushima

Abstract

We investigate the implementation of social choice functions in complete information environments. We consider social choice functions (scf's) which map from a finite set of preference profiles to lotteries over alternatives, and require virtual implementation in iteratively undominated strategies. An scf $x$ is virtually implementable in iteratively undominated strategies if for all $\varepsilon > 0$, there exists an scf $y$ which is $\varepsilon$-close to $x$ (that is, for all preference profiles, $x$ and $y$ map to lotteries which are within $\varepsilon$ of one another) and which is (exactly) implementable in iteratively undominated strategies. Under very weak domain restrictions we show that if there are three or more players, any scf is virtually implementable in iteratively undominated strategies. A noteworthy feature of our constructions is that we only employ finite mechanisms. As a corollary, we obtain virtual implementation in (pure and) mixed strategy Nash equilibrium using well-behaved (in particular, finite) mechanisms. The literature on implementation in Nash equilibrium and its refinements is compromised by its reliance on game forms with unnatural features (for example, "integer" games), or "modulo" constructions with mixed strategies arbitrarily excluded. In contrast, our results allow for mixed strategies and do not rely on mechanisms with obviously suspicious features.