Algorithme d'affectation de candidats après concours multiples

L'algorithme d'affectation des candidats après des concours multiples est une application du « problème des mariages stables » résolu selon l'algorithme de Gale et Shapley. L'algorithme, qui fournit une affectation stable, travaille par itérations successives, selon une stratégie de l'individu qui effectue un pari sur les choix des autres impétrants-candidats, selon ce qu'il présume être « la cote » (cela constitue pour le robot son heuristique de fonctionnement propre). Suivant une variante de l'algorithme, chaque candidat peut privilégier son choix de candidat ou bien la qualité des filières ou encore proposer une solution intermédiaire minimisant le nombre de regrets. Cette variante est utilisée en particulier en France pour déterminer l'affectation des étudiants après les concours de PACES, puis PASS (première année des études de santé) et des Épreuves classantes nationales informatisées (parfois abrégées en ECNI).

Problème rencontré

En France

Une variante du système initial est utilisée dans le cadre du fonctionnement de la plateforme Parcoursup, site Web créé en 2018 destiné à recueillir et gérer les vœux d'affectation des futurs étudiants de l'enseignement supérieur français.

Lorsque des candidats sont classés après un concours, l’étudiant le mieux classé choisit la filière de son choix et les suivants choisissent, selon leur position sur le classement, la filière de leur choix parmi celles où des places sont encore disponibles. Ce choix peut se faire en présentiel lors d’une réunion (parfois qualifiée d'« amphi de garnison » similairement aux écoles de l'armée).

Lorsque les mêmes candidats passent plusieurs concours (et obtiennent donc des rangs de classement différents), le problème est un peu plus complexe si l’on veut coordonner les affectations. Nous sommes en présence d’une population de N étudiants et de M filières différentes, chaque filière possédant un nombre de places qui est généralement limité. Les étudiants, qui ont donc passé M concours, ont obtenu M rangs de classement, un dans chacune des filières. Chaque étudiant va devoir exprimer un choix et donc classer les filières par ordre de préférence. De même, on peut considérer que chaque filière va choisir les étudiants en les classant par ordre de préférence (ce classement est bien entendu celui obtenu au concours). Le problème est donc assez symétrique (les filières choisissent les étudiants / les étudiants choisissent les filières) avec généralement des conflits qui surviennent entre choix des filières et choix des étudiants (tous ceux qui préfèrent une filière ne sont pas forcément classés en rang utile).

Il s'agit donc de développer une méthode pour décider de l’affectation des étudiants dans les différentes filières en prenant en compte à la fois les classements des étudiants aux différents concours et leurs préférences entre les différentes filières.

Une méthode serait de procéder filière après filière, mais ceci aurait deux inconvénients majeurs :

• Elle introduirait une hiérarchie entre filières ;
• Un étudiant aurait tendance à choisir la filière dans laquelle il est bien classé, en dépit de son attrait envers une autre filière afin de minimiser les risques.

Ce problème s’est posé lors de la mise en place de la première année des études de santé (PACES) en 2010-2011 et il a été résolu par l’utilisation d’un algorithme dit « algorithme de mariages stables » proposé par David Gale et Lloyd Shapley.

Aux États-Unis

Affectation des organes à transplanter chez des patients dans les hôpitaux publics.

Affectation des étudiants aux postes comportant une bourse d'études de l'enseignement supérieur.

Fonctionnement

Cet algorithme fonctionne de manière itérative.

Si on se place dans le cas retenu pour la PACES en France, où l’on privilégie les choix des étudiants, on procède de la manière suivante :

1. On choisit un étudiant, n’importe lequel (le résultat final ne dépendra pas de l’ordre dans lequel on traite les étudiants) ;
2. On affecte provisoirement cet étudiant dans la filière qu’il préfère ;
3. On recommence l’étape 1 avec un autre étudiant jusqu’à ce qu’il y ait un conflit (plus assez de place dans la filière choisie). Dans ce cas, on regarde tous les étudiants affectés dans la filière et on élimine le moins bien classé de cette filière. Cet étudiant est éliminé définitivement de la filière en question et affecté provisoirement dans la filière de son second choix (ou troisième s’il était affecté dans la filière de son deuxième choix et ainsi de suite) ;
4. On itère à partir de l’étape 1 jusqu’à ce qu’il n’y ait plus aucune modification ;
5. La solution est alors trouvée.

Cet algorithme de mariages stables est convergent (on converge toujours vers une solution) et stable (il trouvera toujours la même solution pour des conditions de départ identiques, quel que soit l’ordre dans lequel on traite les étudiants).

Par ailleurs, lorsqu’un étudiant est éjecté d’une filière A et affecté dans une filière B, il est traité dans la filière B exactement comme un étudiant ayant choisi la filière B en premier choix : seul comptera son rang de classement. Un étudiant ne perd donc aucune chance dans la filière B s’il met en premier vœu la filière A (évidemment, s’il est affecté dans la filière A, il ne pourra pas accéder à la filière B).

Le caractère itératif de l’algorithme explique pourquoi un choix public en direct (« amphi de garnison ») serait psychologiquement désastreux : on commence par affecter un étudiant dans la filière de son premier choix avant, éventuellement, de l’en éjecter. Ceci n’empêche néanmoins pas la transparence et l’analyse des affectations montrera bien que si un étudiant A est affecté dans une filière et pas l’étudiant B, c’est qu'A est mieux classé que B dans cette filière ou affecté dans une autre filière qu’il préfère.

Algorithme du "mariage stable" transposé à l'affectation d'étudiants

Considérons N hommes et N femmes que l’on souhaite marier (cet exemple ne traite que les mariages dans une population sur laquelle une bipartition a été définie).

Chaque homme va classer les N femmes par ordre de préférence ; de même, chaque femme va classer les N hommes par ordre de préférence (sans ex æquo). L’algorithme va ensuite tenter de construire une liste de couples pour lesquels les adultères sont impossibles : en effet, dans la configuration retenue, si un homme souhaite avoir une relation extraconjugale, celle-ci préférera son actuel mari à l’homme en question et refusera donc l’adultère. De même, si une femme trouvait un homme plus à son goût que son actuel mari, l’homme en question préférera son épouse. En découle la notion de mariages stables (pas d’adultère possible).

On peut faire l’analogie suivante qui n'est pas dans la bipartition :

• Les étudiants correspondent aux hommes (par exemple) ;
• Les places disponibles dans les différentes filières correspondent aux femmes.

Affecter les étudiants revient donc à les « marier » avec des filières.

Que garantit cet algorithme ?

Par analogie avec les mariages (c-à-d sans adultère possible), l’algorithme va garantir que si un étudiant A est affecté dans une filière alors que B ne l’est pas, cela signifie que :

• A est mieux classé que B dans cette filière ;
• Ou B a été affecté dans une filière que lui-même préférait.

Ces raisons font que cet algorithme est par exemple utilisé aux États-Unis pour l'affectation des internes (en).

Conflits

Lors des mariages (ou affectations), des situations de conflit peuvent survenir. Dans ce cas, l'algorithme peut être paramétré pour privilégier les choix d'un groupe ou de l'autre.

Dans le cas des affectations des étudiants en première année des études de santé (PACES), en France, les deux options étaient envisageables :

• Privilégier les classements des étudiants dans les filières, pour que chaque filière récupère les étudiants les mieux classés ;
• Ou privilégier les choix des étudiants, pour que les étudiants soient satisfaits.

C’est la seconde solution qui a été retenue pour les raisons suivantes :

• Les étudiants seront satisfaits dans la mesure du possible ;
• Les filières récupéreront des étudiants motivés ;
• Même dans l’intérêt des filières, il est probablement préférable de récupérer un étudiant un peu plus motivé qu’un étudiant un peu mieux classé ;
• Ceci évite des situations de croisement comme présentées au paragraphe suivant.

Situation de croisement

Supposons 100 places disponibles en médecine et 100 places disponibles en pharmacie.

Dans le cas où l’affectation privilégie le choix des filières, on pourrait dans certains cas aboutir à la configuration suivante :

• L’étudiant A est classé 150^e en médecine et affecté à la dernière (100^e) place disponible en médecine, mais il préférerait pharmacie (où il est classé 151^e) ;
• L’étudiant B est classé 150^e en pharmacie et affecté à la dernière (100^e) place disponible en pharmacie, mais il préférerait médecine (où il est classé 151^e).

Ces deux étudiants sont presque aussi bons dans les deux filières. Ils souhaiteraient permuter leurs affectations (ce qui est impossible) et seront donc frustrés. Le fait de privilégier les étudiants dans le choix évite ce genre de situation.

Déroulement de l'algorithme sur un exemple

Soient X, Y, Z trois filières disposant respectivement de 2, 1 et 2 places. Soient cinq candidats A, B, C, D et E dont les résultats et les choix sont définis par les listes suivantes :

Classements par filière X [BCEAD] Y [CADEB] Z [BDECA]

Choix des candidats A [XYZ] B [YXZ] C [ZYX] D [YXZ] E [YXZ]

À partir de ces données, on peut démarrer l'algorithme :

• On affecte sa filière préférée à chaque étudiant : A$\rightarrow$X / B$\rightarrow$Y / C$\rightarrow$Z / D$\rightarrow$Y / E$\rightarrow$Y
• La filière Y déborde (1 place, 3 candidats BDE ; on élimine les 2 moins bien classés B et E et on les affecte à leur filière de deuxième choix) : A$\rightarrow$X / B$\rightarrow$X / C$\rightarrow$Z / D$\rightarrow$Y / E$\rightarrow$X
• La filière X déborde (2 places, 3 candidats ABE ; on élimine le moins bien classé, A et on l'affecte à la filière de son choix suivant) : A$\rightarrow$Y / B$\rightarrow$X / C$\rightarrow$Z / D$\rightarrow$Y / E$\rightarrow$X
• La filière Y déborde (1 place, 2 candidats AD ; on élimine le moins bien classé D et on l'affecte à sa filière de choix suivant) : A$\rightarrow$Y / B$\rightarrow$X / C$\rightarrow$Z / D$\rightarrow$X / E$\rightarrow$X
• La filière X déborde (2 places, 3 candidats BDE ; on élimine le moins bien classé, D et on l'affecte à la filière de son choix suivant) : A$\rightarrow$Y / B$\rightarrow$X / C$\rightarrow$Z / D$\rightarrow$Z / E$\rightarrow$X
• Aucune filière ne débordant plus, les itérations prennent fin. On aboutit au résultat : A$\rightarrow$Y / B$\rightarrow$X / C$\rightarrow$Z / D$\rightarrow$Z / E$\rightarrow$X

Le résultat est satisfaisant, car :

• Dans la filière X, sont affectés B et E ; C est mieux classé que E, mais a été affecté dans une filière qu'il préférait (Z) ;
• Dans la filière Y, est affecté A ; C est mieux classé que A, mais a été affecté dans une filière qu'il préférait (Z) ;
• Dans la filière Z, sont affectés C et D ; B est mieux classé qu'eux deux, mais a été affecté dans la filière X qu'il préférait à Z ; E est mieux classé que C, mais a été affecté dans la filière X qu'il préférait à Z.