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.
翻译:最大概率估计提供了对投票理论和投票规则设计的有力洞察力。 但是, MLE通常会被单一的外围样本严重腐蚀。 这意味着一个单一的选民或一组串通的选民能够从战略角度投票并极大地影响选举结果。 受最近算法稳健统计进展的驱动,我们重新审视了估算Mallows模式中心排名的基本问题,但要求有一个与MLE不同的、稳健的估算器。 我们的主要结果是一个高效的可折算的估测器,能够实现几乎最佳的稳健保证。 特别是, 强健的保证是维度的维度独立, 因为它意味着我们的总体准确性并不取决于正在排位的替代物的数量。 作为直接的结果, 我们显示,尽管标志性的Gibbard-Satterwaite the the orem告诉我们在设计防战略的投票规则方面存在着强烈的失常结果, 但如果我们假设剩下的选民是诚实的, 并且他们的偏好被选自Mallows模型的样本, 就能在数量上保护。 我们的工作还在技术上为精确的稳健的精确度统计提供了技术。