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-HARD）来保护选举系统免受操纵。他们的工作开始了丰富的研究，产生了许多这样的计算保护结果。但是，这种方法中的许多弱点已经出现：（1）许多作品假设选民具有完整的传递性偏好，并且操纵者对每个选民的偏好具有完美的知识。（2）许多选举系统具有用于完美操纵的多项式时间算法，因此不能在计算上受到保护。（3）即使有NP固定性结果，这些都假定所有选民的合奏都是可能的，最近已经证明，当人们观察的选民遵守称为单峰的共同行为模型时，这些NP硬度的结果经常蒸发。（4）即使有NP硬度结果，它们也是最坏的结果，因此可能存在经常正确的启发攻击。该项目将响应这些弱点，重建计算方法以保护选举并更严格地划定其局限性。就上述弱点而言，更自然和现实的模型将产生强烈的后果。复杂性理论和算法都将在对上述弱点和技术的广泛研究中开发，以超越它们，以保留使用复杂性理论保护选举系统免受操纵的价值。