Voting Rules As Error-Correcting Codes

Authors

  • Ariel Procaccia Carnegie Mellon University
  • Nisarg Shah Carnegie Mellon University
  • Yair Zick Carnegie Mellon University

DOI:

https://doi.org/10.1609/aaai.v29i1.9292

Keywords:

Voting rules, Ground truth, Adversarial noise

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.

Downloads

Published

2015-02-16

How to Cite

Procaccia, A., Shah, N., & Zick, Y. (2015). Voting Rules As Error-Correcting Codes. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9292

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms