Randomization in Mechanism Design For Voting Environments - Some Recent Results

The talk will summarize some recent results on strategy-proof random social choice functions in voting environments. The notion of strategy-proofness will that of Gibbard (1977); i.e. the lottery from truth-telling will be required to stochastically dominate that from misrepresentation. A domain will be said to have the deterministic extreme point property (DEP) if every strategy-proof and unanimous random social choice function is a probability mixture of strategy-proof and unanimous deterministic social choice functions over that domain. The results of Gibbard (1977) and the Gibbard-Satterthwaite Theorem imply that the complete domain has the DEP property. The talk will present recent results (Picot-Sen (2012), Peters-Roy-Sen-Storcken (2013), Pycia-Unver (2013), Chatterji-Roy-Sen (2012)) which have shown that familiar domains such as (i) the binary domain (ii) the single-peaked domain and (iii) the multi-dimensional domain with (lexicographically) separable preferences have the DEP property. The focus of the talk will be the paper Chatterji-Sen-Zeng (2012) which shows that dictatorial domains do not have the DEP property, i.e. a domain on which every unanimous, strategy-proof deterministic social choice function is dictatorial is not one on which every strategy-proof, unanimous, random social choice function is a random dictatorship. The paper also presents additional restrictions on domains that are sufficient to ensure that every dictatorial domain is a random dictatorship domain.

Please click here to download paper.