The Impossibility of Strategyproof Rank Aggregation

Patrick Lederer

Papers from arXiv.org

Abstract: In rank aggregation, the goal is to combine multiple input rankings into a single output ranking. In this paper, we analyze rank aggregation methods, so-called social welfare functions (SWFs), with respect to strategyproofness, which requires that no agent can misreport her ranking to obtain an output ranking that is closer to her true ranking in terms of the Kemeny distance. As our main result, we show that no anonymous SWF satisfies unanimity and strategyproofness if there are at least four alternatives. This result is proved using SAT solving, a computer-aided theorem-proving technique, and verified using Isabelle/HOL, a highly trustworthy interactive proof assistant. Moreover, we show by hand that strategyproofness is incompatible with majority-consistency, a variant of Condorcet-consistency for SWFs. Lastly, we analyze the incentive ratio of SWFs, which measures the worst-case ratio between a voter's utility when manipulating and when voting honestly. Unfortunately, we show that many natural SWFs have a large incentive ratio and are thus severely manipulable. Specifically, we prove that, if there are $m\geq 4$ alternatives, all positional scoring rules have an unbounded incentive ratio, and all distance scoring rules have an incentive ratio of roughly ${m\choose 2}$. Moreover, we identify an SWF called the Minimal Compromise rule, which has an incentive ratio of $m-2$.

Date: 2026-02, Revised 2026-09
New Economics Papers: this item is included in nep-des and nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://arxiv.org/pdf/2602.06582 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2602.06582

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().