RI:HCC:Small:Preference Aggregation: Bypassing Worst-Case Protections

RI:HCC:Small:偏好聚合：绕过最坏情况保护

• 批准号: 0915792
• 负责人: Lane Hemaspaandra
• 金额: $ 33.07万
• 依托单位: University of Rochester
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0915792&HistoricalAwards=false
• 关键词: RI; HCC; Small; Preference; Aggregation

Elections are a broad model for collective decision-making. Since around 1990, worst-case hardness notions (most particularly, NP-hardness) have been widely studied as a method for protecting election systems from manipulation, bribery, and control. Such protective worst-case results have by now been obtained for many problems and many election systems.The goal of this project is to study the ways that these protective results can be bypassed for the election manipulation, bribery, and control problems. This project will seek to transform the way security of elections is viewed: to make vividly clear by actual proofs and algorithms that worst-case protections can on important real-word systems and situations be shredded, and thus that bypass attacks are a true threat. The project will do this through exploring the extent of worst-case protections and by finding the extent to which those protections can be bypassed, via studying restrictions on and assumptions about models, domains, and distributions.This project involves a wide range of broader impacts, including information dissemination, bringing together local researchers interested in computational social choice, training of students, and service to the community. In addition, the topic itself is of broad relevance to society. Elections are of great importance both in human settings and in a rapidly expanding range of electronic settings, and indeed the study of elections is of active interest in computer science, economics, political science, operations research, and mathematics. The core research of this project seeks to better understand when the protection offered by worst-case hardness results about election systems can be bypassed, and thus is relevant within a broad range of contexts in which elections are used for collective decision-making: from spam filtering to critical human elections to sports tournaments to multiagent systems. Showing which important, known-worst-case-safe election systems are vulnerable to bypass attacks serves the interest of the citizenry, since system designers can then avoid those systems, and in the long run more broadly secure systems can be developed.

选举是集体决策的广泛模式。 自 1990 年左右以来，最坏情况硬度概念（尤其是 NP 硬度）作为保护选举系统免受操纵、贿赂和控制的方法得到了广泛研究。 迄今为止，许多问题和许多选举系统都已经获得了这种保护性的最坏情况结果。该项目的目标是研究如何在选举操纵、贿赂和控制问题中绕过这些保护性结果。 该项目将寻求改变看待选举安全的方式：通过实际证明和算法生动地表明，重要的真实系统和情况下的最坏情况保护可以被粉碎，因此旁路攻击是真正的威胁。 该项目将通过研究对模型、领域和分布的限制和假设，探索最坏情况保护的程度，并找到可以绕过这些保护的程度，从而实现这一目标。该项目涉及广泛的广泛影响，包括信息传播，汇集对计算社会选择、学生培训和社区服务感兴趣的当地研究人员。 此外，该主题本身与社会具有广泛的相关性。 选举在人类环境和迅速扩大的电子环境中都非常重要，事实上，选举研究在计算机科学、经济学、政治学、运筹学和数学中都具有积极的意义。 该项目的核心研究旨在更好地了解选举系统最坏情况硬度结果所提供的保护何时可以被绕过，因此在选举用于集体决策的广泛背景下具有相关性：免受垃圾邮件过滤到关键的人类选举、体育比赛到多智能体系统。 显示哪些重要的、已知最坏情况安全的选举系统容易受到旁路攻击符合公民的利益，因为系统设计者可以避免这些系统，并且从长远来看可以开发更广泛的安全系统。