# Robust Voting Rules from Algorithmic Robust Statistics

arXiv: https://arxiv.org/abs/2112.06380 · HTML: https://mlsanity.com/paper/2112.06380/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 57 references that are in the map.
- First posted on arXiv 13 Dec 2021.

## Builds on (most cited first, 21 of 21)

- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Sever: A Robust Meta-Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1803.02815/) (2018)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Outlier Robust Mean Estimation with Subgaussian Rates via Stability](https://mlsanity.com/paper/2007.15618/) (2020)
- [Robust Linear Regression: Optimal Rates in Polynomial Time](https://mlsanity.com/paper/2007.01394/) (2020)
- [Settling the Robust Learnability of Mixtures of Gaussians](https://mlsanity.com/paper/2011.03622/) (2020)
- [Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination](https://mlsanity.com/paper/2010.04157/) (2020)
- [Learning Mixtures of Plackett-Luce Models](https://mlsanity.com/paper/1603.07323/) (2016)
- [Robust Learning of Mixtures of Gaussians](https://mlsanity.com/paper/2007.05912/) (2020)
- [Efficiently Learning Mixtures of Mallows Models](https://mlsanity.com/paper/1808.05731/) (2018)
- [Optimal Learning of Mallows Block Model](https://mlsanity.com/paper/1906.01009/) (2019)
- [Learning GMMs with Nearly Optimal Robustness Guarantees](https://mlsanity.com/paper/2104.09665/) (2021)
- [Efficiently Learning Structured Distributions from Untrusted Batches](https://mlsanity.com/paper/1911.02035/) (2019)
- [Learning Mixtures of Permutations: Groups of Pairwise Comparisons and Combinatorial Method of Moments](https://mlsanity.com/paper/2009.06784/) (2020)
- [Preference Elicitation For General Random Utility Models](https://mlsanity.com/paper/1309.6864/) (2013)
- [Robust Learning of Optimal Auctions](https://mlsanity.com/paper/2107.06259/) (2021)
- [Learning sparse mixtures of rankings from noisy information](https://mlsanity.com/paper/1811.01216/) (2018)

## Built on by (most cited first, 1 of 1)

- [Perturbation Sensitivity of Maximum-Likelihood Pairwise Ranking in Computational Decision Systems](https://mlsanity.com/paper/2604.17805/) (2026)

## Abstract (arXiv)

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.