ICES: Small: Collaborative Research: New Approaches to Computationally Protecting Elections from Manipulation

选举机制广泛应用于计算环境中，包括多智能体系统中快速扩展的应用范围。20年前，针对所有合理的选举系统都可以被操纵的结果，Bartholdi，Orlin，Tovey和Trick提出通过使攻击者的任务在计算上禁止来保护选举系统免受操纵，例如，NP难他们的工作开启了一个丰富的研究路线，产生了许多这样的计算保护结果，然而，这种方法的一些弱点已经出现：（1）大部分工作假设选民有完整的，可传递的偏好，操纵者对每个选民的偏好有完美的了解。 (2)许多选举系统具有多项式时间算法以实现完美操作，因此无法在计算上受到保护。(3)即使有NP-硬度结果，这些假设所有的选民集合都是可能的，最近已经表明，当人们看到，例如，选民服从称为单峰的常见行为模型时，这些NP-硬度结果经常消失。(4)即使有NP困难的结果，它们也是最坏情况的结果，因此可能存在经常正确的启发式攻击。本项目将针对这些弱点，重建保护选举的计算方法，并更严格地描述其局限性。 更自然和现实的模型将在上面讨论的弱点方面产生强烈的后果。复杂性理论和算法都将在对上述弱点和技术的广泛调查中发展，以超越它们，保留使用复杂性理论保护选举系统免受操纵的价值。

Election mechanisms are broadly used in computational settings, including a rapidly expanding range of applications in multiagent systems. Twenty years ago, responding to results showing that all reasonable elections systems can be manipulated, Bartholdi, Orlin, Tovey, and Trick proposed protecting election systems from manipulation by making the attacker's task computationally prohibitive, e.g., NP-hard. Their work started a rich line of research, yielding many such computational protection results.However, a number of weaknesses in this approach have emerged: (1) Much of the work assumes that voters have complete, transitive preferences and that the manipulator has perfect knowledge of the preferences of each voter. (2) Many election systems have polynomial-time algorithms for perfect manipulation and so cannot be computationally protected. (3) Even when there are NP-hardness results, these assume all ensembles of voters are possible, and it has recently been shown that when one looks at, for example, voters obeying the common behavior model known as single-peakedness, these NP-hardness results often evaporate. (4) Even when there are NP-hardness results, they are worst-case results, and so it is possible that often-correct heuristic attacks exist.This project will respond to these weaknesses, rebuilding the computational approach to protecting elections and more rigorously delineating its limitations. More natural and realistic models will have strong consequences in terms of the weaknesses discussed above. Complexity theory and algorithmics will both be developed in a broad investigation of the above weaknesses and techniques to go beyond them to retain the value of using complexity theory to protect election systems against manipulation.