Le problème des mariages stables est au coeur de nombreuses procédures d'affectation, la plus connue en France
étant probablement ParcourSup. Il y a dans ce problème deux types de joueurs (hommes/femmes, candidat(e)s/universités,...),
chaque joueur d'un type donnant ses préférences sur les joueurs de l'autre type (les universités classent les
candidat(e)s par exemple). Le but est de trouver une affectation/un couplage vérifiant une propriété de stabilité.
L'algorithme le plus connu pour trouver une telle affectation est l'algorithme de Gale-Shapley.
Nous nous intéressons dans ce projet à un cadre dynamique, où l'ensemble de joueur peut évoluer au fil du temps (par
exemple les joueurs d'un type apparaissent au fur et à mesure). Le but est de conserver une affectation stable
au cours du temps, tout en faisant le moins de ré-affectations (changements d'affectation) possibles.
Le but du projet est:
- d'implanter des heuristiques simples (comme l'algorithme de Gale-Shapley) dans ce processus dynamique;
- d'implanter un algorithme permettant de calculer une solution optimale (par programmation linéaire);
- de faire des tests pour évaluer empiriquement les heuristiques implantées;
- de réaliser une interface conviviale.
Possibilité de faire ce projet à 2 ou 3 étudiants.