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

点击翻译按钮获取中文摘要

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.