IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2602.06582.html

The Impossibility of Strategyproof Rank Aggregation

Author

Listed:
  • Manuel Eberl
  • Patrick Lederer

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 his ranking to obtain an output ranking that is closer to his true ranking in terms of the Kemeny distance. As our main result, we show that no anonymous SWF satisfies unanimity and strategyproofness when there are at least four alternatives. This result is proven by SAT solving, a computer-aided theorem proving technique, and verified by Isabelle, a highly trustworthy interactive proof assistant. Further, we prove by hand that strategyproofness is incompatible with majority consistency, a variant of Condorcet-consistency for SWFs. Lastly, we show that all SWFs in two natural classes have a large incentive ratio and are thus highly manipulable.

Suggested Citation

  • Manuel Eberl & Patrick Lederer, 2026. "The Impossibility of Strategyproof Rank Aggregation," Papers 2602.06582, arXiv.org.
    • Handle: RePEc:arx:papers:2602.06582
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2602.06582
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Shmuel Nitzan & Ariel Rubinstein, 1981. "A further characterization of Borda ranking method," Public Choice, Springer, vol. 36(1), pages 153-158, January.
    2. Chatterji, Shurojit & Zeng, Huaxia, 2023. "A taxonomy of non-dictatorial unidimensional domains," Games and Economic Behavior, Elsevier, vol. 137(C), pages 228-269.
    3. Athanasoglou, Stergios & Bonkoungou, Somouaoga & Ehlers, Lars, 2025. "Strategy-proof preference aggregation and the anonymity-neutrality tradeoff," Games and Economic Behavior, Elsevier, vol. 152(C), pages 216-240.
    4. Felix Brand & Patrick Lederer & Sascha Tausch, 2023. "Strategyproof Social Decision Schemes on Super Condorcet Domains," Papers 2302.12140, arXiv.org.
    5. Athanasoglou, Stergios, 2016. "Strategyproof and efficient preference aggregation with Kemeny-based criteria," Games and Economic Behavior, Elsevier, vol. 95(C), pages 156-167.
    6. Athanasoglou, Stergios, 2019. "Solidarity and efficiency in preference aggregation: A tale of two rules," Games and Economic Behavior, Elsevier, vol. 118(C), pages 126-140.
    7. Dietrich, Franz & List, Christian, 2007. "Strategy-Proof Judgment Aggregation," Economics and Philosophy, Cambridge University Press, vol. 23(3), pages 269-300, November.
    8. Can, Burak & Storcken, Ton, 2018. "A re-characterization of the Kemeny distance," Journal of Mathematical Economics, Elsevier, vol. 79(C), pages 112-116.
    9. Brandt, Felix & Lederer, Patrick & Suksompong, Warut, 2023. "Incentives in social decision schemes with pairwise comparison preferences," Games and Economic Behavior, Elsevier, vol. 142(C), pages 266-291.
    10. Brandt, Felix & Saile, Christian & Stricker, Christian, 2022. "Strategyproof social choice when preferences and outcomes may contain ties," Journal of Economic Theory, Elsevier, vol. 202(C).
    11. Wulf Gaertner, 2019. "Kenneth Arrow’s impossibility theorem stretching to other fields," Public Choice, Springer, vol. 179(1), pages 125-131, April.
    12. K. J. Arrow & A. K. Sen & K. Suzumura (ed.), 2002. "Handbook of Social Choice and Welfare," Handbook of Social Choice and Welfare, Elsevier, edition 1, volume 1, number 1.
    13. Lederer, Patrick, 2024. "Bivariate scoring rules: Unifying the characterizations of positional scoring rules and Kemeny's rule," Journal of Economic Theory, Elsevier, vol. 218(C).
    14. Kelly, Jerry S, 1977. "Strategy-Proofness and Social Choice Functions without Singlevaluedness," Econometrica, Econometric Society, vol. 45(2), pages 439-446, March.
    15. Can, Burak & Storcken, Ton, 2013. "Update monotone preference rules," Mathematical Social Sciences, Elsevier, vol. 65(2), pages 136-149.
    16. Harless, Patrick, 2016. "Solidarity in preference aggregation: Improving on a status quo," Games and Economic Behavior, Elsevier, vol. 95(C), pages 73-87.
    17. Manuel Eberl & Patrick Lederer, 2026. "The Impossibility of Strategyproof Rank Aggregation," Papers 2602.06582, arXiv.org.
    18. Gibbard, Allan, 1973. "Manipulation of Voting Schemes: A General Result," Econometrica, Econometric Society, vol. 41(4), pages 587-601, July.
    19. Zoi Terzopoulou & Ulle Endriss, 2019. "Strategyproof judgment aggregation under partial information," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 53(3), pages 415-442, October.
    20. Bossert, Walter & Sprumont, Yves, 2014. "Strategy-proof preference aggregation: Possibilities and characterizations," Games and Economic Behavior, Elsevier, vol. 85(C), pages 109-126.
    21. Hayrullah Dindar & Onur Doğan & Jean Lainé, 2025. "Minimally strategy-proof rank aggregation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 65(1), pages 117-147, August.
    22. Patrick Lederer & Dominik Peters & Tomasz Wk{a}s, 2024. "The Squared Kemeny Rule for Averaging Rankings," Papers 2404.08474, arXiv.org.
    23. H. Moulin, 1980. "On strategy-proofness and single peakedness," Public Choice, Springer, vol. 35(4), pages 437-455, January.
    24. Stergios Athanasoglou & Somouaoga Bonkoungou & Lars Ehlers, 2023. "Strategy-proof preference aggregation and the anonymity-neutrality tradeoff," Working Papers 519, University of Milano-Bicocca, Department of Economics, revised Apr 2025.
    25. Shin Sato, 2015. "Bounded response and the equivalence of nonmanipulability and independence of irrelevant alternatives," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 44(1), pages 133-149, January.
    26. Smith, John H, 1973. "Aggregation of Preferences with Variable Electorate," Econometrica, Econometric Society, vol. 41(6), pages 1027-1041, November.
    27. Zoi Terzopoulou & Ulle Endriss, 2019. "Strategyproof judgment aggregation under partial information," Post-Print hal-04809526, HAL.
    28. Gibbard, Allan, 1977. "Manipulation of Schemes That Mix Voting with Chance," Econometrica, Econometric Society, vol. 45(3), pages 665-681, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Manuel Eberl & Patrick Lederer, 2026. "The Impossibility of Strategyproof Rank Aggregation," Papers 2602.06582, arXiv.org.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Athanasoglou, Stergios & Bonkoungou, Somouaoga & Ehlers, Lars, 2025. "Strategy-proof preference aggregation and the anonymity-neutrality tradeoff," Games and Economic Behavior, Elsevier, vol. 152(C), pages 216-240.
    2. Stergios Athanasoglou & Somouaoga Bonkoungou & Lars Ehlers, 2023. "Strategy-proof preference aggregation and the anonymity-neutrality tradeoff," Working Papers 519, University of Milano-Bicocca, Department of Economics, revised Apr 2025.
    3. Patrick Lederer, 2025. "Robust Voting Rules on the Interval Domain," Papers 2509.04874, arXiv.org.
    4. Burak Can & Peter Csoka & Emre Ergin, 2017. "How to choose a non-manipulable delegation?," KRTK-KTI WORKING PAPERS 1713, Institute of Economics, Centre for Economic and Regional Studies.
    5. Felix Brandt & Patrick Lederer, 2024. "Weak Strategyproofness in Randomized Social Choice," Papers 2412.11977, arXiv.org.
    6. Csóka, Péter & Kondor, Gábor, 2019. "Delegációk igazságos kiválasztása társadalmi választások elméletével [Choosing a fair delegation by social choice theory]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(7), pages 771-787.
    7. Lederer, Patrick, 2024. "Bivariate scoring rules: Unifying the characterizations of positional scoring rules and Kemeny's rule," Journal of Economic Theory, Elsevier, vol. 218(C).
    8. Burak Can & Péter Csóka & Emre Ergin, 2021. "How to choose a fair delegation?," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 72(4), pages 1339-1373, November.
    9. Hayrullah Dindar & Onur Doğan & Jean Lainé, 2025. "Minimally strategy-proof rank aggregation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 65(1), pages 117-147, August.
    10. Fujun Hou, 2024. "A new social welfare function with a number of desirable properties," Papers 2403.16373, arXiv.org.
    11. Can, Burak & Csóka, Péter & Ergin, Emre, 2017. "How to choose a delegation for a peace conference?," Research Memorandum 008, Maastricht University, Graduate School of Business and Economics (GSBE).
    12. Stergios, Athanasoglou, 2017. "An investigation of weak-veto rules in preference aggregation," Working Papers 363, University of Milano-Bicocca, Department of Economics, revised 18 Feb 2017.
    13. Felix Brandt, 2015. "Set-monotonicity implies Kelly-strategyproofness," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 45(4), pages 793-804, December.
    14. Patrick Lederer, 2025. "Proportional Representation in Rank Aggregation," Papers 2508.16177, arXiv.org.
    15. Gilbert Laffond & Jean Lainé & M. Remzi Sanver, 2020. "Metrizable preferences over preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 55(1), pages 177-191, June.
    16. Aditya Aradhye & Hans Peters, 2024. "Group strategy-proof rules in multidimensional binary domains," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 63(1), pages 103-124, August.
    17. Ville Korpela, 2023. "Irresolute mechanism design: a new path to possibility," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(4), pages 993-1007, December.
    18. Raffaele Berzi & Daniela Bubboloni & Michele Gori, 2025. "Manipulation of social choice correspondences under incomplete information," Papers 2503.23141, arXiv.org, revised Dec 2025.
    19. Felix Brandt & Patrick Lederer & René Romen, 2024. "Relaxed notions of Condorcet-consistency and efficiency for strategyproof social decision schemes," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 63(1), pages 19-55, August.
    20. Brandt, Felix & Saile, Christian & Stricker, Christian, 2022. "Strategyproof social choice when preferences and outcomes may contain ties," Journal of Economic Theory, Elsevier, vol. 202(C).

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2602.06582. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.