AF: Small: Complexity and Computational Social Choice

AF：小：复杂性和计算社会选择

• 批准号: 2006496
• 负责人: Lane Hemaspaandra
• 金额: $ 36.59万
• 依托单位: University of Rochester
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006496&HistoricalAwards=false
• 关键词: AF; Small; Complexity; Computational; Social

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.

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

项目成果

Existence versus exploitation: the opacity of backdoors and backbones

存在与剥削：后门和主干的不透明性

• DOI: 10.1007/s13748-021-00234-6
• 发表时间: 2021
• 期刊: Progress in Artificial Intelligence
• 影响因子: 4.2
• 作者: Hemaspaandra, Lane A.;Narváez, David E.
• 通讯作者: Narváez, David E.

Defying Gravity and Gadget Numerosity: The Complexity of the Hanano Puzzle

挑战重力和小工具的数量：Hanano 谜题的复杂性

• 发表时间: 2023
• 期刊: Proceedings of the 25th International Conference on Descriptional Complexity of Formal Systems
• 作者: Chavrimootoo, Michael C.

SIGACT News Complexity Theory Column 115: Juris Hartmanis and Two Golden Rules

SIGACT 新闻复杂性理论专栏 115：Juris Hartmanis 和两条黄金法则

• DOI: 10.1145/3577971.3577977
• 发表时间: 2022
• 期刊: ACM SIGACT News
• 作者: Hemaspaandra, Lane A.

Closure and nonclosure properties of the classes of compressible and rankable sets

可压缩集和可排序集类的闭包和非闭包性质

• DOI: 10.1016/j.jcss.2021.02.004
• 发表时间: 2021
• 期刊: Journal of Computer and System Sciences
• 影响因子: 1.1
• 作者: Abascal, Jackson;Hemaspaandra, Lane A.;Maimon, Shir;Rubery, Daniel
• 通讯作者: Rubery, Daniel

Separating and Collapsing Electoral Control Types

• DOI: 10.48550/arxiv.2207.00710
• 发表时间: 2022-07
• 作者: Benjamin Carleton;Michael C. Chavrimootoo;L. Hemaspaandra;David E. Narv'aez;Conor Taliancich;Henry B. Welles