Le système d’orientation des lycéens a récemment changé, et comme chaque évolution sur ce sujet sensible, fait débat. Un point en particulier revient souvent : pourquoi ne pas continuer à utiliser un algorithme de Gale-Shapley tel que celui qui était implémenté 1)Plus ou moins bien… par APB ?

En première approximation, on pourrait penser comme certains qu’il s’agit d’une erreur, et cela a d’ailleurs été ma première réaction, avant de noter qu’il existe une différence critique entre APB et Parcoursup qui rend impossible l’utilisation d’une méthode similaire à celle d’APB : la réponse « Oui, si » destinée à permettre aux élèves d’intégrer une formation sous des conditions de formation complémentaire définies par la formation visée. D’autres ont fait une erreur similaire, qui a été largement retweetée :

L’erreur ici est que l’introduction du « Oui, mais » fait tomber une des hypothèses nécessaires à l’algorithme de Gale-Shapley : l’existence d’une relation d’ordre dans les préférences des élèves vis-à-vis des formations. Ne partez pas tout de suite, nous allons expliquer cela avec un exemple.

Dans APB comme dans Parcoursup, les formations peuvent classer sur dossier les candidats, possiblement en leur imposant le cas échéant une formation complémentaire dans le cas de Parcoursup. Pour le candidat, en revanche, la différence est majeure : l’éventuelle formation exigée peut changer l’ordre dans lequel il classe un établissement ! Ses préférences pourraient donc potentiellement ressembler à ceci dans les deux cas :

APB

Université d’Ankh Morpork > Université de Thélème > Université d’Eckmül

ParcourSup

Université d’Ankh Morpork > Université de Thélème > Université d’Eckmül, mais si Ankh Morpork m’impose un an de propédeutique en magie, je préfère Thélème, en revanche si c’est une semaine de formation, Ankh Morpork reste devant, sauf si Thélème exige aussi une semaine de formation. Et bien sûr, si Thélème exige un an de propédeutique en ancien français, Ankh Morpork reste devant même si elle exige une année de propédeutique, sauf si Eckmül n’exige rien. etc.

Malgré seulement trois choix et deux formations complémentaires, le classement est déjà dans la pratique quasiment impossible à cause de l’explosion combinatoire, et il le serait totalement avec un nombre d’options plus important. Outre le léger souci de devoir faire classer des milliers de situations théoriques à des centaines de milliers d’élèves, l’algorithme est quadratique en taille et en espace2)En très très résumé : la durée d’exécution et la quantité de mémoire augmentent avec le carré de la taille de l’entrée. : un algorithme quadratique sur une entrée qui présente déjà une explosion combinatoire ferait des dégâts.

Un autre détail plus subtil est que cet ordre n’existe peut-être tout simplement pas, même d’un point de vue théorique. C’est moins problématique au niveau terminale et n’est pas géré par APB, mais c’est un cas courant pour les médecins en couple au moment de leurs ECN, dont le classement détermine où et dans quelle spécialité ils peuvent faire leur internat3)C’est une problématique plus générale que les chercheurs surnomment le problème à deux corps par métaphore de physicien : arriver à faire carrière sans sacrifier un des époux alors que les postes sont extrêmement compétitifs et sans vivre à 500km de l’autre. : les préférences de deux personnes en couple peuvent dépendre les unes des autres ainsi que de leurs classements respectifs, rendant impossible, même théoriquement, l’établissement d’un classement a priori.

La solution

L’utilisation naïve d’un algorithme de Gale-Shapley étant impossible, des variantes de l’algorithme sont utilisées où les myriades de possibilités théoriques ne sont pas classées, en revanche, entre chaque itération, les préférences dans le cas qui se présente sont demandées à chaque élève.

C’est une sorte de sparse Gale-Shapley où seules les informations nécessaires à la décision sont requises. Cela a l’avantage de ne demander de classement que sur un nombre relativement restreint de cas concrets, plutôt qu’une multitude de cas théoriques mais cela a l’inconvénient de nécessiter un input entre chaque itération, qui prend un certain temps mais moins toutefois que la saisie d’un hypothétique classement de toutes les options possibles, suivie d’un calcul monstrueux4)Je n’ai pas fait de calcul même approximatif du temps que prendrait le calcul avec plusieurs milliers de vœux par élève mais je doute que la rentrée puisse se faire en septembre dans ce cas, sans même compter le temps de saisie des vœux.5)Surtout si l’algorithme est implémenté en SQL hideux avec des curseurs partout comme l’était APB..

C’est d’ailleurs une solution similaire qui est utilisée en médecine pour les ECN, ou dans les universités américaines, où les bourses offertes par les universités peuvent être un facteur de modification des préférences étant donnés les coûts de scolarité importants. La problématique est ici la même et, si on peut discuter de l’opportunité de la réforme ou des moyens donnés aux universités pour la mettre en place, l’algorithme en lui-même n’est pas en cause : celui d’APB ne peut, techniquement, pas marcher.

References   [ + ]

1. Plus ou moins bien…
2. En très très résumé : la durée d’exécution et la quantité de mémoire augmentent avec le carré de la taille de l’entrée.
3. C’est une problématique plus générale que les chercheurs surnomment le problème à deux corps par métaphore de physicien : arriver à faire carrière sans sacrifier un des époux alors que les postes sont extrêmement compétitifs et sans vivre à 500km de l’autre.
4. Je n’ai pas fait de calcul même approximatif du temps que prendrait le calcul avec plusieurs milliers de vœux par élève mais je doute que la rentrée puisse se faire en septembre dans ce cas, sans même compter le temps de saisie des vœux.
5. Surtout si l’algorithme est implémenté en SQL hideux avec des curseurs partout comme l’était APB.