Cloud Computing Network Online Internet Storage Concept Data

Rappelons qu’APB est le système d’admission post-bac, auprès duquel chaque bachelier déclare ses préférences auprès de filières d’enseignement post-bac.

Ce système est (ou était, puisque sa mort a été annoncée) censé affecter les étudiants aux établissements en tenant compte des préférences et des critères d’admission.

Il se trouve que ce problème d’apparier deux populations (les étudiants d’un côté et les établissements de l’autre) ayant chacune des listes de préférences exprimées pour les individus de l’autre population (les étudiants pour les établissements et les établissements pour les étudiants) consiste à trouver un appariement parfait stable entre les deux populations. Parfait car chaque étudiant est affecté à un établissement, stable car les préférences ont été respectées au mieux (pour le dire simplement, il n’existe pas deux étudiants qui pourraient échanger leur affectation sans que les établissements s’y opposent parce qu’ils préfèrent garder chacun l’étudiant qui leur a été affecté).

L’algorithme de Gale-Shapley

Ce problème d’appariement stable parfait a été formalisé par deux mathématiciens américains en 1962. Ils ont même proposé un algorithme pour calculer cet appariement, c’est-à-dire établir une liste des couples étudiants – établissements qui soit parfaite et stable. Présentons le principe de cet algorithme sur un cas différent, celui de l’appariement d’une population d’hommes et d’une population de femmes, de mêmes nombres pour ne pas faire de malheureux.

Chaque homme fournit sa liste de préférence parmi toutes les femmes, chaque femme en fait de même avec les hommes.

Et l’algorithme procède ainsi :

  • Prenons un homme non encore engagé à une femme
  • Cet homme fait une proposition à la femme qui a sa préférence, la première de sa liste à qui il n’ait pas déjà fait une proposition
  • Deux cas se produisent :
    • Si la femme à qui il se propose est libre, elle accepte sa proposition et les voilà fiancés
    • Si elle n’est pas libre, elle regarde si l’homme qui vient de lui faire sa demande a sa préférence par rapport à celui auquel elle est engagé
      • Si cet homme a sa préférence, alors elle s’engage avec lui et abandonne son précédent compagnon
      • Sinon elle reste avec son compagnon et notre homme est toujours libre
  • On recommence les étapes précédentes jusqu’à ce qu’il n’y ait plus d’homme libre
  • On dispose à la fin d’un ensemble de couples appariés

Cet algorithme, assez simple finalement, a plein de bonnes propriétés que l’on démontre, dont celle bien entendu de produire un appariement parfait et stable !

Revenant à l’APB, nous voyons qu’à quelques adaptations près, l’appariement des étudiants et des établissements peut se ramener à une variante de l’algorithme de Gale-Shapley.

Si nous nous intéressons aux détails de l’algorithme, nous découvrons quelques propriétés plus gênantes.

Par exemple, tel qu’exprimé ci-dessus, ce sont les préférences des hommes qui sont maximisés. Même si le résultat est stable et parfait, comme les hommes font les propositions, leur préférence prévalent.

Bien sûr, il suffit de remplacer homme par femme dans la rédaction de l’algorithme pour donner la préférence aux femmes.

Nous arrivons là à notre point principal : un algorithme peut être rédigé correctement tout en étant non équitable.

Ainsi APB a-t-il été créé de telle façon que les établissements étaient « favorisés » au dépend des étudiants (tout comme les hommes le sont dans la rédaction de l’algorithme ci-dessus). Ce sujet a-t-il été même formulé lors de la conception du système ?

Vers plus d’équité algorithmique

APB a illustré de façon la plus exacerbée les enjeux derrière les algorithmes dans nos sociétés numériques, probablement pour beaucoup d’autres raisons que celles évoquées ci-avant.

Mais combien d’autres algorithmes, produisant certes des résultats corrects, comporteront des discriminations plus ou moins identifiées, discrètes mais bien effectives ?

Il existe une version « plus juste » de l’algorithme de Gale-Shapley. Cette recherche d’équité algorithmique passera par la sensibilisation des gens de data à ce sujet, comme l’illustre l’algorithme de Gale-Shapley. Et en développant des procédures de testing pour aller plus loin.

Quant à APB, c’est maintenant son successeur qu’il faudra tester…


Avatar de Hervé Mignot
Hervé Mignot

Hervé is passionate about Data Science & Computer Science. He joined Equancy in 2008 as Partner in charge with Data Technologies & Data Science practice, including data engineering, data science and innovating with data. He works cross-industry with leading brands to transform data into predictive models, and crafts innovative data products. He is also acting as Chief Scientist Officer, leading Equancy R&D program. Hervé has a PhD in Computer Science (Machine Learning). He is teaching Big Data & Data Science at ENSAE-ENSAI and is Associate Professor from Aix-Marseille University.

Leave a Reply

Your email address will not be published. Required fields are marked *