Parcoursup n'est pas APB

Hier soir, le commentaire de Guillaume Haeringer sur mon précédent billet [1] m'a surpris, puis a créé une sorte d'étincelle. Je me suis souvenue des propos de la ministre le 12 décembre dernier, à propos d'humain au cœur de la procédure [2]. J'en ai conclu que ces 810000 humains au coeur de Parcoursup risquaient de générer un sacré bordel... Les discussions avec Lucie sur les réseaux sociaux ont fini par éclairer ma lanterne. Je vous livre ici ce que j'ai compris. N'hésitez pas à corriger, à commenter si possible en bas de ce blog, afin que tous en profitent. A la fin de l'article, les diverses corrections sont listées. 

Guillaume Haeringer a dit…

On peut difficilement comparer l’algorithme d’APB avec celui de parcoursup. Les algorithmes de parcoursup ne servent qu’à déterminer les choix des formations. On a à faire ici à un problème de many-to-one matching, il faut donc rajouter une fonction de choix du côté des formations. APB faisait la même chose, mais en plus APB calculait une affection, ce que les algorithmes de parcoursup ne font pas. Avec parcoursup on a un mécanisme de matching décentralisé, on ne peut donc pas garantir la stabilité du matching final.
Autre erreur souvent vue dans les commentaires sur APB: celui-ci n’optimisait pas, stricto sensu, les préférences des candidats car il utilisait la version formations proposant de l’algorithme d’acceptation différée (mais pour des problèmes de cette taille il n’y a en général qu’un seul matching stable, donc il est probable que APB donne aussi le matching student-optimal).

Frédérique Vidal à dit... 

Ce pacte de confiance, il traduit également, Mesdames et Messieurs les députés, notre volonté de remettre de l’humain au cœur de la procédure d’entrée en premier cycle. C’était indispensable, car le recours même à l’algorithme avait fini par rendre le système aussi peu intelligible qu’inégalitaire.

4 formations et 5 étudiants en attente

Prenons un exemple très simple : 4 formations universitaires (donc qui sont censées accepter tout le monde), et une "en tension", la verte, qui est très demandée. Regardons étape par étape ce qui se passe avec APB et Parcoursup. 

Etape 1 : les vœux des lycéens

Avec APB, les lycéens devaient classer les vœux, c'est-à-dire choisir quelle formation avait leur préférence. 

Avec parcoursup, ce classement n'est pas demandé, ce qui fait que l'algorithme ne peut pas prédire le choix du candidat, quand deux formations sont proposées.

 Etape 2 : Première réponse

APB repose sur l'algorithme de Gale Shapley qui permet de résoudre le problème des mariages stables [3]. Il va essayer de satisfaire les premiers vœux des étudiants, et proposer une répartition aux universités. Les candidats qui ont préférés une formation sélective (Prépa, IUT, BTS) n'apparaissent pas dans cette réponse, puisque aucun n'aura mis une université en premier vœu.  

L'université rouge et ses 2 étudiants sont ravis. En revanche, deux universités (bleu et orange) n'ont pas d'étudiants et il y a un peu trop de monde dans l'université verte. 

Pour Parcoursup, la première réponse, c'est des propositions, et surtout des listes d'attente avec des positions sur cette liste d'attente. Admettons que tous les candidats soient sur liste d'attente (en position 1, 2, 3)  et que toutes les places universitaires aient été proposées aux élèves qui ont aussi postulé pour des formations sélectives. On peut schématiser l'état des lieux comme ça :

Comme l'écrit Guillaume Haeringer :

On peut difficilement comparer l’algorithme d’APB avec celui de parcoursup. Les algorithmes de parcoursup ne servent qu’à déterminer les choix des formations [..] APB faisait la même chose, mais en plus APB calculait une affection, ce que les algorithmes de parcoursup ne font pas.

Etape 3 : Affectation

Les candidats n'auront pas forcément vu la première réponse d'APB, puisque ce sont les universités qui ont le dernier mot. APB pourrait donc aboutir à une répartition comme celle-là, qui contenterait tout le monde. Certains étudiants auront eu leur second choix, ce qui finalement n'est pas si mal. 

La différence entre cette configuration est celle de l'étape précédente correspond au deuxième paragraphe de la réponse de Guillaume Haeringer : 

Autre erreur souvent vue dans les commentaires sur APB: celui-ci n’optimisait pas, stricto sensu, les préférences des candidats car il utilisait la version formations proposant de l’algorithme d’acceptation différée (mais pour des problèmes de cette taille il n’y a en général qu’un seul matching stable, donc il est probable que APB donne aussi le matching student-optimal).

Pour Parcoursup, je vais supposer qu'à chaque étape, une place se libère dans chaque université dans l'ordre des aiguilles d'une montre : bleu, vert, orange, rouge. La situation peut rester "bloquée" avec des universités sans place qui se libère, ou au contraire, 3 places peuvent se libérer en même temps dans chaque université. On n'en sait rien. 

Admettons donc qu'une place se libère (le petit drapeau vert) dans l'université bleue et qu'elle soit proposée au premier candidat sur liste d'attente. 

Comme c'est sa seule proposition, il va l'accepter. Paroursup pourrait même le décider sans intervention humaine. En revanche, on ne peut pas mesurer la satisfaction du candidat, puisque l'on ne sait pas si c'est son premier choix ou pas. Il va conserver tous ses vœux en liste d'attente, ce qui fait que rien ne change pour les autres candidats. Ils ont les mêmes positions dans les listes d'attente des 3 formations.  

Avec A.P.B, on avait 5 candidats affectés. Là, on a juste un candidat qui a accepté une proposition, sans être affecté pour l'instant à cette université. Parcoursup n'est pas programmé pour cela. 

Etape 4 : L'heure du choix

C'est au tour de l'université verte de proposer une place au premier sur la liste d'attente, à savoir le candidat qui vient d'accepter la proposition de l'université bleue.

Sans connaître sa réponse, les deux autres candidates qui postulent sur l'université verte voient leur place dans la liste d'attente progresser. Celle qui se retrouve première sur liste d'attente est sans doute un peu moins inquiète. Quand au candidat qui a deux propositions, il est aussi ravi que s'il avait eu son premier choix avec APB. Il aura juste dû attendre un peu plus.

Etape 5 : Le choix  (de 1 à 6 jours). 

On voit très bien l'intérêt de remettre l'humain au cœur de la procédure d'entrée en premier cycle : "The Winner Takes It All". Celui qui a gagné peut prendre tout son temps (6 jours) pour libérer une place dans l'université bleue ou verte. 

D'où la phrase : 

On a à faire ici à un problème de many-to-one matching, il faut donc rajouter une fonction de choix du côté des formations. 

Si parcoursup savait que le premier candidat préfère le vert au bleu, il aurait immédiatement proposé une affectation dans l'université verte.

Ca ne change rien pour les autres candidats qui ne profitent pas de la place libérée dans l'université bleue à laquelle ils n'avaient pas postulé. Pour l'université bleue, en revanche, elle aura perdu un candidat qu'elle jugeait bon... C'est maintenant à l'université orange de voir une place qui se libère et de la proposer à la première personne sur la liste d'attente.

Etapes 6, 7, 8 : nouvelles propositions

Au fur et à mesure que les humains au coeur de Parcoursup vont choisir, des places vont se libérer. Les candidats vont recevoir une seule proposition pour chacune des trois universités. Cela peut se passer le même jour, ou avec un décalage que l'on ne peut pas anticiper.

On sent que ça peut durer longtemps, mais que globalement, le seul candidat sans proposition est premier sur une liste d'attente de l'université rouge.

Il peut réviser son bac en fredonnant "Si tu changes d'avis, je suis le premier sur la liste, saisi ta chance avec moi".

If you change your mind, I'm the first in line.
Honey I'm still free
Take a chance on me

Etape 9 : Humain, trop humain

Le première candidate sur la liste d'attente de l'université orange a déjà une affectation, mais comme parcoursup ne connait pas sa préférence, il va lui proposer et potentiellement attendre 6 jours une réponse.

Etape 10 : Tout le monde a sa proposition

Une place se libérant dans l'université rouge, le dernier candidat reçoit enfin une proposition.

Etape 11 : La victoire des plus patients.

Le job de Parcoursup est de proposer des trucs, pas d'inscrire les étudiants à l'université. Ceux qui resteront sur les listes d'attente et retarderont leur inscription, on des chances de voir de meilleures propositions arriver, sans doute au cœur de l'été. 

Etape 12 : Waterloo

Si les préférences sont les mêmes, on pourrait avoir une configuration qui ressemble à celle qu'avait calculée APB, sauf que l'université verte n'est pas surchargée, puisque si les 3 étudiants ont une place, c'est que d'autres ont renoncé à ce choix. Les 5 étudiants seront au final satisfaits, puisqu'ils auront eu le choix qui était le premier.

En revanche, les université n'auront pas les étudiants qu'elles avaient choisi au départ, et deux se retrouveront avec des places vides.

On peut donc parier que malgré la motivation exprimée dans les lettres, ou les attendus, il y aura autant d'étudiants qui se planteront en L1 et se réinscriront dans Parcoursup en 2019 si ça existe encore.

Dans les exemples ci-dessous, j'ai pris 4 formations... Si on ne met aucun critère, Parcoursup propose 13297 formation, dont 2486 licences et 46 première année communes aux études de santé (PACES).
J'ai pris 810000 candidats qui ont fait en moyenne 7 vœux, alors que dans l'exemple, j'ai pris 5 candidats qui ont fait entre 1 et 3 vœux. On sent que le nombre de flèches doit être énorme !

Parcoursup n'est pas APB

Alors qu'ils avaient l'air de se ressembler, de reposer sur des mêmes concepts de choix faits par des étudiants ou des universités, les deux systèmes sont donc complètement différents. En mettant l'humain au coeur de la procédure d'affectation, Parcoursup ajoute des délais qui peuvent être très longs, surtout du point de vue de quelqu'un qui a 18 ans, qui a l'habitude des réponses immédiates quand il interroge Google ou s'exprime sur un réseau social.

On comprend aussi qu'il y aura au final de la place pour ceux qui n'ont pas d'affectation, même s'ils devront aller à Rennes apprendre le russe [4]

A.P.B. a été jeté à la poubelle parce qu'il y avait eu des tirages au sort, que c'était injuste, etc... Mais tant que les algorithmes locaux n'auront pas été publiés, on ne pourra pas garantir qu'aucun tirage au sort n'a eu lieu. Ce sont des humains qui ont créé ces algorithmes, qui s'apparentent sans doute à un bon vieux fichier xls et des choix de tri qui peuvent aussi être l'ordre alphabétique des prénoms ou la date de naissance. Il faut que l'on sache !
  

1. Le nez dans le code 
2. Examen du projet de loi ORE
3. Problème des mariages stables (Wikipédia)
4. Parcoursup. Cinq chiffres insolites sur les vœux émis par les candidats

Modifications de cet article : 

26/05 - 19h26 : 
+ Ajout de "A la fin de l'article, les diverses corrections sont listées. "
+- Correctif ; 6 jours à la place de 5 jours suite au tweet  de Yann Bisiou