发帖
雷达卡
摘要翻译：
我们证明了由两个操纵者组成的联盟计算如何操纵Borda投票规则是NP难的。这解决了操纵普通投票规则的计算复杂性中最后一个公开的问题。由于这种NP困难，我们把计算一个操作作为一个近似问题，我们试图最小化操作手的数量。基于装箱和多处理机调度的思想，我们提出了两种新的近似方法来计算Borda规则的操作。实验表明，这些方法的性能明显优于以前最著名的%现有逼近方法。我们能够在几乎所有随机产生的选举中找到最优操纵。我们的结果表明，虽然计算一个联盟对Borda规则的操纵是NP困难的，但计算复杂性可能只提供了一个很弱的障碍来防止实际操作。
---
英文标题：
《Complexity of and Algorithms for Borda Manipulation》
---
作者：
Jessica Davies, George Katsirelos, Nina Narodytska, Toby Walsh
---
最新提交年份：
2011
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
We prove that it is NP-hard for a coalition of two manipulators to compute how to manipulate the Borda voting rule. This resolves one of the last open problems in the computational complexity of manipulating common voting rules. Because of this NP-hardness, we treat computing a manipulation as an approximation problem where we try to minimize the number of manipulators. Based on ideas from bin packing and multiprocessor scheduling, we propose two new approximation methods to compute manipulations of the Borda rule. Experiments show that these methods significantly outperform the previous best known %existing approximation method. We are able to find optimal manipulations in almost all the randomly generated elections tested. Our results suggest that, whilst computing a manipulation of the Borda rule by a coalition is NP-hard, computational complexity may provide only a weak barrier against manipulation in practice.
---
PDF链接：
https://arxiv.org/pdf/1105.5667
京公网安备 11010802022788号
