RECORD
Robust Voting Rules from Algorithmic Robust Statistics
Data Structures and Algorithms · Submitted 13 Dec 2021
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Our main result is an efficiently computable estimator that achieves nearly optimal robustness guarantees.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Maximum likelihood estimation furnishes powerful insights into voting theory, and the design of voting rules. However the MLE can usually be badly corrupted by a single outlying sample. This means that a single voter or a group of colluding voters can vote strategically and drastically affect the outcome. Motivated by recent progress in algorithmic robust statistics, we revisit the fundamental problem of estimating the central ranking in a Mallows model, but ask for an estimator that is provably robust, unlike the MLE. Our main result is an efficiently computable estimator that achieves nearly optimal robustness guarantees. In particular the robustness guarantees are dimension-independent in the sense that our overall accuracy does not depend on the number of alternatives being ranked. As an immediate consequence, we show that while the landmark Gibbard-Satterthwaite theorem tells us a strong impossiblity result about designing strategy-proof voting rules, there are quantitatively strong ways to protect against large coalitions if we assume that the remaining voters voters are honest and their preferences are sampled from a Mallows model. Our work also makes technical contributions to algorithmic robust statistics by designing new spectral filtering techniques that can exploit the intricate combinatorial dependencies in the Mallows model.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Maximum likelihood estimation furnishes powerful insights into voting theory, and the design of voting rules. | background 1.00 | 0.07 | 0.02 | asserted 0.99 |
| s1 | However the MLE can usually be badly corrupted by a single outlying sample. | background 0.81 | 0.10 | 0.02 | asserted 0.72 |
| s2 | This means that a single voter or a group of colluding voters can vote strategically and drastically affect the outcome. | background 0.68 | 0.09 | 0.02 | asserted 0.94 |
| s3 | Motivated by recent progress in algorithmic robust statistics, we revisit the fundamental problem of estimating the central ranking in a Mallows model, but ask for an estimator that is provably robust, unlike the MLE. | contribution 0.79 | 0.38 | 0.06 | asserted 0.81 |
| s4 | Our main result is an efficiently computable estimator that achieves nearly optimal robustness guarantees. | result 0.69 | 0.96 | 0.95 | asserted 1.00 |
| s5 | In particular the robustness guarantees are dimension-independent in the sense that our overall accuracy does not depend on the number of alternatives being ranked. | result 0.81 | 0.91 | 0.09 | asserted 1.00 |
| s6 | As an immediate consequence, we show that while the landmark Gibbard-Satterthwaite theorem tells us a strong impossiblity result about designing strategy-proof voting rules, there are quantitatively strong ways to protect against large coalitions if we assume that the remaining voters voters are honest and their preferences are sampled from a Mallows model. | interpretation 0.77 | 0.87 | 0.19 | asserted 0.99 |
| s7 | Our work also makes technical contributions to algorithmic robust statistics by designing new spectral filtering techniques that can exploit the intricate combinatorial dependencies in the Mallows model. | contribution 0.98 | 0.95 | 0.03 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Maximum likelihood estimation furnishes powerful insights into voting theory, and the design of voting rules. However the MLE can usually be badly corrupted by a single outlying sample. This means that a single voter or a group of colluding voters can vote strategically and drastically affect the outcome. Motivated by recent progress in algorithmic robust statistics, we revisit the fundamental problem of estimating the central ranking in a Mallows model, but ask for an estimator that is provably robust, unlike the MLE. Our main result is an efficiently computable estimator that achieves nearly optimal robustness guarantees. In particular the robustness guarantees are dimension-independent in the sense that our overall accuracy does not depend on the number of alternatives being ranked. As an immediate consequence, we show that while the landmark Gibbard-Satterthwaite theorem tells us a strong impossiblity result about designing strategy-proof voting rules, there are quantitatively strong ways to protect against large coalitions if we assume that the remaining voters voters are honest and their preferences are sampled from a Mallows model. Our work also makes technical contributions to algorithmic robust statistics by designing new spectral filtering techniques that can exploit the intricate combinatorial dependencies in the Mallows model.
Human review
How the literature uses it
1 arXiv paper cite this in 1 sentence
What it cites · 2 sentences without a confident label
Uses the method or tool of 1 paper
-
Then we iteratively refine the estimate $π$ by using stronger robust mean estimation algorithms [ref] that give us accuracy guarantees that depend on how well we know the covariance of the underlying distribution.
Outlier Robust Mean Estimation with Subgaussian Rates via Stability · Spectral Filtering with Combinatorial Dependencies · 0.98
Cites as background 5 papers
-
Our work builds on a long line of progress in high-dimensional algorithmic robust statistics, which includes algorithms for robustly estimating a single Gaussian [ref] , robust linear regression [ref] and mixture models [ref] .
Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination · Related Work · 0.81
-
Many recent works have focused on characterizing and computing the MLE in various ranking models [ref] and investigating its other statistical properties [ref] .
Random Utility Theory for Social Choice · Background · 0.98
-
Many recent works have focused on characterizing and computing the MLE in various ranking models [ref] and investigating its other statistical properties [ref] .
Preference Elicitation For General Random Utility Models · Background · 0.98
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.