Computational social choice
Enseignant responsable :
Volume horaire : 24Description du contenu de l'enseignement :
The aim of this course is to give an overview of the problems, techniques and applications of computational social choice, a multidisciplinary topic at the crossing point of computer science (especially artificial intelligence, operations research, theoretical computer science, multi-agent systems, computational logic, web science) and economics. The course consists of the analysis of problems arising from the aggregation of preferences of a group of agents from a computational perspective. 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. The course will focus on normative aspects, computational aspects, and real-world applications (including some case studies). Program: 1. Introduction to social choice and computational social choice. 2. Preference aggregation, Arrow's theorem and how to escape it. 3. Voting rules: informational basis and normative aspects. 4. Voting rules : computation. Voting on combinatorial domains. 5. Strategic issues: strategyproofness, Gibbard and Satterthwaite's theorem, computational resistance to manipulation, other forms of strategic behaviour. 6. Multiwinner elections. Public decision making and participatory budgeting. 7. Communication issues in voting: voting with incomplete preferences, elicitation protocols, communication complexity, low-communication social choice. 8. Fair division. 9. Matching under preferences. 10. Specific applications and case studies (varying every year): rent division, kidney exchange, school assignment, group recommendation systems …
Pré-requis recommandés :
Prerequisite-free. Basics of discrete mathematics (especially graph theory) and algorithmics is a plus.
Pré-requis obligatoires :
none
Compétence à acquérir :
N/S
Mode de contrôle des connaissances :
Written exam by default.
Bibliographie, lectures recommandées
References: * Handbook of Computational Social Choice (F. Brandt, V. Conitzer, U. Endriss, J. Lang, A. Procaccia, eds.), Cambridge University Press, 2016. Available for free online. * Trends in Computational Social Choice (U. Endriss, ed), 2017. Available for free online.