Cette année, plus de 900.000 lycéens ont formulé un vœu sur Parcoursup, la plateforme de vœux pour les études supérieures. Ce chiffre inclut la majorité des futurs bacheliers mais aussi les élèves en réorientation, qui sont en légère hausse par rapport à l’an dernier (+4,9%). L’intégration des lycéens dans l’enseignement supérieur est un moment clé du calendrier académique : période charnière dans la vie d’un jeune adulte, il s’agit également d’un des choix les plus importants dans une vie.
Historiquement, au moment d’exprimer leur envie d’intégrer un certain établissement, les lycéens devaient s’informer des procédures propres à chaque établissement : les dates n’étaient pas les mêmes, les documents à fournir encore moins. Bien sûr, tous les dossiers étaient sous forme papier, à retourner aux universités ou autres classes préparatoires par courrier ou en mains propres.
Au début des années 2000, une révolution est créée pour les classes préparatoires : les élèves souhaitant intégrer une classe préparatoire pouvaient alors s’inscrire sur une plate-forme commune, en renseignant les éléments de leur dossier de manière informatique, et leur affectation était décidée par un algorithme selon l’ordre de leurs vœux et de leurs résultats. Rapidement, certaines académies souhaitent utiliser cette plateforme pour toutes leurs autres filières du supérieur. Ce système a été créé par Bernard Koehret, ancien professeur de l’Institut polytechnique de Toulouse, à la demande du ministère de l’éducation nationale – il s’agit de l’ancêtre d’APB – Admission Post-Bac. En 2009, APB est étendu à tout le territoire national et pour l’immense majorité des formations du paysage de l’enseignement supérieur français. Ce système, qui est déjà passé par de multiples itérations, est donc relativement récent. Cependant, les fondations d’APB et de Parcoursup sont beaucoup plus anciennes.
Le problème des mariages stables et l’algorithme de Gale-Shapley
S’il a été utilisé pour APB en 2009, l’algorithme qui se cache derrière ne date en réalité pas d’hier. En effet, il s’agit de l’algorithme de Gale-Shapley, présenté par les mathématiciens David Gale et Lloyd Shapley en 1962. Cet algorithme a été conçu pour répondre au “problème des mariages stables”.
Dans ce problème, un groupe égal d’hommes et de femmes doivent être réunis en couples homme-femme dits “stables, c’est-à-dire qu’aucun mariage ne va se briser pour en reformer un plus optimal.
Pour répondre à ce problème, l’algorithme reprend l’adage, “L’homme propose, la femme dispose”. Chaque homme propose à plusieurs femmes de son choix de l’épouser. Les femmes choisissent d’épouser l’homme qui leur convient le plus parmi eux. Les hommes non choisis redemandent la main d’autres femmes jusqu’à ce qu’il ne reste plus personne de libre.
Sur ce schéma, les lettres a, b et c représentent les hommes ; A, B et C, les femmes. Entre parenthèses, sont écrits leurs ordres de préférence des personnes du sexe opposé.
Dans la première rotation de l’algorithme ; B reçoit une proposition de mariage de c et b ; tandis que A reçoit une proposition de a. B préfère c à b, donc choisit d’épouser c. A accepte la main de a. L’homme b est toujours célibataire et demande la main de C, restée libre : ils se marient. Les mariages ainsi obtenus sont stables : par exemple, A ne pourra pas quitter a pour b, car b lui préfère sa partenaire B.
Dans l’algorithme d’APB, les candidats sont les “femmes”, ce qui pose un certain problème : dans notre exemple précédent, si les femmes proposaient en premier, A serait mariée à b, son partenaire préféré, dès le premier tour, tandis que dans le scénario précédent, elle épouse l’homme qu’elle aime le moins. De plus, l’algorithme de Gale-Shapley n’est pas optimal lorsque tous les participants ne sont pas classés. Or, dans le contexte de l’orientation à l’université, tous les candidats sont égaux, car il n’y a pas toujours de sélectivité liée à leurs résultats. L’université est donc obligée de procéder à des tirages au sort pour faire une “proposition de mariage”.
Parcoursup : une amélioration de l’algorithme ?
A l’époque d’APB, le résultat final d’affectation n’était transparent : l’étudiant était automatiquement accepté au vœu qu’il avait classé au plus haut rang, et n’était pas informé de son classement dans les autres formations.
Aujourd’hui, Parcoursup repose toujours sur un algorithme de Gale-Shapley, mais sa principale différence repose en la manière pour les candidats d’exprimer leurs préférences.Dans le système de Parcoursup, l’élève ne classe pas ses vœux, mais il est régulièrement appelé par la plateforme à choisir la formation qu’il préfère parmi celles qui l’ont accepté, avec la possibilité de “mettre en attente” son choix, en attendant de remonter le classement d’une formation.
Dans les faits, il s’agit de matérialiser les choix opérés par les femmes dans l’algorithme de Gale-Shapley. Les tours de l’algorithme deviennent transparents pour les candidats, mais deviennent fatalement plus longs : les délais entre chaque tour se comptent en jours voire en semaines. La nouvelle plateforme permet désormais au candidat de changer d’avis dans le classement de ses vœux tout au long du processus d’affectation, et évite les stratégies de classement que supposait la plateforme APB : “si je mets cette prépa cotée en 1ervoeu, je ne serai plus prioritaire pour la prépa de ma région si jamais elle me refuse“.
D’autres applications de l’algorithme de Gale-Shapley ?
À emlyon business school, comme dans de nombreuses écoles de commerce, les élèves de première année souhaitent rejoindre des associations étudiantes. Historiquement, l’association Plug’n’Play est chargée de récolter les vœux des étudiants sur une plateforme interne, ainsi que les classements de chaque association de tous les candidats ayant passé leurs entretiens. Les résultats étaient récupérés informatiquement, mais traitées manuellement sur plusieurs jours. Depuis 2020, l’association Plug’n’play a développé un algorithme qui reprend les principes de l’algorithme de Gale-Shapley : l’intérêt de l’élève est toujours placé en premier, plutôt que celui d’une association.
Chaque élève de l’école qui le souhaite s’inscrit à un entretien avec une ou plusieurs associations. Le processus et les critères diffèrent pour chaque association, mais chacune répartit les élèves en deux listes : une liste principale non classée, et une liste secondaire classée. La liste principale correspond au nombre d’élèves pouvant intégrer l’association (en général, entre 20 et 40 personnes) et la liste secondaire est limitée. Parallèlement, chaque élève émet des vœux d’association, ce nombre varie entre 4 et 6 chaque année. Ces vœux sont classés par ordre de préférence.
🗳️ Comment l’algorithme traite-t-il les vœux des étudiants ?
Lorsque les vœux et les classements sont compilés, l’algorithme commence à tourner et procède par des étapes très simples qu’il va appliquer, élève par élève. L’algorithme vérifie le premier vœu du premier élève ; à ce moment-là, plusieurs options sont possibles :
- Il est dans la liste principale de l’association : il l’intègre immédiatement et libère les listes principales et secondaires de ses autres vœux.
- Il est dans la liste secondaire : il est mis en attente dans l’algorithme jusqu’à ce qu’il remonte dans la liste principale. S’il ne remonte jamais dans la liste principale, l’algorithme vérifie son vœu suivant.
- Il n’est pas classé par l’association : l’algorithme vérifie son vœu suivant.
Ces opérations sont répétées jusqu’à ce que tous les vœux de tous les élèves soient traités. À la fin du traitement, il arrive que des élèves n’aient pas d’associations ; mais à l’inverse, certaines associations ont encore de la place : un second tour est alors organisé, et à l’issue de celui-ci, l’immense majorité des élèves est répartie dans une association, et les mandats associatifs sont remplis.
L’algorithme est fait de telle sorte que l’élève sera toujours dans l’association qu’il préfère, parmi celles qui l’ont classé. Il est donc dans son intérêt de classer les associations selon ses préférences personnelles, sans stratégie. De plus, les vœux sont strictement privés et les associations n’ont pas le droit de connaître ni de demander à un élève son ordre de préférence.
Les résultats de cooptation, les vœux et les classements sont strictement confidentiels : seule une poignée de personnes les connaissent à chaque étape et sont tenues au secret. Les résultats finaux sont transmis par Plug’n’Play au conseil de corporation, puis individuellement à chaque association avant de les diffuser publiquement aux élèves de l’école ; généralement dans le plus grand amphithéâtre de l’école sur écran géant. Restrictions sanitaires obligent, la diffusion se fera sur Facebook cette année.
Que ce soit pour s’orienter vers des études supérieures, ou pour intégrer une association étudiante à l’emlyon, les algorithmes ont donc une place très importante. Sans eux, classer des dizaines, des centaines voire des milliers de candidats prendrait des mois. Cependant, ils sont rarement parfaits, et doivent être constamment ajustés pour garantir une répartition optimale.
Par Natalia Wojnowski
En dehors de l’orientation scolaire et des campagnes associatives, les algorithmes sont utilisés dans quasiment tous les systèmes informatiques existants. Parmi les domaines dans lequel ils font l’actualité, on peut notamment citer l’intelligence artificielle. Pour en savoir plus sur le fonctionnement et les biais des algorithmes d’IA, n’hésitez pas à consulter l’article qui y est consacré.
Cet article a été publié pour la première fois le 19 avril 2021 sur Hypertext, le blog de l’association Plug’n’Play. N’hésitez pas à y faire un tour pour trouver d’autres articles sur le numérique !
