Complexity of Strategic Behavior in Collective Decision Making

这个研究项目福尔斯属于计算社会选择（COMSOC）领域，经典的社会选择理论和经济学满足理论计算机科学（特别是，计算复杂性和算法）和人工智能（特别是，多智能体系统）。本项目提案的主要目标是研究集体决策的两个核心领域中战略行为的计算复杂性：投票和不可分割商品的分配。虽然这些是单独的主题，但有各种连接链接和联合功能。我们将重点介绍我们最近推出的战略在线影响力在顺序投票（在社会选择理论的经典模型和投票的空间模型中）和以下四个工作包中的评分分配模型：（1）连续选举中的在线操纵、控制和贿赂;（2）单峰值选民的在线操纵、在线控制和在线贿赂;（3）连续选举中的在线操纵、在线控制和在线贿赂。（3）不可分割商品的评分分配具有防策略性等性质：（4）不可分割商品分配具有公平性和社会福利最优化性。在每个工作包中，我们将考虑对某种战略行为或其他行为（例如，公平）财产。特别是，我们试图探索以何种方式和在何种程度上计算复杂性可以用来防止不受欢迎的战略行为，如操纵攻击。 我们的复杂性分析将采用经典复杂性，参数化复杂性和近似理论的工具，此外，我们将进行实证研究，利用概率方法，并将研究基本的投票和分配机制的公理属性。

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.