IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2202.08656.html
   My bibliography  Save this paper

Robust Sparse Voting

Author

Listed:
  • Youssef Allouah
  • Rachid Guerraoui
  • L^e-Nguy^en Hoang
  • Oscar Villemaud

Abstract

Many applications, such as content moderation and recommendation, require reviewing and scoring a large number of alternatives. Doing so robustly is however very challenging. Indeed, voters' inputs are inevitably sparse: most alternatives are only scored by a small fraction of voters. This sparsity amplifies the effects of biased voters introducing unfairness, and of malicious voters seeking to hack the voting process by reporting dishonest scores. We give a precise definition of the problem of robust sparse voting, highlight its underlying technical challenges, and present a novel voting mechanism addressing the problem. We prove that, using this mechanism, no voter can have more than a small parameterizable effect on each alternative's score; a property we call Lipschitz resilience. We also identify conditions of voters comparability under which any unanimous preferences can be recovered, even when each voter provides sparse scores, on a scale that is potentially very different from any other voter's score scale. Proving these properties required us to introduce, analyze and carefully compose novel aggregation primitives which could be of independent interest.

Suggested Citation

  • Youssef Allouah & Rachid Guerraoui & L^e-Nguy^en Hoang & Oscar Villemaud, 2022. "Robust Sparse Voting," Papers 2202.08656, arXiv.org, revised Jan 2024.
    • Handle: RePEc:arx:papers:2202.08656
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Stephan Morgenthaler, 2007. "A survey of robust statistics," Statistical Methods & Applications, Springer;Società Italiana di Statistica, vol. 16(1), pages 171-172, June.
    2. Stephan Morgenthaler, 2007. "A survey of robust statistics," Statistical Methods & Applications, Springer;Società Italiana di Statistica, vol. 15(3), pages 271-293, February.
    3. Stephan Morgenthaler, 2007. "A survey of robust statistics," Statistical Methods & Applications, Springer;Società Italiana di Statistica, vol. 15(3), pages 271-293, February.
    4. Editors The, 2009. "Content," Basic Income Studies, De Gruyter, vol. 4(1), pages 1-1, August.
    5. Amartya Sen, 1999. "The Possibility of Social Choice," American Economic Review, American Economic Association, vol. 89(3), pages 349-378, June.
    6. Kenneth J. Arrow, 1950. "A Difficulty in the Concept of Social Welfare," Journal of Political Economy, University of Chicago Press, vol. 58(4), pages 328-328.
    7. Michel Balinski & Rida Laraki, 2011. "Majority Judgment: Measuring, Ranking, and Electing," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262015137, December.
    8. Erick Moreno-Centeno & Adolfo R. Escobedo, 2016. "Axiomatic aggregation of incomplete rankings," IISE Transactions, Taylor & Francis Journals, vol. 48(6), pages 475-488, June.
    Full references (including those not matched with items on IDEAS)

    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. Cerioli, Andrea & Farcomeni, Alessio, 2011. "Error rates for multivariate outlier detection," Computational Statistics & Data Analysis, Elsevier, vol. 55(1), pages 544-553, January.
    2. Roland Fried & Herold Dehling, 2011. "Robust nonparametric tests for the two-sample location problem," Statistical Methods & Applications, Springer;Società Italiana di Statistica, vol. 20(4), pages 409-422, November.
    3. Christophe Croux & Catherine Dehon, 2010. "Influence functions of the Spearman and Kendall correlation measures," Statistical Methods & Applications, Springer;Società Italiana di Statistica, vol. 19(4), pages 497-515, November.
    4. Leonid Hanin, 2021. "Cavalier Use of Inferential Statistics Is a Major Source of False and Irreproducible Scientific Findings," Mathematics, MDPI, vol. 9(6), pages 1-13, March.
    5. Alfons, A. & Ates, N.Y. & Groenen, P.J.F., 2018. "A Robust Bootstrap Test for Mediation Analysis," ERIM Report Series Research in Management ERS-2018-005-MKT, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    6. Eugster, Manuel J.A. & Leisch, Friedrich, 2011. "Weighted and robust archetypal analysis," Computational Statistics & Data Analysis, Elsevier, vol. 55(3), pages 1215-1225, March.
    7. repec:jss:jstsof:32:i03 is not listed on IDEAS
    8. Ada Ferrer-i-Carbonell, 2002. "Subjective Questions to Measure Welfare and Well-being," Tinbergen Institute Discussion Papers 02-020/3, Tinbergen Institute.
    9. Todorov, Valentin & Filzmoser, Peter, 2009. "An Object-Oriented Framework for Robust Multivariate Analysis," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 32(i03).
    10. Kotaro Suzumura, 2002. "Introduction to social choice and welfare," Temi di discussione (Economic working papers) 442, Bank of Italy, Economic Research and International Relations Area.
    11. Antoinette Baujard, 2016. "Welfare economics," Chapters, in: Gilbert Faccarello & Heinz D. Kurz (ed.), Handbook on the History of Economic Analysis Volume III, chapter 42, pages 611-624, Edward Elgar Publishing.
    12. Nicola Cantore, 2005. "Reconsidering the Environmental Kuznets Curve hypothesis: the trade off between environment and welfare," Working Papers 13, ECINEQ, Society for the Study of Economic Inequality.
    13. Grainger, Daniel & Watkin-Lui, Felecia & Cheer, Karen, 2021. "The value of informed agency for Torres Strait climate change," Ecological Economics, Elsevier, vol. 180(C).
    14. Zhijun Zhao, 2011. "Preference Relativity, Ambiguity and Social Welfare Evaluation," Working Papers 352011, Hong Kong Institute for Monetary Research.
    15. Sunhee Baik & Alexander L. Davis & M. Granger Morgan, 2019. "Illustration of a Method to Incorporate Preference Uncertainty in Benefit–Cost Analysis," Risk Analysis, John Wiley & Sons, vol. 39(11), pages 2359-2368, November.
    16. Justin Kruger & M. Remzi Sanver, 2021. "An Arrovian impossibility in combining ranking and evaluation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(3), pages 535-555, October.
    17. Ada Ferrer-i-Carbonell, 2013. "Happiness economics," SERIEs: Journal of the Spanish Economic Association, Springer;Spanish Economic Association, vol. 4(1), pages 35-60, March.
    18. Lingfang (Ivy) Li & Donald Saari, 2008. "Sen’s theorem: geometric proof, new interpretations," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 31(3), pages 393-413, October.
    19. Richiardi Matteo G, 2009. "Should (and Could) We Ban Prescriptions?," The B.E. Journal of Economic Analysis & Policy, De Gruyter, vol. 9(1), pages 1-28, January.
    20. George Djolov, 2014. "Business concentration through the eyes of the HHI," International Journal of Business and Economic Sciences Applied Research (IJBESAR), International Hellenic University (IHU), Kavala Campus, Greece (formerly Eastern Macedonia and Thrace Institute of Technology - EMaTTech), vol. 7(2), pages 105-127, September.
    21. Michel Balinski & Rida Laraki, 2022. "Majority Judgment vs. Approval Voting," Operations Research, INFORMS, vol. 70(3), pages 1296-1316, May.

    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:2202.08656. 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.