投票问题在限定偏好集上的参数复杂性研究

Parameterized complexity is one of the most efficient approaches to deal with hard problems. It has been successfully used in a broad range of areas such as algorithmic graph theory, bioinformatics, data encoding, computer network etc. In recent years, parameterized complexity has been used in several emerging areas such as computational social choice. Voting is one of the most important topics in computational social choice. In particular, voting is recognized as a common method for preference aggregation and has found applications in many areas such as economics, multiagent systems, machine learning, computer networks, distributive systems, big data etc. Investigating the complexity of voting problems in restricted domains has been one of the hot topics in computational social choice recently. Though that much effort has been made, there are still many voting problems whose parameterized complexity is unknown. This project aims to systematically and extensively study the related problems. We shall classify voting problems into fixed-parameter tractable and fixed-parameter intractable classes. For the former problems, we shall further develop FPT-algorithms and kernelization algorithms. The parameters will be the ones imposed in the restricted domains under consideration. Our study will advance the development of the aforementioned areas.

参数计算理论是处理工程难解问题的有效方法之一，并被成功应用到很多领域，比如图论算法、生物信息学、数据编码、计算机网络等。近几年，参数计算理论也被应用到一些新兴领域比如计算社会选举。投票理论主要研究如何有效和公平地将多个不同偏好综合成一个统一结果，是解决集体决策问题的有效方式，也是目前计算社会选举的核心研究内容。投票理论最初是经济学的一个重要分支。随着人工智能的发展，投票系统近年来被应用到很多领域，比如多智能体(multiagent systems)、机器学习、计算机网络、分布式系统、大数据等。研究投票问题在限定偏好集的参数复杂性是近几年计算社会选举的研究热点。然而，目前还有大量问题的参数复杂性没有得到研究。本课题将对相关问题进行深入研究，首先将问题分为固定参数可解和固定参数不可解。对于固定参数可解问题，设计参数算法和核心化算法。本课题的研究将对以上相关领域的发展起到重要推动作用。

偏好聚合（投票模型）旨在将给定集合和不同偏好公平合理地聚合为一个统一结果，在推荐系统、多智能体协作、启发式算法设计、群体决策等领域有着重要的应用价值。随着大数据和网络时代的发展，很多应用中需要聚合的偏好规模呈指数级增长，这对各类偏好聚合方法在实际中的应用提出了新的挑战。此外，社交网络和虚拟平台也为各种恶意篡改输入偏好的性为提供了可能，这于偏好聚合方法的公平性相违背。基于此背景，项目对偏好聚合相关的几类问题从参数计算角度进行了深入研究。具体研究内容大致分为一下几类：（1）研究了二分偏好聚合的若干聚合函数的赢家计算问题的参数复杂性。（2）研究了候选者关联关系的二分偏好聚类模型和相关问题的参数复杂性。（3）研究了带有冗余偏好的二分偏好聚类函数的赢家计算问题的复杂性。（4）首次提出和研究了距离限定的线性偏好聚合函数的投票贿赂问题的复杂性。(5)解决了若干限性偏好聚合函数偏好控制问题复杂性的开放性问题。我们具体研究的二分偏好聚合函数包括approval voting (AV), satisfaction approval voting (SAV), net-SAV, proportional approval voting (PAV), Chamberlin-Courant Approval Voting (CCAV)和Maximin Approval voting (MAV), consent规则, consensues/liberal-start-respecting 规则等，研究的线性偏好聚合函数包括Borda, Condorcet, Maximin, Copeland, r-approval, plurality/veto-with runoff等。对于以上涉及到的问题，我们用复杂性工具和算法设计分析方法将问题分为NP-难解问题和多项式时间可解问题。对于前者，我们继续研究其参数复杂性。我们研究的参数包括候选者数目，给定的偏好数目，赢家数，非赢家数，以及引导图的若干结构参数等。对于每类问题我们将得到的结果汇总到复杂性分类表以便研究人员可以在最快的时间内获得相关问题最新的研究状况。在IJCAI, AAMAS我们的成果发表在CCF推荐的A,B类会议和期刊如发表了12篇高质量学术论文。我们的结果对以上提到的各类偏好聚合函数在实际中的应用有着重要的理论指导。