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

项目名称： 社会投票问题的参数化建模与算法研究

项目编号： No.61402054

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 郑莹

作者单位： 长沙理工大学

项目金额： 26万元

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

中文关键词： 投票；社会选择；计算复杂性；固定参数可解；NP难解

英文摘要： 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 sys

英文关键词： Voting；Social Choice；Computation Complexity；Fixed Parameter Tractable；NP-hard