APB utilisait « l’algorithme des mariages stables » pour affecter les candidats aux filières, un algorithme optimal, tandis que ParcourSup est un algorithme ad hoc, opaque, qui ne peut par définition pas faire mieux.

La citation ci dessus est une version un peu raccourcie (et donc nécessairement un peu caricaturale, je m’en excuse) de plusieurs threads ou articles de blogs récents apparus sur les réseaux sociaux. Mon analyse est que, indépendamment de l’opinion qu’on peut avoir sur le principe de la réforme, l’affirmation ci-dessus est factuellement infondée. On peut être contre ParcourSup, mais pas pour cette (mauvaise) raison.

À nouveau, on est sur un sujet d’actualité brulante et donc ouvert à la controverse entre les différentes parties mobilisées par la loi Orientation et Réussite des Etudiants. Comme tout le monde, j’ai un avis, mais ce n’est pas le sujet du billet (même si la neutralité de point de vue du billet peut, j’en conviens, être affectée par mon opinion). On peut être pour ou contre la réforme des conditions d’accès à l’université, mais la question posée est celle des bases factuelles de cette affirmation sur les outils informatiques sous-tendant la réforme.

C’est un sujet qui m’a vraiment titillé. Pour vous raconter ma lointaine vie antérieure, il se trouve que je connais bien le sujet, puisque j’ai eu à coder l’algorithme des mariages stables (ou algorithme de Gale-Shapley) pour gérer des questions pratiques d’affectation d’étudiants à des stages. A l’époque c’était en Fortran (je sais, ça fait vraiment ancien combattant…). C’était donc il y a longtemps (environ 30 ans…), mais je n’ai pas tout oublié de la sueur dépensée à écrire et tester le programme qui décidait de l’avenir de mes jeunes co-religionnaires étudiants affectés en stage.

Dans la citation ci-dessus, je vois plusieurs affirmations implicites qui méritent un minimum de fact-checking, dans l’esprit de ce blog :

• APB utilise l’algorithme de Gale-Shapley ou algorithme des mariages stables.
• L’algorithme des mariages stables est optimal
• ParcourSup est un algorithme

L’algorithme APB est-il basé sur l’algorithme des mariages stables ?

Cette question suppose de dire deux mots d’explication à la fois sur APB et sur l’algorithme des mariages stables. Commençons par le second.

Les mariages stables

L’algorithme des mariages stables (ou Gale-Shapley) permet de résoudre un problème d’optimisation classique. On a deux ensembles pour lesquels il faut procéder à des appariements : des étudiants avec des stages, des bacheliers avec des filières universitaires ou encore des prétendants hommes qui font la cour avec des fiancées potentielles femmes… Dans chacun des deux ensembles (par exemple : hommes et femmes), chaque individu formule une liste de préférence de ses choix de partenaires.

L’algorithme des mariages stables permet de trouver un appariement entre les deux ensembles (hommes/femmes, candidats/filières) qui est stable, c’est à dire qu’il n’est pas possible de faire une permutation entre deux couples (homme-femme, candidat-filière) qui améliore simultanément le rang des préférences des deux. C’est donc une solution globale qui est proposée aux demandeurs pour résoudre d’un seul coup l’ensemble des préférences qu’ils ont formulées. Il y a un élément important sur lequel je vais revenir par la suite : Gale-Shapley suppose que les deux groupes impliqués (hommes et femmes, candidats et filières, étudiants et stages) formulent chacun des ordres de préférence.

La problématique APB

L’affectation des bacheliers dans des filières du supérieur a d’abord été effectuée par APB, un système né localement en 2002, puis généralisé au niveau national. APB a été initialement développé pour les affectations des étudiants dans les filières sélectives, et notamment dans les classes prépa. Dans ce contexte de filières sélectives, on avait donc bien simultanément des préférences formulées par les bacheliers pour les classes prépa et des classements des bacheliers candidats effectués par les prépa, comme précisé juste au dessus. On est donc dans les conditions d’application standard de l’algorithme des mariages stables / Gale-Shapley.

A partir de 2009, APB a géré l’ensemble des filières au niveau national, y compris les filières universitaires non-sélectives. La problématique a progressivement changé de nature pour plusieurs raisons :

1. Les filières universitaires (licences générales, PACES) sont non-sélectives, donc on sort des conditions strictes d’application de l’algorithme de Gale-Shapley. En effet, seuls les étudiants établissent une liste de préférences de vœux, pas les universités qui ne formulent aucune hiérarchisation. Dans ce contexte, l’algorithme n’est plus directement applicable, puisque les universités n’ont pas d’ordre de préférence pour les candidats. On peut en principe contourner cette difficulté en « créant artificiellement » une hiérarchisation des candidats par les universités, par un tirage au sort interne à l’algorithme. Cette méthode avec tirage au sort est utilisée localement aux USA ou aux Pays-Bas pour répartir des élèves dans des écoles, sous le nom Deferred Acceptance algorithm.
2. Un certain nombre de critères ad hoc rajoutés dans APB au cours des années sont difficilement compatibles avec les principes initiaux de l’algorithme des mariages stables : distinction entre vœux relatifs et vœux absolus, priorité donnée aux candidats ayant formulé six vœux en licence dans la même mention, préférence régionale (ou académique), obligation de mettre une licence « pastille verte », vœux groupés.

Quel est véritablement l’algorithme sous-jacent dans APB ?

Mon analyse est qu’initialement APB a pu être une version adaptée de l’algorithme des mariages stables quand il ne concernait que des filières sélectives sans autres critères, mais qu’il en avait largement divergé dans les dernières années, quand il a été appliqué systématiquement à tous les vœux des bacheliers.

D’ailleurs, la publication d’éléments de l’algorithme APB suite à plusieurs actions en justice courant 2016 montre bien qu’APB avait très largement divergé de l’algorithme des mariages stables pour devenir à mon sens une « usine à gaz » (= aéroergastère) de première catégorie, bourrée de traitements ad hoc.

L’algorithme est-il optimal ?

Là, il faut s’entendre sur les termes. Dire que l’algorithme des mariages stables fournit une solution optimale est un raccourci, qui peut donner l’impression qu’il y aurait une solution idéale unique et que le programme la produirait à coup sûr. L’algorithme fournit une solution stable, ce qui n’est pas du tout la même chose. Une solution stable, c’est une solution qu’on ne peut pas améliorer par une permutation simple entre deux couples (homme-femme, candidat-filière), elle est optimale au sens de Pareto. Mais la notion d’optimalité dans ce contexte est intrinsèquement relative et il n’y a pas qu’une seule solution stable (ou Pareto-optimale), mais en général plusieurs (voir la publication de D. Knuth sur la question). Dans le cas des mariages hommes-femmes, il y a des solutions globalement optimales pour les hommes (qui obtiennent collectivement leurs meilleurs choix, au détriment de ceux des femmes), et symétriquement des solutions globalement optimales pour les femmes (au détriment des hommes). Il y a aussi des solutions stables qui optimisent simultanément les choix des deux ensembles (hommes et femmes) au prix de compromis pour les uns et les autres.

L’algorithme de Gale-Shapley n’est d’ailleurs pas le seul possible pour faire des appariements, en particulier lorsque les individus de l’un des ensembles ne formulent pas de liste hiérarchisée de vœux (comme c’est le cas pour les filières universitaires) : il y a aussi l’algorithme d’appariement de Boston (appelé ainsi, parce qu’il a été développé pour affecter les élèves dans les écoles publiques de Boston) ou encore l’algorithme TTC  (Top Trading Cycle, aussi dû à Gale & Shapley) initialement imaginé à partir d’un problème de répartition de chambres dans des résidences étudiantes. L’algorithme TTC donne aussi des solutions optimales au sens de Pareto, mais différentes de celles de l’algorithme de Gale-Shapley.

Qu’est-ce qui est mieux ? C’est une question subjective et qui relève d’un jugement externe, pas un paramètre objectif et absolu.

Doit-on optimiser le nombre de candidats obtenant leur premier vœux (ce que fait l’algorithme Boston), le rang moyen du vœu finalement obtenu par le candidat ? Doit-on minimiser le nombre de candidats obtenant leur dernier vœu (pastille verte…), voire pas de vœux ? Doit-on privilégier un algorithme qui est insensible aux stratégies de contournement que les candidats pourraient essayer de développer en faisant leur liste de vœux (ce que fait l’algorithme TTC) ?

Je soutiens de surcroit que l’algorithme d’APB n’était plus l’algorithme des mariages stables / Gale-Shapley pour les raisons évoquées ci-dessus. Le nombre de contorsions/modifications qu’on a imposé au système l’en ont nécessairement fait fortement diverger. Dès lors, on ne peut le parer des caractéristiques ou vertus démontrées pour ledit algorithme princeps (sauf à le démontrer explicitement, ce qui n’a jamais été fait, à ma connaissance).

Dire que l’algorithme APB était optimal est donc à mon sens un double abus de langage : l’algorithme APB a largement divergé de l’algorithme des mariages stables et l’optimalité de ce dernier est de toute manière une notion  tout à fait subjective.

Comme souvent, lorsqu’on a un outil ou une règle imposée par des autorités extérieures,  on/nous sommes nombreux à stigmatiser ses défauts. Mais dès qu’on réforme cette règle critiquée, de nombreuses voix s’élèvent soudain pour expliquer que c’était mieux avant. J’ai un peu l’impression que c’est ce qui se passe aujourd’hui pour APB.

ParcourSup est-il un algorithme ?

Dans ParcourSup, on a un renversement partiel des règles de fonctionnement par rapport à APB. Ce sont les filières universitaires qui vont formuler des classements des étudiants, tandis que ces derniers ne hiérarchisent plus leurs vœux sur la plate-forme informatique (même si cette hiérarchisation doit en principe bien exister dans leur tête).

Dans ce contexte, l’application stricte de l’algorithme des mariage stables est tout aussi impossible qu’avec APB. Mais cette fois-ci c’est pour la raison inverse : pour APB, il n’y avait pas de préférences exprimées par les universités, tandis que pour ParcourSup, il n’y a plus de préférences exprimées par les étudiants. En conséquence, il n’est pas possible d’avoir une automatisation de la procédure d’affectation.

Dans la phase d’affectation des candidats, ParcourSup n’est pas un algorithme stricto sensu. C’est un outil de gestion du désistement des étudiants, par lequel ils vont exprimer leur préférences et leur choix de filières, a posteriori.

A titre personnel, je m’interroge sur la logique qui a consisté à ne pas demander aux candidats de formuler de hiérarchisation de leurs vœux, comme avant dans APB. Je ne comprends pas. La mécanique de désistement manuel me paraît très lourde, anxiogène et susceptible de générer de nombreux recours.

Mais comme je suis un pragmatique, j’attend de voir ce que ça va donner avant de formuler un jugement. C’est mon coté scientifique expérimentateur. Tant que je n’ai pas le résultat de la manip, je m’astreins à faire taire mes idées préconçues.