Dates des Séminaires ED d’Informatiques 2019-2020

Jeudi 10h-12h, 
Jeudi 10 Octobre 2019 : Manel Ayadi + Alexandre ARAUJO Salle A304
Jeudi 7 Novembre 2019 : Eric Benamou + Raphael Pinot Salle P507
Jeudi 19 Décembre 2019 : Alexis Duburcq+ Guillaume Prévost Salle P517
Jeudi 16 Janvier 2020 : Amin Farvardin + () Salle P517
Jeudi 13 Février 2020 : Raja Trabelsi + Felippe Garrido Salle P517
Jeudi 12 Mars 2020 : Hajer Ben Fekih + Ons Nefla Salle P517
Jeudi 09 Avril 2020 : Pedro Guillermo Lopez+ Beatrice Napolitano Salle P517
Jeudi 14 Mai 2020 : Geovani Rizk+ Beji Celine Salle P517
Jeudi 18 Juin 2020 : Axel Faure Beaulieu + () Salle P517

 

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

(boolean) logic.

 

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

computational problems.

The course will be based on the following resources:

[1] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D.

Procaccia: Handbook of Computational Social Choice. Cambridge University

Press 2016.

[2] 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.

[3] 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.

References:

-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

press, 2016

 

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.

References

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

complexity)

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.