AF: Small: Complexity and Computational Social Choice

University Of Rochester, Rochester NY

Investigators

Abstract

Computational social choice, most especially its focus on preference aggregation/elections, is of central importance in the human world. With the rising prevalence of multiagent systems, it becomes of greater importance with each passing year. Perhaps the most active research stream within computational social choice is the study of manipulative actions on elections. In a few settings such actions can be viewed positively, e.g., as efficient campaign management. In many settings manipulative actions are viewed negatively. Which voting systems are most resistant to manipulative actions? Which are most vulnerable? There has been intense research activity in the area. Yet an embracing theoretical framework classifying the complexity of the most important problems still has not been obtained, and it is not clear what the best next step is. This project identifies two themes or deficits. Their study, guided by the tools of the foundational type of complexity known as structural complexity theory, will help move in the direction of improved coherence and unity in, and better understanding of, computational social choice. The two themes or deficits to be studied study are these. First, the team will study the importance of general functions (as opposed to the study of 0/1 functions) in computational social choice. Second, it will try to better understand and better frame the key manipulative actions. That will involve more generally exploring weaknesses and limitations of current models, and it will involve proposing and exploring new models and questions that more accurately capture the key algorithm/complexity questions, and that better model natural (human and electronic-agent) situations. In some sense, the investigators will not take for granted where the field is and look for a next step. Rather, the project will look at whether where the field is is even the right place to be. This work will more tightly connect the theoretical study of computational social choice, and in particular elections, to the real-world counterparts being modeled. The two themes bring highlight several remarkable issues, and ones that are particularly well suited for study using the tools, techniques, and world-view of structural complexity theory. Is it easier to tell if an election can be manipulated than it is to find what the successful manipulative action is? One of the project's goals is showing that, for important problems in computational social choice and other areas of AI, search and decision often not only separate within worst-case complexity but indeed separate in the typical case. In the real world, aren't elections attacked simultaneously in multiple ways? Another project goal is to better model and study multiple simultaneous attacks. Isn't it unnatural that election attacks are typically not studied in the online setting? Isn't it unnatural that in theoretical models of partitioning in multistage elections, the partitions/districts are often allowed to be unbalanced in size? A project goal is to better model these and other settings. This will include developing and exploring online settings. It will also include so-called control models that better capture the real-world motivating examples and the real (human or electronic-agent) settings. An embedded project for undergraduates will show the challenge and beauty of computational social choice and how it interacts with structural complexity theory. This will help keep current STEM students STEM-interested and bring new undergraduates to STEM. In summary, this project will focus the tools, techniques, and general sensibility of structural complexity theory on the area of computational social choice. By doing so, the project will put computational social choice on a firmer footing as to appropriately studying voting theory with regard to computational costs, and will contribute to improving the body of questions, models, and results in this area. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.