Voting rules as error-correcting codes

详细信息    查看全文

• 作者：Ariel D. Procaccia ^{arielpro@cs.cmu.edu" class="auth_mail" title="E-mail the corresponding author} ; Nisarg Shah ; ^{nkshah@cs.cmu.edu" class="auth_mail" title="E-mail the corresponding author} ; Yair Zick ^{yairzick@cmu.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Social choice ; Voting ; Ground truth ; Adversarial noise ; Error-correcting codes
• 刊名：Artificial Intelligence
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：231
• 期：Complete
• 页码：1-16
• 全文大小：649 K

文摘

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.