Minimally strategy-proof rank aggregation

Abstract

A rank aggregation rule aggregates finitely many linear orderings of objects to a collective linear ordering of these objects. We consider the robustness of rank aggregation methods to manipulation by misrepresentation of some individual order. This requires formulating assumptions about how individuals compare orders. Betweenness is a natural assumption for rank aggregation rules interpreted as Arrowian aggregation rules, which maps every family of individual preferences over social alternatives to a collective preference over those alternatives. However, many rank aggregation rules do not relate to the classical preference aggregation problem, and call for different assumptions. Instead of focusing on specific assumptions, we only assume that individuals compare orders by means of an order extension, which maps every linear order p over objects to a linear order over orders which places p at top. We define as minimally strategy-proof a rank aggregation rule that cannot be manipulated with respect to at least one order extension. We characterize the class of minimal strategy-proof rules. Based on this characterization, we show that most rules considered in Bossert and Sprumont (2014) and Athanasoglou (2016, 2019) are not minimally strategy-proof (while being betweenness strategy-proof). This emphasizes the critical role of linearity when imposed to order extensions. Moreover, we show that a rule is strategy-proof for a rich domain of order extensions if and only if it is either constant or dictatorial, where richness requires that each ordering of a pair of orders can prevail in some hyper-order. We also discuss the existence of rules that are strategy-proof for all order extensions that satisfy the Kemeny distance criterion.