Algorithmic Decision Theory: Using Complexity to Protect Collective Decision-Making Procedures from Manipulative Attacks

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

This project concerns Computational Social Choice, a young, interdisciplinary field emerging at the interface of social choice theory and computer science, which is also related to the fundamental theory explaining the structure of consensus problems. It brings together researchers from many different disciplines in order to improve decision-making procedures in large-scale computer settings, combinatorial structures, and in settings based on partial and/or uncertain information. How independent agents reach collective decisions in the presence of large datasets and partial or uncertain information, is a very complex process, yet its solution is of key importance in many real life applications, like Politics, Image Processing, Auctions, Recommender Systems, Social Networks, and Multi-Agent Systems, just to name a few. The purpose of this project is to analyze different decision-making procedures from a complexity-theoretic and empirical perspective. The project will broadly cover the study of manipulative actions, such as bribery, manipulation (in its narrow term-of-art sense in the field), and control in different types of elections and judgment aggregation procedures. Our key objective is to break the in Computational Social Choice prevailing practice of operating on the basis of purely theoretical assumptions, and rise to the challenge of finding and using assumptions of considerable practical relevance instead. Our research will focus on the following four core issues:1. Bribery, control, and manipulation in elections, in settings with domain restrictions or uncertainty (such as nearly single-peaked elections, k-peaked elections, voting rule uncertainty),2. parameterized and average-case complexity of decision-making problems,3. computational aspects of judgment aggregation procedures, and4. empirical analyses of concepts introduced under the previous three points.