Mariage stable avec des données qui évoluent dans le temps

Ce stage s'intéresse à un problème d'optimisation dans le cadre multiagent dans lequel chaque agent a sa propre liste de préférence et l'objectif est de déterminer une solution prenant en compte ces préférences. Dans ce cadre, nous proposons d'étudier une variante du problème de mariage stable avec capacités dans laquelle certaines données évoluent au cours du temps. Plus précisément, on se donne un ensemble d'établissements, chacun avec sa capacité d’accueil, et un ensemble d'élèves-candidats. Chaque établissement ordonne les étudiants et chaque élève a une liste de préférence des établissements. Il est assez facile de calculer une affectation stable pour ce problème. Néanmoins, après cette première affectation des candidats peuvent disparaître, pour différentes raisons : non obtention du bac, etc... Une des questions que l'on pourrait se poser dans ce contexte est la suivante : est-il toujours possible de calculer une nouvelle affectation stable où aucun candidat parmi ceux qui restent ne détériore son affectation par rapport à sa liste de préférence ? D'autres variantes pourraient également être envisagées comme par exemple le cas où il y a un changement au niveau de capacité d'accueil des établissements. Dans ce cas, on pourrait s'intéresser à retrouver une solution stable minimisant la détérioration maximale ou moyenne. Le stagiaire éventuel commencera son travail par une recherche bibliographique sur le problème de mariage stable avec des données qui évoluent avec le temps avant d'étudier les aspects algorithmiques et de complexité liés à la variante proposée.

Encadrant: 
E. Bampis et B. Escoffier
Référent Universitaire: 
n/a
Attribué: 
No
Année: 
2 019

User login