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.

本文证明了一个有两方联盟的问题计算如何操纵 Borda 投票规则是 NP 难的，并提出了基于箱装和多处理器调度的两种新的近似方法来计算 Borda 规则的操纵。实验表明，这些方法明显优于以前已知的近似方法，并能在几乎所有测试的随机生成的选举中找到最佳的操纵结果。结果表明，虽然 Borda 规则的联盟操纵计算是 NP-hard 的，但计算复杂度在实践中可能只提供弱障碍。