社会投票问题的参数化建模与算法研究

Voting is an easy, feasible and popular social choice method. But it initiates an argument that whether voting can truly reflect the aspirations of the voters and the winner is really a successor as the wishes. Research on the complexity of the voting system has attracted much attentions in recent years. Many problems in voting systems have been proved NP-hard, however, the knowledge about the complexity of some voting systems is few, and there exist many faults in the complexity and accuracy of these known research results. This project mainly focuses on the study of the formulation and the complexity of the voting problems, the design of the parameterized algorithms of the voting problems, the analysis of the strategic attacks on the voting systems and the extension application of the voting systems. Firstly, we will analyze the parameterized complexity of the concrete voting problems and propose efficient algorithms combining with the structural properties and the parameterized computation technologies. Then we will study the patterns and the complexity of strategic attacks on these voting systems, thus prove the infeasibility of the attacks. Finally the procedures of kernelization and the parameterized algorithms will be realized algorithmically. The statistics analysis for the rationality of the voting systems will also be done to push the development of the field of computable social choice.

投票是一种简单可行且深入人心的社会选择方式，然而投票能否真正反映投票人的意愿，当选者是否真的众望所归，引发了很多争议，对投票系统的复杂性研究也成为近些年的热点。投票系统中很多问题都已经证明了是NP难解的，但人们对投票系统复杂性的认识还处在一个初级阶段，而且目前很多投票系统研究结果在复杂度或精确度方面存在着种种缺陷。本项目主要从投票问题的建模和复杂性分析、投票问题的参数算法设计、投票系统的策略攻击分析以及投票系统的扩展应用等方面进行研究。首先从投票系统中具体问题出发，分析这些问题的参数复杂性，并根据问题的结构特性结合参数计算技术提出高效可行的求解方法。然后分析具体投票系统的策略攻击模式以及复杂性，从而证明这些破坏行为的不可行。并最终实现对投票系统的核心化过程和参数算法实现，更好地对投票系统的合理性进行统计分析，从而推动可计算的社会选择领域的发展。

人们在做出一个共同的决定时最好的办法就是投票。然而，即便我们有好的投票规则，仍然无法保证能得到期盼的结果。其中一个原因就是会有人为了改变投票结果而对整个投票过程进行策略攻击。人们不禁会问：是否存在一种投票规则，即在这个投票规则下即便有人进行策略攻击也不能改变最终结果？这个问题促生了一个新的研究领域的出现——可计算的社会选择。. 本课题主要研究了可计算的社会选择领域中的四个问题：投票问题的建模和复杂性分析、投票问题的参数算法设计、投票系统的策略攻击分析以及投票系统的扩展应用。研究了投票问题基于d-赞成规则，最大最小规则，孔多塞规则，Copeland规则等不同的投票规则下的计算复杂性，并根据问题的结构特性结合参数计算技术提出了可行的求解方法。重点研究了投票问题在三种策略攻击模式下的计算复杂性，已经证明了基于最大最小规则，Copeland规则和孔多塞规则的投票问题在贿赂攻击下是NP难解的，基于Borda规则的投票问题在操纵攻击下是NP难解的，以及基于孔多塞规则，Copeland规则和最大最小规则的投票问题在控制攻击下是NP难解的，说明这些策略攻击行为是不可行的。项目资助发表SCI、EI和核心论文5篇，待发表2篇。培养硕士生3名（包括留学生），其中1名已经取得硕士学位，1名取得博士学位，1名在读。