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

算法决策理论：利用复杂性保护集体决策程序免受操纵攻击

• 批准号: 248483686
• 负责人: Professor Dr. Gábor Erdelyi
• 金额: --
• 依托单位: Lehrstuhl für Entscheidungs- und Organisationstheorie
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2013
• 资助国家: 德国
• 起止时间: 2012-12-31 至 2014-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/248483686?language=en
• 关键词: Algorithmic; Decision; Theory; Using; Complexity

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.

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