Computational Social Choice and Manipulation in Approval Voting


Tuesday, April 8, 16:00
1C/150, Torre Archimede (Via Trieste 63, Padova)

Computational Social Choice and Manipulation in Approval Voting
Ulle Endriss (ILLC, University of Amsterdam)

Computational social choice is an interdisciplinary field of study at the interface of social choice theory and 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 the study of social choice mechanisms, such as voting procedures or fair division algorithms. On the other hand, computational social choice is concerned with importing concepts from social choice theory into computing. In the first part of this talk I will give a brief introduction to the field and discuss several examples.
In the second part of the talk I will present one particular direction of research, namely the fine-grained analysis of manipulation in approval voting, in more detail. By a classical result from social choice theory, all voting systems are manipulable in the sense that they all allow for situations where some voters will have an incentive
not to report their preferences sincerely when casting their ballot. I will show that for the system of approval voting, despite this general impossibility result, we can characterize several interesting classes of scenarios where it is possible to give guarantees that no voter will ever have an incentive to vote insincerely.

Rif. int. F. Rossi