A Survey of Computational Social Choice: Theory and Applications

PhD Qualifying Examination


Title: "A Survey of Computational Social Choice: Theory and Applications"

by

Mr. Ning DING


Abstract:

Social choice theory is a branch of mathematical social science discussing 
the property of all possible election systems. It emerges when scientist 
study the mathematical model of political institutions. Any society faces 
the question of making compromise between people who have interest 
conflicts. And people develop political systems to solve these problems. 
For example, in modern democratic societies, residents cast votes to elect 
political leaders and legislature, who are given the power to arbitrate 
the compromise in the society. Although the interest of social choice 
theory comes from these problems, once developed, this discipline applies 
not only to the limited field. One of the areas it attracts attention from 
is computer science, especially multi-agent systems domain. In this survey 
we'll introduce some preliminary insights social choice theory and 
computer science draws from each other.

As social choice theory considers the properties of all possible society, 
we could imagine not much could be said to subscribe it. Actually most of 
the fundamental results are impossibility theorem, saying what we can't 
get, rather than the properties of what we can get, from a society. Among 
the many results in this field, Arrow's impossibility theorem is probably 
the most famous one. This theorem states that there's no social choice 
function which satisfies 3 intuitive propositions, namely, Pareto 
Optimality, non-dictatorship and Independent of Irrelevant 
Alternatives(IIA).After discovery of this impossibility theorem, many 
other impossibility theorems were found out, giving us a deeper 
understanding of the dilemma in elections. In the Section 3 we'll have a 
brief introduction of these impossibility theorems.

These complicated impossibility theorems are often big stones standing in 
front of any novice willing to study social choice. The theorems 
themselves are difficult to understand, let alone the even more subtle 
proof. To make a more readable proof and understanding, Tang and Lin 
introduced how to use a computer to prove these theorems. Section 4 will 
include this and some other usage of computer to help solve problems in 
social choice theory.

Social choice theory applies not only to human society, but also to 
situations when multiple agents need to make common decisions. Since 
multiagent system was introduced to artificial intelligence community, 
social choice theory has drawn a lot of attention from computer 
scientists. In section 5, there will be some discussion about the 
application of choice rules to multiagent systems.

In section 6, we'll introduce some practical applications of social choice 
theory. After that, some conclusion will be made.


Date:                   Wednesday, 20 April 2011

Time:                   1:45pm - 3:45pm

Venue:                  Room 1504
                         lifts 25/26

Committee Members:	Prof. Fangzhen Lin (Supervisor)
                         Prof. Siu-Wing Cheng (Chairperson)
  			Dr. Ke Yi
  			Prof. Nevin Zhang


**** ALL are Welcome ****