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

ICES：小型：协作研究：通过计算保护选举免遭操纵的新方法

基本信息

批准号：
1101479
负责人：
Lane Hemaspaandra
金额：
$ 12.42万
依托单位：
University of Rochester
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2011
资助国家：
美国
起止时间：
2011-08-01 至 2015-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1101479&HistoricalAwards=false
关键词：
ICES Small Collaborative Research New

项目摘要

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.

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