选举系统的参数复杂性研究

Voting systems play an important role in the modern information society and can find various applications such as the coordination of multi-agent systems. There are many voting protocols whose pro and cons have been studied for centuries in such diverse fields as philosophy, mathematics, political science, and economy. With the omnipresence of the Internet and modern communication tools, applications such as auctions, ratings, and recommendations have become an everyday business. The computational complexity of voting systems has been established as one of the key criteria for evaluating voting systems. In the last decade, many computational problems related to voting systems have been proven to be computationally hard based on the classical complexity theory and accordingly, algorithms have been proposed as efficient solving approaches for voting problems with respect to new applications. This project aims to conduct a systematic investigation the interaction between structural parameters of voting systems and the computational complexity of voting problems, by examining the parameterized complexity of voting systems instead of their classical complexity. Based on this, frameworks for designing parameterized algorithms for voting problems shall be derived and the classification of voting systems, which is now mainly based their classical complexity behavior, can be further refined, giving a more comprehensive, theoretical basis for designing the voting systems suitable for concrete applications. This project also intends to derive from the study of the parameterized complexity of voting systems, new techniques for designing parameterized/kernelization algorithms or proving parameterized complexity, enriching the arsenal of parameterized complexity theory.

选举系统在现代信息社会中起着重要的作用，广泛用于多智能体系统的协调。对选举系统的研究持续了几个世纪，涉及哲学、数学、政治及经济等领域。随着英特网普及和现代通讯设备的出现，拍卖、评价、推荐等多种涉及选举的应用已成为日常生活的重要组成部分，各种选举系统的计算复杂度也成为了评价它们的实用性的关键因素。近十年来，传统计算复杂性理论被用于选举系统的重新分类，涌现了许多解决新时代背景下的选举问题的算法。本项目旨在通过对典型的选举问题的参数复杂性的分析，系统性地归纳出各种选举系统的结构参数对所涉及问题的计算复杂性的影响，从而细化已有的基于传统复杂性理论的分类，提出针对选举问题的参数算法设计框架，给创造适用于新兴应用的选举系统提供更全面的理论基础。本项目另一主要目标在于从选举系统的参数复杂性的研究中，提炼出新的参数和核心化算法的设计技术和新的参数复杂性的证明工具，从而推动参数复杂性理论的发展。

在本基金的支持下，课题组对选举系统的参数复杂性进行了系统的研究，在计算社会选择学领域取得了一系列成果，填补了多个选举系统目前的研究热点问题的计算复杂性研究的空白，回答了多个前期研究提出的开放性问题，总结了若干可用于自动证明一系列选举问题的传统和参数复杂性的工具和技术。其一为委员会选举问题，对近期提出的三种新的委员会选举模型进行了全面的参数复杂性分析，涉及此领域采用的所有结构参数，并且将这三种委员会选举模型的分析拓展到Trichotomous选票，基本完成了委员会选举的各种变形的计算复杂性分析。其二为多轮次选举问题，探讨了多轮次选举的交换贿选问题的参数计算复杂性，为证明多轮次选举比单轮次选举有更强的抵抗性这一猜测提供了首个系统性的理论证据；并且提出了一个全新的多轮次选举的Possible/Necessary获胜者问题的模型，对证明此模型在常用的多轮次选举规则下的计算复杂性提出了通用的规约框架，取得了一系列NP难的结果。其三为Borda控制问题，Borda是一个有名的选举规则，完善了Borda传统控制问题的计算复杂性，解决了一个前人提出的开放性问题，并对通用的结构参数对其计算复杂性的影响给出了完整的分类。其四是偏好模型下的匹配问题，常规匹配问题在多模态偏好输入的情况下有多个无法解决的计算问题，针对这些问题，提出了全新的适应多模态偏好的匹配模型，并证明了这些模型在计算复杂性方面的优势，另外，还针对传统匹配模型的若干扩展在偏好输入下的参数复杂性进行了系统的研究，有效地扩展了已有的传统复杂性结果。.此项目的研究不仅丰富和发展了选举及其相关问题的算法和计算复杂性的分析，同时推动了计算社会选择学领域的参数算法和参数复杂性的应用，拓展了与德国柏林工大Rolf Niedermeier教授领导的算法教研组的合作，并进一步巩固了研究组目前在选举问题的参数复杂性领域的地位。