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