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

这个项目涉及计算社会选择，这是一个年轻的跨学科领域，出现在社会选择理论和计算机科学的界面上，它也与解释共识问题结构的基本理论有关。它汇集了来自许多不同学科的研究人员，以改进大规模计算机设置、组合结构和基于部分和/或不确定信息的设置中的决策程序。独立代理如何在大数据集和部分或不确定信息存在的情况下达成集体决策，是一个非常复杂的过程，但它的解决方案在许多现实生活应用中至关重要，如政治、图像处理、拍卖、推荐系统、社交网络和多代理系统，仅举几例。本课题的目的是从复杂性理论和实证的角度分析不同的决策程序。该项目将广泛地涵盖对操纵行为的研究，例如贿赂、操纵（在该领域狭义的艺术意义上）以及对不同类型的选举和判决汇总程序的控制。我们的主要目标是打破计算社会选择中基于纯理论假设的主流实践，并迎接挑战，寻找和使用具有相当实际意义的假设。我们的研究将集中在以下四个核心问题上：1。选举中的贿赂、控制和操纵，在有领域限制或不确定性的情况下（如近单峰选举、k峰选举、投票规则不确定性）；决策问题的参数化和平均情况复杂性，3。3 .判断聚合程序的计算方面；对前三点介绍的概念进行实证分析。

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.