ML Anthology

Voting Rules as Error-Correcting Codes

Ariel D. Procaccia, Nisarg Shah, Yair Zick
AAAI 2015 pp. 1000-1006
doi:10.1609/AAAI.V29I1.9292 /aaai/2015/procaccia2015aaai-voting/

Abstract

We present the first model of optimal voting under adversarial noise. From this viewpoint, voting rules are seen as error-correcting codes: their goal is to correct errors in the input rankings and recover a ranking that is close to the ground truth. We derive worst-case bounds on the relation between the average accuracy of the input votes, and the accuracy of the output ranking. Empirical results from real data show that our approach produces significantly more accurate rankings than alternative approaches.

PDF AAAI Semantic Scholar

Cite

Text

Procaccia et al. "Voting Rules as Error-Correcting Codes." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9292

Markdown

[Procaccia et al. "Voting Rules as Error-Correcting Codes." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/procaccia2015aaai-voting/) doi:10.1609/AAAI.V29I1.9292

BibTeX

@inproceedings{procaccia2015aaai-voting,
  title     = {{Voting Rules as Error-Correcting Codes}},
  author    = {Procaccia, Ariel D. and Shah, Nisarg and Zick, Yair},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2015},
  pages     = {1000-1006},
  doi       = {10.1609/AAAI.V29I1.9292},
  url       = {https://mlanthology.org/aaai/2015/procaccia2015aaai-voting/}
}