The Analysis Of The Preference Aggregation In Social Choice

Computational Social Choice(COMSOC)is a multidisciplinary research field that combines ideas,models,tools,and techniques from both traditional social choice theory as well as computer science.For a few years now,computer science and artificial intelligence(AI)have been taking more and more interest in social choice.The preference aggregation is one of the most popular fields in social choice,and it concerns how to combine each individual's preference in the group to get a consistent and aggregate preference.When we consider how to combine ranking preferences of a number of candidates by different voters into a single consensus ranking,the problem comes into play.The preference aggregation has many practical and applications,such as winner determinations et al.With the development of the Internet and the advent of Artificial intelligence,a wide range of applications in computer science have been found.In this thesis,we firstly consider the Kemeny ranking problem,a well-known preference aggregation rules.However,it is NP-hard.In this paper we consider Kemeny ranking problem from a computational perspective.We propose a “spanning skeleton” and discuss its relations to Kemeny rankings.Then we solve the problem by finding spanning skeletons of the underlying graphs.We also suggest two other simple greedy algorithms,similar to Copeland's algorithm and Borda's algorithm.Experimental results on different random groups of instances show that our algorithms perform well.For the second part,we give good algebraic and geometric explanations for score aggregation,and develop a spectral method for it.If we view the original scores as ‘noise data',our method can find an ‘optimal'aggregate scoring by minimizing the ‘noise information'.We also suggest a signal-to-noise indicator to evaluate the validity of the aggregation or the consistency of the agents.At last,we build a mathematical model for the peer assessment problem and regard it as an optimization problem.The model illustrate the peer assessment with geometric meaning and define the ‘distance' of two agent's evaluations.Besides,such optimal solutions are also easy to compute by using standard math softwares.