Comment l’algorithme de Parcoursup trouve-t-il des correspondances parfaites entre étudiant.e.s et formations ? Découvrez la théorie des mariages stables derrière cette méthode de sélection et d’affectation.
L’idée des mariages stables, née en 1962, est un problème qui voit le jour grâce aux mathématiciens Gale et Shapley. Cette théorie se base sur l’idée de trouver un partenaire qui convient parfaitement et qui offre une relation stable et harmonieuse. L’algorithme de Parcoursup est lui aussi basé sur l’idée de trouver une filière universitaire qui convient parfaitement à un étudiant et qui offre des perspectives d’avenir solides. Dans les deux cas, la compatibilité est l’élément clé qui permet d’assurer la stabilité de la relation. Plus généralement, l’objectif de la théorie des mariages stables est de trouver une correspondance dite stable entre deux ensembles de taille égale.
Qu’est ce que Parcoursup ?
Parcoursup est la plate-forme de vœux actuelle pour les études supérieures. Sur cette plateforme, les bacheliers et étudiants font leur choix de parcours post bac pour leurs futures études et espèrent obtenir ce qu’ils demandent. Les universités et écoles sélectionnent quant à elles les candidats les plus adaptés à leurs formations, mais l’affectation de ces milliers de candidats se fait en partie en utilisant la théorie des mariages stables. En effet, la problématique de l’affectation des étudiants dans les formations supérieures est très similaire à celle des mariages stables. Dans ce contexte, les étudiants ont une liste de vœux (formations) qu’ils souhaitent intégrer et les formations ont une liste de critères (les notes des étudiants, compétences, remarques…) pour sélectionner les étudiants. L’objectif ici est de trouver une affectation stable, une affectation dans laquelle aucun étudiant n’a envie de changer de formation.
L’algorithme de Parcoursup, utilisé en France depuis 2018 fonctionne comme suit :
- Chaque étudiant commence par hiérarchiser ses vœux selon ses préférences.
- Chaque formation évalue les candidatures des étudiants selon leurs critères d’admission.
- Dans un premier temps, la formation offre une admission aux premiers étudiants classés..
- Si un étudiant est admis à plusieurs formations, il accepte son choix n°1 et rejette les autres.
- Si une formation a encore des places libres, elle fait une deuxième phase d’admission et propose à nouveau des places aux étudiants les mieux classés. et ainsi de suite.
- Le processus continue jusqu’à ce que tous les étudiants soient affectés à une formation et que toutes les formations soient complètes.
Ainsi, l’algorithme de Parcoursup est efficace pour trouver une affectation stable pour les étudiants tout en prenant en compte les critères d’admission des formations. Il permet également aux étudiants de faire des choix en fonction de leurs préférences en sachant que leur affectation sera stable, en opposition à l’ancienne plateforme Admissions Post Bac (APB), où un facteur aléatoire était intégré.
La théorie des mariages stables
Enoncé du problème :
« Etant donné n hommes et n femmes, où chaque personne a classé tous les membres de sexe opposé par ordre de préférence, marier les hommes et les femmes ensemble de telle sorte qu’il n’y ait pas deux personnes de sexe opposé qui préféreraient tous les deux s’avoir l’un l’autre plutôt que leurs partenaires actuels. Lorsqu’il n’y a pas de telles paires de personnes, l’ensemble des mariages est dit stable. »
En d’autres termes, les mariages stables sont une méthode de résolution de problèmes d’attribution, dans laquelle un ensemble d’individus doit être associé à un autre ensemble de personnes ou d’objets, en prenant en compte leurs préférences respectives. Dans le cadre des mariages stables, les participants ont une liste ordonnée de préférences, et l’objectif est de trouver une association stable, c’est-à-dire une association dans laquelle il n’existe pas de couple qui souhaite se séparer pour s’associer à une autre personne.
Comment résoudre ce problème ?
Pour trouver un mariage stable, on procède comme suit :
Première phase : chaque homme propose à la femme qu’il préfère le plus. Si une femme reçoit plus d’une proposition elle choisit l’homme qu’elle préfère dans la deuxième phase. Une femme ne recevant aucune proposition reste célibataire dans ce premier temps. Et on réitère jusqu’à ce que tout le monde ait un conjoint affecté.
Un exemple :
Voici un exemple présentant les préférences :
| Adam | Ben | Chris | |
|---|---|---|---|
| 1 | Dana | Dana | Françoise |
| 2 | Erica | Françoise | Erica |
| 3 | Françoise | Erica | Dana |
| Dana | Erica | Françoise | |
|---|---|---|---|
| 1 | Ben | Adam | Ben |
| 2 | Adam | Ben | Chris |
| 3 | Chris | Chris | Adam |
Dans cet exemple, Adam préfère Dana à Erica et Erica à Françoise, Ben préfère Françoise à Erica et Dana et ainsi de suite. Selon l’algorithme de Gale-Shapley, dans notre exemple, Adam et Ben proposent à Dana, et Chris propose à Françoise. Ainsi, Dana choisit celui qu’elle préfère : Ben, Françoise et Chris repartent aussi ensemble. Dans un second tour, Adam propose à Erica (Son deuxième choix). Nous avons donc obtenu trois couples : Adam-Erica, Ben-Dana, et Chris-Françoise. Et cette affectation est stable après deux tours de propositions.
Cependant, cet exemple reste simple et n’a que 3 individus de chaque sexe. Les ensembles sont donc petits et le problème est rapide à traiter. Mais dès lors que la taille des ensembles augmentent, la problématique des mariages stables devient compliquée et prend du temps, d’où la difficulté des affectations pour les admissions post bac !
Si cet article vous a plu et que vous désirez vous former dans le domaine de la data n’hésitez pas à consulter nos formations !
