Robust Sparse Voting

Youssef Allouah, Rachid Guerraoui, Lê-Nguyên Hoang, Oscar Villemaud
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:991-999, 2024.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-allouah24a, title = {Robust Sparse Voting}, author = {Allouah, Youssef and Guerraoui, Rachid and Hoang, L\^{e}-Nguy\^{e}n and Villemaud, Oscar}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {991--999}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/allouah24a/allouah24a.pdf}, url = {https://proceedings.mlr.press/v238/allouah24a.html}, 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.} }
Endnote
%0 Conference Paper %T Robust Sparse Voting %A Youssef Allouah %A Rachid Guerraoui %A Lê-Nguyên Hoang %A Oscar Villemaud %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-allouah24a %I PMLR %P 991--999 %U https://proceedings.mlr.press/v238/allouah24a.html %V 238 %X 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.
APA
Allouah, Y., Guerraoui, R., Hoang, L. & Villemaud, O.. (2024). Robust Sparse Voting. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:991-999 Available from https://proceedings.mlr.press/v238/allouah24a.html.

Related Material