Complexity of Strategic Behavior in Collective Decision Making

集体决策中战略行为的复杂性

• 批准号: 438204498
• 负责人: Professor Dr. Jörg-Matthias Rothe
• 金额: --
• 依托单位: Arbeitsgruppe Computational Complexity and Cryptology
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/438204498?language=en
• 关键词: Complexity; Strategic; Behavior; Collective; Decision

This research project falls into the area of computational social choice (COMSOC) where classical social choice theory and economics meet theoretical computer science (in particular, computational complexity and algorithmics) and artifical intelligence (in particular, multiagent systems). The main objective of this project proposal is to study thecomputational complexity of strategic behavior in two central areas of collective decision making: voting and the allocation of indivisible goods. While these are separate topics, there are various connecting links and joint features. We will focus on our recently introduced strategic online influence in sequential voting (both in the classical models of social choice theory and in the spatial models of voting) and scoring allocation models in the following four work packages: (1) Online manipulation, control, and bribery in sequential elections; (2) online manipulation, online control, and online bribery over single-peaked electorates; (3) strategy-proofness and other properties in scoring-basedallocation of indivisible goods; and (4) fairness properties and social welfare optimization in the allocation of indivisible goods. In each of these work packages, we will consider natural, important problems modeling a certain kind of strategic behavior or some other(e.g., fairness) property. In particular, we seek to explore in which way and to what extentcomputational complexity can be used as protection against undesired strategic behavior such as manipulation attacks. Our complexity analysis will employ tools from classical complexity, parameterized complexity, and the theory of approximations, and inaddition we will perform empirical studies, make use of probabilistic approaches, and will study the axiomatic properties of the underlying voting and allocation mechanisms.

本研究项目属于计算社会选择(COMSOC)领域，经典的社会选择理论和经济学与理论计算机科学(特别是计算复杂性和算法)和人工智能(特别是多智能体系统)相结合。本项目提案的主要目标是研究集体决策的两个中心领域中战略行为的计算复杂性：投票和不可分割的商品分配。虽然这些是单独的主题，但有各种连接链接和连接特征。我们将集中于我们最近在顺序投票(包括经典的社会选择理论模型和投票的空间模型)和得分分配模型中引入的战略性在线影响，这些模型包括以下四个工作包：(1)顺序选举中的在线操纵、控制和贿赂；(2)对单峰选民的在线操纵、在线控制和在线贿赂；(3)基于得分的无策略性和其他性质；以及(4)不可分割商品分配中的公平性和社会福利优化。在每个工作包中，我们都将考虑对某种战略行为或其他一些(例如，公平)属性进行建模的自然、重要的问题。特别是，我们试图探索以何种方式以及在多大程度上可以使用计算复杂性来保护自己免受不受欢迎的战略行为的影响，例如操纵攻击。我们的复杂性分析将使用经典复杂性、参数复杂性和近似理论的工具，此外，我们将进行实证研究，利用概率方法，并将研究潜在投票和分配机制的公理性质。