Les approches algorithmiques classiques en optimisation font généralement des hypothèses fortes sur le système étudié: problème clairement défini, fonction objectif précise, données parfaitement connues,... Or, ces hypothèses sont dans de nombreux cas pratiques irréalistes. Par exemple, lors d'applications en ligne il est fréquent que les données soient susceptibles d'évoluer au cours du temps. Aussi, plusieurs personnes sont souvent partie prenante dans le système étudié, ce qui rend l'objectif et la dynamique même du système plus complexes.
Dans cette UE, nous présenterons des modèles, concepts et méthodes récemment développés pour prendre en compte les trois aspects majeurs suivants:
- le fait que le problème concerne plusieurs agents aux intérêts potentiellement contradictoires, modélisé dans le cadre de la théorie des jeux algorithmique;
- le fait que les ressources de calcul sont nécessairement limités, avec de nouvelles approches pour la résolution de problèmes NP-difficiles;
- le fait que le système comporte des aspects dynamiques, avec des données susceptibles d'évoluer ou connues au fur et à mesure.
Première partie: théorie des jeux algorithmique
Dans cette première partie, nous présenterons les principaux modèles et approches utilisés pour la modélisation de systèmes composés d'un ensemble d'agents indépendants et égoïstes. Cette problématique est au coeur de la théorie des jeux algorithmique, discipline née il y a une dizaine d'années suite à l'essor d'internet. Les notions abordées seront en particulier illustrées sur des problèmes liés aux systèmes informatiques et aux réseaux.
Notions clés: équilibres de Nash, prix de l'anarchie, enchères, marchés, mécanismes d'incitation, jeux coopératifs
Deuxième partie: Résolution de problèmes difficiles
Dans la deuxième partie de cette UE, nous nous focaliserons sur le développement de méthodes exactes ou approchées avec garantie de performance pour la résolution de problèmes NP-difficiles.
Notions clés: complexité paramétrée, algorithmes approchés
Troisième partie: Algorithmique dans un environnement dynamique
Nous nous intéresserons dans cette dernière partie à différents modèles visant à prendre en compte l'aspect intrinsèquement dynamique de certains problèmes. Notions clés: algorithmique en-ligne, analyse de compétitivité, réoptimisation
Documents
- Algorithm Design, J. Kleinberg, E. Tardos, 2005
- Algorithmes d'approximation, V. Vazirani, 2006
- Invitation to Fixed-Parameter Algorithms, R. Niedermeier, 2006
- Networks, Crowds, and Markets: Reasoning About a Highly Connected World, D. Easley, J. Kleinberg, 2010
- Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani, 2007
- Computational Aspects of Cooperative Game Theory, G. Chalkiadakis, E. Elkind, M. Wooldridge
[Credit image: Image(s) by Chris Jensen and Greg Riestenberg, as part of the free image from the Evolutionary Games Infographic Project gallery]