April 20, 2017, 10:30 am, Nikos Karanikolas (GraphIK, IATE)
Jeudi 20 avril, 10h30, Bat 5, salle 1.156
Title: Computational aspects of social choice theory.
This talk will focus on computational problems arising from the theory of social choice and especially voting theory.
A central problem of voting theory is the computation of the winner of the elections when we have as input the preferences of the voters. In the literature there are many voting rules according to which the computation of the winner of the elections is done. Voting theory is a seminal subject in the Computational Social Choice (CSC) with applications in the society. First, we will start by defining the voting problem and some voting rules and give results about the approximation of these rules. The voting rules we primarily focus are the rules proposed by Dodgson and Young, that are designed to to find an alternative closest to being a Condorcet winner. According to the Condorcet criterion, the winner of the elections should be the one that the majority of the voters prefer in relation to every other candidate. Then, we will point out the approximability of these rules in satisfying social desirable properties. The last issue we are going to mention, is the interaction of InfoVis and CSC and specify how this approach can help people understand the structure of preferences and voting theory’s notions.