Qu'est-ce que l'algorithme de David Gale et Lloyd Shapley ? © Shutterstock

Sciences

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

Question/RéponseClassé sous :Mathématiques , algorithme , bac

Jusqu'en 2017, le système admission post-bac (ex APB, maintenant Parcoursup) gérait l'affectation des bacheliers dans l'ensemble des filières de l'enseignement supérieur. Il a fait scandale quand des injustices flagrantes sont apparues dans ses résultats. Pour examiner la question, une plongée au cœur de l'algorithme utilisé est nécessaire.

Cet algorithme a été présenté en 1962 par les mathé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 source de son implémentation devraient être publics, au moins pour la représentation nationale.

Abonnez-vous à la lettre d'information Mathématiques amusantes : chaque semaine, Futura traite une question de mathématique pour le plaisir des 7 à 77 ans.

!

Merci pour votre inscription.
Heureux de vous compter parmi nos lecteurs !

En savoir plus sur Hervé Lehning

Normalien et agrégé de mathématiques, Hervé Lehning a enseigné sa discipline une bonne quarantaine d'années. Fou de cryptographie, membre de l'Association des réservistes du chiffre et de la sécurité de l'information, il a en particulier percé les secrets de la boîte à chiffrer d'Henri II. 

À découvrir également : L'univers des codes secrets de l'Antiquité à Internet, paru en 2012 chez Ixelles.