Parcoursup : quel est l’algorithme derrière l’APB ?

Cet algorithme a été présenté en 1962 par les mathématiciensmathématiciens David Gale et Lloyd Shapley en utilisant la métaphore du mariage. Le but est de réaliser des « mariages stables » dans le sens qu'on ne puisse trouver un homme et une femme qui se préfèrent l'un l'autre à leurs conjoints respectifs. Cette contrainte implique qu'hommes et femmes désignent au préalable les personnes du sexe opposé qu'ils jugent acceptables et les classent, sans ex aequo.

L’algorithme de Gale-Shapley

Pour construire une solution stable, Lloyd Shapley a proposé un algorithme fondé sur l'idée traditionnelle : l'homme propose, la femme dispose. Il applique cette logique en procédant par étapes, chacune se scindant en deux parties. Dans la première, les hommes font des propositions de mariage. Les femmes les rejettent ou les acceptent.

David Gale à gauche et Lloyd Shapley à droite. © Jarssker09, © Bengt Nyman, Wikimedia commons, CC by-sa 3.0

À la première étape, chaque homme propose le mariage à la femme qu'il préfère sans tenir compte d'éventuels concurrents. À ce moment, chaque femme accepte la proposition qu'elle préfère parmi celles qu'elle a reçues. Elle se « fiance » alors à celui-ci en rompant éventuellement ses fiançailles précédentes. Les femmes ne recevant aucune proposition de mariage attendent l'étape suivante.

Quand celle-ci arrive, les hommes déjà fiancés ne font rien, les autres font une proposition aux femmes qui ne les ont pas déjà refusés. Après un nombre fini d'étapes, l'algorithme de Gale-Shapley donne des mariages stables. Il ne s'agit pas des seuls mariages possibles mais la solution est optimale... pour les hommes. À l'inverse, les femmes ne peuvent pas être plus mal loties.

Les injustices dans l'APB

Dans l'APB (admission post-bac), les candidats jouent le rôle des femmes, ils ne peuvent donc pas être plus mal lotis. D'autre part, l'algorithme repose sur le fait qu'établissements comme candidats classent leurs préférences sans ex aequo. Dans les filières sélectives, cela peut fonctionner. Dans les autres, il est naturel de tirer au sort... ce qui engendre fatalement des injustices.

Le côté technique ne doit pas cacher que les choix à faire sont politiques et ne doivent pas être masqués par les contraintes techniques. Ainsi, le cahier des charges de l'algorithme comme le code sourcecode source de son implémentation devraient être publics, au moins pour la représentation nationale.