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. For instance, social welfare orderings originally developed to analyse the quality of resource allocations in human society are equally well applicable to problems in multi-agent systems or network design. The course will focus on normative aspects, computational aspects, and real-world applications (including some case studies). Program: 1. Introduction to social choice. 2. Computing hard voting rules and preference aggregation functions. Application to aggregating web page rankings. 3. Strategic issues: manipulation, control, game-theoretic analyses of voting. Short introduction to algorithmic mechanism design. 4. Preference aggregation on combinatorial domains. 5. Communication issues in voting: voting with incomplete preferences, elicitation protocols, communication complexity, low-communication mechanisms. 6. Fair division of indivisible goods. 7. Cake cutting algorithms 8. Matching under preferences 9. Coalition formation. 10. Specific applications and case studies (varying every year): rent division, kidney exchange, school assignment, group recommendation systems…
Bibliographie, lectures recommandées
Handbook of Computational Social Choice (F. Brandt, V. Conitzer, U. Endriss, J. Lang, A. Procaccia, eds.), Cambridge University Press, 2016. Algorithmics of Matching Under Preferences (D. Manlove), World Scientific, 2013.