COURS 1 (Octobre – 2019, Prof invité)
Titre : Automated Reasoning for Social Choice Theory
Intervenants: Ulle Endriss
Volume horaire : 9h, 3 fois 3h, sur deux Mardi
Dates: Mardi 1 Octobre: 6h. Matin 9h-12h. Après Midi 14h-17h (B510)
Mardi 8 Octobre: 3h Après midi: 14h-17h. (C108)
Description: One of the most exciting development in computational social
choice in recent years has been the use of tools for automated reasoning
developed in AI, notably SAT solvers, to support researchers in social choice
theory in their quest of getting a deeper understanding of the axiomatic
foundations of collective decision making. This short course, based on the
course on computational social choice I teach at the ILLC in Amsterdam
(http://www.illc.uva.nl/~ulle/teaching/comsoc/2019/) will enable participants to
employ these tools in their own research. Lectures will cover both introductory
material on the axiomatic method in social choice theory and a hands-on session
on how to use a modern SAT solver to (partly) automate the proof of the
seminal Gibbard-Satterthwaite Theorem. Besides attending lectures, participants
will complete a programming assignment and present a recent paper from the
relevant literature. The course is equally suitable for those carrying out research
in (computational) social choice themselves and those who are new to the field.
The only prerequisites for being able to fully benefit from the course are some
basic programming skills in Python and familiarity with classical propositional
COURS 2 (Octobre 2019, Prof Invité)
Titre: Judgement Aggregation and Strategy-Proof Social Choice
Intervenants: Clemens Puppe
Volume horaire : 6h, Mercredi et Jeudi de14h à17h.
Dates: Mercredi 9 Octobre: 3h Après midi, 14h-17h. (P521)
Jeudi 10 Octobre, 3h Après midi, 14h-17h (Salle C bis)
Description: We review the basic results in the recent field of judgement
aggregation and explore some deep connections with the theory of strategyproof
social choice on restricted domains. At the heart of the course is the
characterization of all monotonic, issue-wise aggregation rules in terms of the
Intersection Property (Nehring and Puppe, Journal of Economic Theory 2007).
COURS 3 (Octobre 2019, Prof invité)
Titre: Byzantine Fault Tolerant Distributed Computing
Intervenants : Aris Pagourtzis
Volume horaire : 3h Mardi.
Dates : Mardi 15 Octobre, 14h-17h. (Salle C)
Description: Byzantine Fault Tolerance (BFT) is a fundamental issue in
distributed computing, which has recently received renewed attention due to the
advent of the blockchain technology and its potential application in a vast
number of distributed systems. We will study BFT issues in both main
paradigms of distributed computing, namely message passing and mobile
agents. Regarding the former, we will talk about the reliable broadcast problem,
also known as Byzantine Generals. For the latter, we will focus on exploration
and rendezvous by mobile agents in the presence of malicious agents. We will
present earlier and recent results for several problems and settings in these two
exciting areas of research.
COURS 4 (Octobre, Novembre 2019, Prof invité)
Title: Introduction to Computational Social Choice
Intervenants: Piotr Skowron
Volume horaire : 12h, les jeudi.
Dates : Jeudi, 14h-17h, 31 October (C108), 7th November (C127), 14 November, 21 November
The objective Computational social choice is a field at the intersection of
economics (specifically, the social choice theory), mathematics and computer
science. It studies situations where a group of agents needs to reach a collective
decision, but the agents might have conflicting preferences with respect to the
decision to be made. In particular, it analyses tools that facilitate such decisionmaking,
aims at comparing the quality and suitability of such tools, and studies
computational problems that arise in the process of making a decision. A
particular example of such tools are voting rules---functions that take agents'
preferences as input (the preferences can be represented in various ways) and
return an outcome. The voting rules can be used to select a single winner among
a group of candidates, to provide a ranking of candidates (e.g., contestants in a
competition), to select a bunch of projects that a city council should fund
(participatory budgeting), etc.
In this course we will cover selected topics from computational social choice,
specifically focussing on the following question: "How computer science and
discrete mathematics can help in understanding and comparing voting rules?".
During the course, we will define and explain a number of voting rules, we will
introduce the classic axiomatic approach that consists in formulating certain
desired properties that voting rules should satisfy and examining which voting
rules satisfy them (we will explain how this axiomatic approach can be
enhanced by using computers, specifically SAT solvers), we will explain the
utilitarian approach to comparing voting rules (in particular, showing how the
idea of approximation algorithms can be used to better understand the suitability
and to assess the quality of decision rules), we will analyse the computational
complexity of finding outcomes of certain voting rules and related
The course will be based on the following resources:
 Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D.
Procaccia: Handbook of Computational Social Choice. Cambridge University
 Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon:
Multiwinner voting: A new challenge for social choice theory. In Ulle Endriss,
ed., Trends in Computational Social Choice. AI Access Foundation 2017.
 Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, Piotr
Skowron: Approximating optimal social choice under metric preferences.
Artificial Intelligence 264: 27-51, 2018.
COURS 5 (Janvier, Février 2020)
Titre: Introduction du algorithmic game theory
Intervenant: Laurent Gourves
Volume horaire : 18h, les jeudi.
Dates : Jeudi, 14h-17h, 9 Janvier, 16 Janvier, 23 Janvier, 30 Janvier, 6 février,
27 Février (Salle A 407)
The objective: Introduction to (mostly strategic) games and discrete
optimization problems. Solution concepts: definition, algorithmic construction,
quality (price of anarchy and stability). Games of potential/congestion games.
Auctions, stable marriage.
-Algorithmic game theory, Tardos Roughgarden, Vazirani (ed), Cambridge
university press, 2007.
-Networks, Crowd, and Markets: reasoning about a highly connected world.
Easley & Kleinberg, Cambridge university press, 2010.
-20 Lectures on Algorithmic game theory, Roughgarden, Cambridge university
COURS 6 (Mars, Avril 2020)
Titre: Polynomial and Super-polynomial Approximation of NP-hard problems
Intervenant: Vangelis Paschos
Volume horaire : 18h, les jeudi.
Dates : Jeudi, 14h-17h, 5 Mars, 12 Mars, 19 Mars, 26 Mars, 2 Avril, 23 Avril (Salle A 407)
The objective: A graduate course for the students of LAMSADE/CEREMADE.
Polynomial approximation of NP-hard problems in one of the first Theoretical
Computer Science and Complexity Theory research topics born two years after
the first NP-completeness proof of SAT. The objective of of polynomial
approximation is to design polynomial algorithms for NP-hard problems
computing solutions the values of which is, in worst case as close to optimal
solution as possible for any instance of the problem studied. The measure of
such closeness is the so-called approximation ratio. Super-polynomial
approximation is a recent research program mainly developed in LAMSADE in
order to remedy to the negative results proved in the framework of polynomial
approximation for the quasi-totality of the paradigmatic combinatorial
optimization problems. Here the objective is to develop exponential algorithms
guaranteeing approximation ratios impossible in polynomial time, these
algorithms having an exponential worst case complexity much than the best
known exact complexity of the optimal algorithms for problems tackled.
M. R. Garey, D. S. Johnson, Computers and intractability. A guide to the theory
of NP-completeness, W. H. Freeman 1979
C. H. Papadimitriou, K. Steiglitz, Combinatorial optimization: algorithms and
complexity, Prentice Halln, 1981
V. Th. Paschos, Complexité et approximation polynomiale Hermès, 2004
COURS 7 (Juin 2020, Prof invité)
Title: Parameterized Complexity or Kernelization (a subarea in parameterized
Intervenants: Venkatesh Raman
Volume horaire : 12h, les Mardi et Jeudi.
Dates : Mardi 16 Juin et Jeudi 18 Juin de 14h-17h
Mardi 23 Juin et Jeudi 25 Juin: 14h-17h (Salle A 407)
The objective I hope to cover algorithmic techniques and lower bounds. Exact
topic can be based on the interest of the participants.