L’algorithme d’appariement d’Affelnet

[Mise à jour 14/05/2023] j’ai publié cette vidéo sur ce sujet : https://youtu.be/DTC3wrlOuNg

J’ai précédemment tenté de présenter le principe général du mécanisme d’affectation d’Affelnet, mais par souci de simplicité préliminaire, j’ai éludé l’algorithme précis qui associe les collégiens aux lycées. Donc voici ce que j’ai trouvé sur le sujet (il faut creuser avec ténacité car l’opacité est de rigueur avec le rectorat…).

Julien Grenet, directeur de recherche au CNRS, précise lors d’une conférence en 2017 l’algorithme utilisé par Affelnet (le support est aussi disponible): il s’agit du fameux algorithme d’appariement de Gale et Shapley déjà utilisé dans ce type de contexte d’affectation, mais pas seulement (affecter les internes aux hôpitaux par exemple).

Il a d’ailleurs re-confirmé l’information tout récemment lors du comité de suivi Affelnet du 12 avril 2021, qu’il préside.

La bonne surprise c’est qu’il est très simple. Pour s’en convaincre, regardez (au moins) la première moitié de la présentation du célèbre vulgarisateur scientifique David Louapre , qui l’explique de manière limpide en utilisant les personnages de Game of Thrones dans une vidéo (il traite de ParcourSup mais on parle bien du même algorithme qui était utilisé sur APB, l’ancienne version de ParcourSup).

Un exemple simple

Prenons un exemple de 3 lycées A, B et C (A à forte pression, C à faible pression) offrant chacun 2 places (en vert le premier vœu de l’élève, en orange le deuxième et en bleu le troisième) :

Avec la variante où les lycées proposent, les itérations s’effectuent comme suit :

1a. Les 3 lycées demandent leur élève préféré (ici tous les lycées veulent Emma).
1b. Emma ayant déclaré préférer le lycée A, elle y est donc associée.

2a. Les 3 lycées font leur deuxième proposition : Enzo.
2b. Ce dernier avait préféré le lycée B, il y est donc associé.

3a. Les 3 lycées proposent Léa.
3b. Celle-ci avait préféré le lycée A, elle y est donc associée.

A ce stade, le lycée A à forte pression est complet. Il cesse donc de proposer.

4a. Les lycées B et C proposent Lucas
4b. Celui-ci voulait en priorité le lycée A mais il est complet, donc on passe à son 2e vœu : le lycée C

Et ainsi de suite, on arrive très vite au résultat suivant :

On peut noter que s’il on avait laissé les élèves proposer en premier, dans cette configuration (où le classement est le même pour les 3 lycées), on aurait obtenu le même résultat d’affectation (faites l’exercice !).

D’ailleurs Julien Grenet mentionne ce point lors de la conférence pré-citée, et confirme bien que finalement le fait de donner “la main” aux lycées n’a que peu de conséquences (surtout maintenant où des élèves de secteurs 2/3 ne peuvent pas concurrencer les élèves de secteur 1).

Le mérite de cet algorithme est qu’il est stable, c’est à dire équitable : si un élève ayant moins de points que moi sur un lycée a été admis à ce lycée, alors que moi pas, alors forcément j’ai été admis sur un autre lycée que je préférais à celui-là.

Remarque : comme indiqué précédemment, il y a un Affelnet pour les boursiers et un Affelnet pour les non-boursiers. Donc il est probable que le dernier admis boursier et le dernier admis non-boursier n’ait pas le même score Affelnet. Donc l’affirmation précédente ne vaut que pour les boursiers d’une part, pour les non-boursiers d’autre part, mais pas globalement sur les deux groupes.

Le reproche qui restait sur l’algorithme était celui du nombre de vœux limité car cela nécessite d’avoir une vague idée de la probabilité d’obtenir tel ou tel lycée pour ne pas choisir 8 ou 10 lycées perdus d’avance. Mais la nouvelle mouture 2021 semble régler ce problème avec la promesse d’affectation dès le premier tour pour peu qu’on ait sélectionné les 5 lycées de secteur 1 parmi les 8/10 possibles.

Conclusion

On voit que finalement l’algorithme d’association est simple et équitable, et qu’il ne pose pas de problématiques particulières. C’est simplement le score en points qui détermine notre classement et donc notre probabilité d’être admis dans un lycée. Comme déjà évoqué, on peut donc parfaitement “tenter” les lycées qui nous plaisent en premier sans pour autant amputer nos chances d’obtenir les autres en cas d’échec.
Il reste donc à analyser la pondération relative des divers éléments participant à notre score Affelnet pour mieux comprendre nos chances d’être admis dans tel ou tel lycée : j’ai creusé ce point dans un autre article.

Pour les geeks …

L’algorithme de Gale & Shapley est suffisamment connu pour ne pas avoir à le programmer soi-même. Les “Pythonistes” peuvent utiliser cette librairie. Sinon, j’ai plutôt utilisé l’API prête à l’emploi sur le site de MatchingTools.

Pour vérifier l’exemple précédent, il suffit de spécifier les données d’entrée sous forme d’un fichier specs.json comme suit :

{
  "student_prefs": [
    {
      "Emma": [
        "A",
        "B",
        "C"
      ],
      "Enzo": [
        "B",
        "C",
        "A"
      ],
      "Léa": [
        "A",
        "B",
        "C"
      ],
      "Lucas": [
        "A",
        "C",
        "B"
      ],
      "Clara": [
        "B",
        "A",
        "C"
      ],
      "Nathan": [
        "A",
        "B",
        "C"
      ]
    }
  ],
  "college_prefs": [
    {
      "A": [
        "Emma",
        "Enzo",
        "Léa",
        "Lucas",
        "Clara",
        "Nathan"
      ],
      "B": [
        "Emma",
        "Enzo",
        "Léa",
        "Lucas",
        "Clara",
        "Nathan"
      ],
      "C": [
        "Emma",
        "Enzo",
        "Léa",
        "Lucas",
        "Clara",
        "Nathan"
      ]
    }
  ],
  "college_capacity": [
    {
      "A": 2,
      "B": 2,
      "C": 2
    }
  ]
}

Ensuite, via Postman ou directement en ligne de commande, il ne reste qu’à appeler l’API (en paramètre optimum vous indiquez qui propose : college-optimal pour les lycées, sinon student-optimal pour les élèves) :

curl -X POST ‘https://api.matchingtools.org/hri/demo?optimum=college-optimal' — header ‘Content-Type: application/json’ -u mannheim:Exc3llence! -d @’/path/to/specs.json'

Et vous obtiendrez le résultat d’affectation suivant :

{
  "hri_matching": [
    {
      "college": "A",
      "student": "Emma"
    },
    {
      "college": "B",
      "student": "Enzo"
    },
    {
      "college": "A",
      "student": "Léa"
    },
    {
      "college": "C",
      "student": "Lucas"
    },
    {
      "college": "B",
      "student": "Clara"
    },
    {
      "college": "C",
      "student": "Nathan"
    }
  ]
}

Vous pouvez ré-essayer en changement le mode d’appel à “élève-proposant” (optimum=student-optimal) et ainsi vérifier que l’on obtient dans ce cas de figure les mêmes affectations.