On the Incompatibility of Efficiency and Strategyproofness in Randomized Social Choice
Efficiency—no agent can be made better off without making another one worse off—and strategyproofness—no agent can obtain a more preferred outcome by misrepresenting his preferences—are two cornerstones of economics and ubiquitous in important areas such as voting, auctions, or matching markets. Within the context of random assignment, Bogomolnaia and Moulin have shown that two particular notions of efficiency and strategyproofness based on stochastic dominance are incompatible. However, there are various other possibilities of lifting preferences over alternatives to preferences over lotteries apart from stochastic dominance. In this paper, we give an overview of common preference ex- tensions, propose two new ones, and show that the above- mentioned incompatibility can be extended to various other notions of strategyproofness and efficiency in randomized social choice.