Strategy-proof preference aggregation and the anonymity-neutrality tradeoff

Consider a setting in which individual strict preferences need to be aggregated into a social strict preference relation. For two alternatives and an odd number of agents, it follows from May's Theorem that the majority aggregation rule is the only one satisfying anonymity, neutrality and strategy-proofness (SP). For more than two alternatives, anonymity and neutrality are incompatible for many problem instances and we explore this tradeoff for strategy-proof rules. The notion of SP that we employ is Kemeny-SP (K-SP), which is based on the Kemeny distance between social orderings and strengthens previously used concepts in an intuitive manner. Dropping anonymity and keeping neutrality, we identify and analyze the first known nontrivial family of K-SP rules, namely semi-dictator rules. For two agents, semi-dictator rules are characterized by strong unanimity, neutrality and K-SP. For an arbitrary number of agents, we generalize semi-dictator rules to allow for committees and show that they retain their desirable properties. Dropping neutrality and keeping anonymity, we establish possibility results for three alternatives. We provide a computer-aided solution to the existence of a strongly unanimous, anonymous and K-SP rule for two agents and four alternatives. Finally, we show that there is no K-SP and anonymous rule which always chooses one of the agents' preferences.