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 aspects 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 le système comporte des aspects temporels, 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 vingtaine 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: algorithmique dans un environnement dynamique
Nous nous intéresserons dans cette deuxième partie à des modèles visant à prendre en compte l'aspect temporel ou évolutif de certains problèmes. Nous introduirons tout d'abord les graphes temporels, modélisant par exemple les réseaux de transport, en étudiant les spécificités induites par l'aspect temporel sur la résolution de problèmes classiques. Nous étudierons ensuite l'algorithmique on-line, où l'algorithme découvre au fur et à mesure les données du problème qu'il doit résoudre. Nous étendrons ensuite l'algorithmique on-line aux algorithmes dits ``learning augmented'', qui disposent de prédictions sur le futur. Notions clés: graphes temporels, algorithmique en-ligne, analyse de compétitivité, algorithmes avec prédictions
Documents
- Algorithm Design, J. Kleinberg, E. Tardos, 2005
- Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani, 2007
- Computational Aspects of Cooperative Game Theory, G. Chalkiadakis, E. Elkind, M. Wooldridge
- Online Algorithms, Rahul Vaze, Cambridge University Press & Assessment, 2023
[Credit image: Image(s) by Chris Jensen and Greg Riestenberg, as part of the free image from the Evolutionary Games Infographic Project gallery]