Purification of incentive compatible allocations

In implementation theory it is common to consider social choice functions that map to lotteries over outcomes. For example, virtual implementation has been used widely with social choice functions that involve randomization. This paper investigates (in incomplete information environments) the possibility of purification of such social choice functions, where purification means that the “replacement” social choice function maps to outcomes rather than distributions over outcomes, is incentive compatible and generates the same distribution over payoffs and outcomes as the original social choice function. Received: July 31, 2000; revised version: December 2, 2002 RID="*" ID="*" Thanks are due to Ole Nielsen, Terence Tao and Lin Zhou for helpful conversations. Thanks are also due to an anonymous referee for detailed comments.