Algorithmic Decision Theory and Computational Social Choice

Objectives : Many individual or collective decision making contexts involve computationally hard problems, either because of the combinatorial structure of the choice space, or because of the 'computational resistance" to strategic behaviour. This course aims at introducing the main classes of problems and algorithmic techniques in decision theory and social choice, and to study a few classes of applications.

Contents:

• preference representation and optimization on combinatorial domains (CP-nets and extensions, GAI-nets, valued constraint satisfaction problems; applications)
•  algorithms for sequential decision making: planning, fully or partially observable Markov decision processes, influence diagrams
•  algorithmic aspects of voting: computationally hard voting rrules, voting on combinatorial domains, computational resistance to strategic behaviour, communication and incomplete preferences
•  resource allocation: combinatorial auctions (elicitation lannguages, winner determination algorithms), fair division.

Bibliography:

• Concepts et méthodes pour l'aide à la décision (D. Bouyssou, D. Dubois, M. Pirlot, H. Prade, editeurs),  Hermès - Lavoisier
• Handbook of Constraint Programming (T. Walsh, F. Rossi, editeurs), Elsevier
• Handbook of Social Choice and Welfare (K. Arrow, A.  Sen, K. Suzumura  éditeurs), Elsevier.