Complexity of Strategic Behavior in Collective Decision Making

本研究项目属于计算社会选择（COMSOC）领域，古典社会选择理论和经济学与理论计算机科学（特别是计算复杂性和算法）和人工智能（特别是多智能体系统）相结合。本项目提案的主要目标是研究集体决策的两个核心领域的战略行为的计算复杂性：投票和不可分割商品的分配。虽然这些是独立的主题，但有各种联系和共同特征。我们将在以下四个工作包中重点介绍我们最近在顺序投票中引入的战略在线影响（包括社会选择理论的经典模型和投票的空间模型）和得分分配模型：(1)顺序选举中的在线操纵、控制和贿赂；(2)对单峰选民进行网络操纵、网络控制和网络贿赂；(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.