投票理论研究现状及其展望

社会选择理论是研究如何表达和聚合个体选择的一门学问.而社会选择理论与计算机科学的融合产生了称为计算社会选择的交叉学科,该学科成为社会计算的重要研究内容之一,在人工智能、经济和计算性理论领域引起了轰动.其一方面引入了复杂性分析和算法设计等计算机学科中常用的技术来对社会选择机制进行研究;另一方面也通过引入社会选择理论中的概念来推动计算机技术的发展,特别是在多智能体系统研究中有着成功的应用.投票理论是计算社会选择中最重要的研究主题之一.首先介绍常见的投票方法以及投票理论的形式化框架;再对投票理论中所关心的操纵问题做分析;然后介绍在组合域上的投票;最后对其他相关问题作简要介绍,并对该领域未来的发展与应用做出展望.

State-of-the-art and Future of Voting Theory

Social choice theory is concerned with the design and analysis of methods for collective decision making.Computational social choice is an interdisciplinary field of study at the interface of social choice theory and computer science and has attracted much attention from people working in artificial intelligence,economic and theoretical computer science,promoting an exchange of ideas in both directions.On the one hand,it is concerned with the application of techniques developed in computer science,such as complexity analysis or algorithm design,to study social choice mechanisms.On the other hand,computational social choice is concerned with importing concepts from social choice theory into computing,and especially social choice theory has since found its place as one of the fundamental tools for the study of multiagent systems.Voting theory is one of the most important research topics in computational social choice currently.So the main topic for this paper is voting theory,which will be investigated from all sorts of angles.Firstly,some popular voting procedures and formal framework of voting theory were introduced.Secondly,strategic manipulation and ways of circumventing strategic manipulation were discussed.Then some of the problems associated with voting in combinatorial domains were highlighted,and several approaches that have been proposed to address them were introduced.Finally,a number of additional topics in voting theory were touched briefly.Meanwhile,some future directions of voting theory were also addressed shortly.