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 et de l'algorithme de Gale et Shapley à un problème pratique. L'algorithme, qui fournit une affectation stable, travaille par itérations successives, selon une stratégie qui peut, ou bien privilégier les choix des candidats, ou bien la qualité des filières, ou bien encore proposer une solution intermédiaire minimisant le nombre de regrets. Il est utilisé, 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 posé

Lorsque des candidats sont classés après un concours, leur affectation est simple : l’étudiant le mieux classé choisit la filière de son choix et les suivants choisissent, selon leur rang de classement, la filière de leur choix parmi celles où il reste des places. Il n’y a là aucune difficulté conceptuelle. Ce choix peut se faire en direct lors d’une réunion parfois appelée « amphi de garnison ».

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 rang 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 faut donc trouver 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 du fait qu'une autre a sa préférence, pour éviter de lâcher la proie pour l’ombre (i.e. pour minimiser le risque).

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.

Algorithme de mariage stable

Considérons N hommes et N femmes que l’on souhaite marier (cet algorithme ne traite que les mariages dans une population sur laquelle une bipartition a été définie). Si l’on accepte de s’éloigner quelque peu du romantisme du coup de foudre, on va procéder de la manière suivante : 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 tromper sa femme, 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 ne serait pas d’accord, préférant son épouse à la femme en question. C’est de là que vient le terme de mariages stables (pas d’adultère possible).

Quel est le lien entre ce problème matrimonial et nos étudiants ? On peut simplement faire l’analogie suivante :

• 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 et l’absence d’adultère possible, l’algorithme va garantir la chose suivante : si un étudiant A est affecté dans une filière alors que B ne l’est pas, ce peut être :

• soit que A est mieux classé que B dans cette filière (et dans ce cas c’est juste)
• soit que B a été affecté dans une filière que lui-même préférait (dans ce cas, il n’a pas non plus à s’en plaindre)

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

Deux options pour faire tourner cet algorithme

Lors des mariages (ou affectations), des situations de conflit peuvent survenir. Dans ce cas, l’algorithme peut être paramétré soit pour privilégier les choix des hommes, soit pour privilégier les choix des femmes (c’est d’ailleurs la raison pour laquelle l’algorithme ne peut fonctionner que pour des mariages hétérosexuels).

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

• soit privilégier les classements des étudiants dans les filières, pour que chaque filière récupère les étudiants les mieux classés
• soit privilégier les choix des étudiants, pour que les étudiants soient satisfaits (dans la mesure du possible)

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é (les étudiants affectés sont de toute manière de « bons » étudiants).
• ceci évite des situations de croisement comme présenté 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 ait privilégié le choix des filières (et non celui des étudiants), 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.

Comment fonctionne cet algorithme ?

Cet algorithme fonctionne de manière itérative. Si on se place dans le cas retenu pour la PACES 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).

Notons aussi que 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 qui aurait choisi la filière B comme 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.

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, c'est la fin des itérations. 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

Quelle stratégie les étudiants doivent-ils adopter pour formuler leurs vœux ?

L’algorithme a un intérêt majeur : il garantira la meilleure solution possible aux étudiants compte tenu de leurs rangs de classement.

La stratégie que les étudiants doivent adopter est donc très simple : ils mettent en premier choix la filière qu’ils préfèrent (même s’ils estiment avoir très peu de chance de succès dans cette filière). Au mieux, avec beaucoup de chance (par le jeu d’affectations dans d’autres filières), ils y seront affectés. Au pire, ils se retrouveront par rapport aux autres filières exactement dans la même situation que s’ils avaient d’emblée choisi les autres filières.

Aucune stratégie compliquée n’est donc à adopter : on exprime simplement ses préférences contrairement à l'ancienne procédure APB où le fait de ne pas mettre certaines filières universitaires en premier choix pouvait diminuer ses chances d'y être admis.