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

选举机制广泛应用于计算环境，包括在多智能体系统中迅速扩展的应用范围。20年前，Bartholdi, Orlin， Tovey和Trick回应了所有合理的选举系统都可以被操纵的结果，他们提出通过使攻击者的任务在计算上禁止，例如NP-hard，来保护选举系统免受操纵。他们的工作开启了一系列丰富的研究，产生了许多这样的计算保护结果。然而，这种方法的一些弱点已经显现出来：(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.