Incentives in Social Decision Schemes with Pairwise Comparison Preferences

Incentives in Social Decision Schemes with Pairwise Comparison Preferences

Felix Brandt, Patrick Lederer, Warut Suksompong

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence
Main Track. Pages 130-136. https://doi.org/10.24963/ijcai.2022/19

Social decision schemes (SDSs) map the preferences of individual voters over multiple alternatives to a probability distribution over the alternatives. In order to study properties such as efficiency, strategyproofness, and participation for SDSs, preferences over alternatives are typically lifted to preferences over lotteries using the notion of stochastic dominance (SD). However, requiring strategyproofness or strict participation with respect to this preference extension only leaves room for rather undesirable SDSs such as random dictatorships. Hence, we focus on the natural but little understood pairwise comparison (PC) preference extension, which postulates that one lottery is preferred to another if the former is more likely to return a preferred outcome. In particular, we settle three open questions raised by Brandt in Rolling the dice: Recent results in probabilistic social choice (2017): (i) there is no Condorcet-consistent SDS that satisfies PC-strategyproofness; (ii) there is no anonymous and neutral SDS that satisfies PC-efficiency and PC-strategyproofness; and (iii) there is no anonymous and neutral SDS that satisfies PC-efficiency and strict PC-participation. All three impossibilities require m>=4 alternatives and turn into possibilities when m<=3.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice