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.

[Edit] : Ce qui suit est un ajout fait le 25/05 suite à des éléments complémentaires découverts grâce à @nholzschuch, que je remercie.

Une contrainte supplémentaire

L’algorithme a été conçu par Claire Mathieu et Hugo Gimbert du CNRS (je vous laisse aller voir les CVs pour les détails et autres affiliations mais il me parait compliqué de leur donner des cours d’algorithmique sur Twitter…) et Hugo Gimbert, en particulier, nous donne quelques informations sur le cahier des charges.

Algorithmes-de-parcoursup is an open-source project which led to the production of two algorithms and their Java implementation. This piece of software is used by the french government in order to deal with College admission in France. The Gale-Shapley algorithm is the standard method in practice for large matching markets, but must be adapted to the constraints of each situation. Together with Claire Matthieu, we designed a college admission procedure which respect legal regulations and governemental constraints in a setting with the following features:

  • Lack of trust in the platform: students wants to keep control rather than leaving it to a computer: with sometimes more than 50 wishes, the students prefer to express their preferences once they know their options, rather than ranking all these possible options in advance.
  • Transparency: the final result must not be given as a black box but come with an “explanation” that helps rebuild trust.
  • Quotas: schools have a legal obligation to respect certain quotas of student types. The types and quotas vary from school to school.
  • Housing: schools provide housing to some of their students, allocated according to need. Some students can only afford to attend if housing is provided. The offers must thus take into account both the students’ academic ranking and their ranking according to need.
  • Simplicity: to be socially acceptable, the designed algorithm shall be elementary and simple.
  • Determinacy: the use of a random device is forbidden.

La plupart des éléments sont connus et présents dans ce post, dont le grand nombre d’options potentielles créé par le oui, si mais un autre détail m’avait échappé : les critiques récurrentes sur le  côté obscur d’un algorithme qui décidait in fine des études supérieures des lycéens qui n’avaient d’autre choix que de classer et d’attendre que l’ordinateur décide pour eux. Une des contraintes était donc de donner, tout simplement, le dernier mot sur leur avenir aux lycéens, en leur présentant les options possibles. On peut certainement défendre un choix par l’algorithme au nom de la rapidité, ou par l’élève au nom de la transparence mais il me paraît compliqué de demander les deux à la fois6)[Edit] : Le choix final par l’élève était visiblement une exigence de la CNIL. Ca contraint totalement l’algorithme..

Un autre élément sur lequel on m’a posé des questions est le système de queues multiples (boursier, hors académie, internat) : il s’explique par des obligations légales et des critères sociaux dans l’attribution des places d’internat.

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.
6. [Edit] : Le choix final par l’élève était visiblement une exigence de la CNIL. Ca contraint totalement l’algorithme.