AF: Small: Complexity and Computational Social Choice

计算性社会选择，尤其是其对偏好聚合/选举的关注，在人类世界中具有核心重要性。随着多智能体系统的日益流行，它变得一年比一年重要。也许计算社会选择中最活跃的研究流是对选举操纵行为的研究。在一些设置中，这样的动作可以被视为积极的，例如，作为有效的活动管理。在许多情况下，操纵性行为被视为负面行为。哪些投票制度对操纵行为最具抵抗力？哪些是最脆弱的？该地区一直在进行紧张的研究活动。然而，对最重要问题的复杂性进行分类的包容的理论框架仍然没有得到，也不清楚下一步最好的步骤是什么。这个项目确定了两个主题或缺陷。他们的研究在被称为结构复杂性理论的基本复杂性类型的工具的指导下，将有助于朝着改善计算社会选择的一致性和统一性以及更好地理解的方向前进。要研究的两个主题或缺陷是这样的。首先，该团队将研究一般函数(与研究0/1函数相反)在计算社会选择中的重要性。其次，它将努力更好地理解和更好地框定关键的操纵行动。这将涉及更广泛地探索当前模型的弱点和局限性，并将涉及提出和探索新的模型和问题，以更准确地捕捉关键算法/复杂性问题，并更好地模拟自然(人类和电子代理人)情况。在某种意义上，调查人员不会想当然地认为油田在哪里，并寻找下一步。相反，该项目将着眼于油田所在的地方是否甚至是合适的地方。这项工作将更紧密地将计算社会选择的理论研究，特别是选举，与正在建模的现实世界的同行联系起来。这两个主题突出了几个值得注意的问题，以及特别适合使用结构复杂性理论的工具、技术和世界观进行研究的问题。判断一场选举是否可以被操纵，比找出什么是成功的操纵行为更容易吗？该项目的目标之一是表明，对于计算社会选择和人工智能其他领域的重要问题，搜索和决策往往不仅在最坏的情况下复杂性内是分开的，而且在典型情况下确实是分开的。在现实世界中，选举不是同时以多种方式受到攻击吗？另一个项目目标是更好地模拟和研究多个同时发生的攻击。选举攻击通常不会在网络环境中被研究，这不是不自然的吗？在多阶段选举的分区理论模型中，分区/选区往往被允许大小不平衡，这不是不自然的吗？项目目标是更好地模拟这些设置和其他设置。这将包括开发和探索在线设置。它还将包括所谓的控制模型，能够更好地捕捉真实世界的激励例子和真实的(人类或电子代理人)环境。一个面向本科生的嵌入式项目将展示计算社会选择的挑战和美丽，以及它如何与结构复杂性理论相互作用。这将有助于保持现有STEM学生对STEM的兴趣，并将新的本科生带到STEM。总而言之，这个项目将把结构复杂性理论的工具、技术和一般敏感性集中在计算社会选择领域。通过这样做，该项目将使计算社会选择建立在更坚实的基础上，以便适当地研究关于计算成本的投票理论，并将有助于改进这一领域的问题、模型和结果。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Computational social choice, most especially its focus on preference aggregation/elections, is of central importance in the human world. With the rising prevalence of multiagent systems, it becomes of greater importance with each passing year. Perhaps the most active research stream within computational social choice is the study of manipulative actions on elections. In a few settings such actions can be viewed positively, e.g., as efficient campaign management. In many settings manipulative actions are viewed negatively. Which voting systems are most resistant to manipulative actions? Which are most vulnerable? There has been intense research activity in the area. Yet an embracing theoretical framework classifying the complexity of the most important problems still has not been obtained, and it is not clear what the best next step is. This project identifies two themes or deficits. Their study, guided by the tools of the foundational type of complexity known as structural complexity theory, will help move in the direction of improved coherence and unity in, and better understanding of, computational social choice. The two themes or deficits to be studied study are these. First, the team will study the importance of general functions (as opposed to the study of 0/1 functions) in computational social choice. Second, it will try to better understand and better frame the key manipulative actions. That will involve more generally exploring weaknesses and limitations of current models, and it will involve proposing and exploring new models and questions that more accurately capture the key algorithm/complexity questions, and that better model natural (human and electronic-agent) situations. In some sense, the investigators will not take for granted where the field is and look for a next step. Rather, the project will look at whether where the field is is even the right place to be. This work will more tightly connect the theoretical study of computational social choice, and in particular elections, to the real-world counterparts being modeled.The two themes bring highlight several remarkable issues, and ones that are particularly well suited for study using the tools, techniques, and world-view of structural complexity theory. Is it easier to tell if an election can be manipulated than it is to find what the successful manipulative action is? One of the project's goals is showing that, for important problems in computational social choice and other areas of AI, search and decision often not only separate within worst-case complexity but indeed separate in the typical case. In the real world, aren't elections attacked simultaneously in multiple ways? Another project goal is to better model and study multiple simultaneous attacks. Isn't it unnatural that election attacks are typically not studied in the online setting? Isn't it unnatural that in theoretical models of partitioning in multistage elections, the partitions/districts are often allowed to be unbalanced in size? A project goal is to better model these and other settings. This will include developing and exploring online settings. It will also include so-called control models that better capture the real-world motivating examples and the real (human or electronic-agent) settings. An embedded project for undergraduates will show the challenge and beauty of computational social choice and how it interacts with structural complexity theory. This will help keep current STEM students STEM-interested and bring new undergraduates to STEM. In summary, this project will focus the tools, techniques, and general sensibility of structural complexity theory on the area of computational social choice. By doing so, the project will put computational social choice on a firmer footing as to appropriately studying voting theory with regard to computational costs, and will contribute to improving the body of questions, models, and results in this area.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.