Avant d’exprimer ses vœux d’affectation il est utile de comprendre comment les affectations seront calculées.
Le principe général des affectations est que si un candidat n’est pas affecté à son premier vœu, alors tous les postes « préférés » à celui auquel le candidat est affecté (c’est-à-dire les postes mieux classés dans les vœux) ont été affecté à des candidats mieux classés qui ne se sont pas désistés. Une affectation satisfaisant ce critère est dite « stable ».
Exemple : le candidat A a exprimé les vœux suivants :
1er vœu : poste X
2ème vœu : poste Y
3ème vœu : poste Z
Si le candidat A est affecté au poste Z, alors les postes X et Y sont pourvus à des candidats mieux classés que le candidat A. Dans ce cas, il n’est pas possible que le poste X ou le poste Y ne soient pas pourvus, ni qu’ils soient pourvus à des candidats moins bien classés que le candidat A.
Il peut y avoir plusieurs affectations stables.
Exemple : Les candidats A et B son classés sur les postes X et Y (et seulement ces deux postes). A est classé 1er sur le poste X et 2ème sur le poste Y. B est classé 2ème sur le poste X et 1er sur le poste Y.
Vœux de A : (1) Y, (2) Y
Vœux de B : (1) X, (2) Y
Il y a deux affectations stables :
- Affectation 1 : A affecté au poste X, B affecté au poste Y
- Affectation 2 : A affecté au poste Y, B affecté au poste X.
A et B préfèrent l’affectation 2 à l’affectation 1 : ils sont tous deux affectés à des meilleurs vœux que dans l’affectation 1.
Dans ce cas de configuration, l’affectation choisie par l’application Galaxie sera l’affectation 2, celle préférée (selon les vœux exprimés) par les candidats.
Remarque importante : quelques soient les vœux et les classements, s’il y a plusieurs affectations dites « stables », l’affectation stable préférée par tous les candidats est unique. L’ensemble des affectations stables forme un treillis complet, les deux extrêmes du treillis étant l’affectation stable préférée par tous les candidats et l’affectation stable préférée par tous les départements (selon leurs classements). Il s’agit ici des préférences sur les affectations déduites à partir des préférences sur les postes : un candidat préfère une affectation X à une affectation Y si le poste auquel il est affecté avec X est préféré au poste auquel il est affecté avec Y. L’existence d’un treillis n’est valable que lorsque l’on se restreint à l’ensemble des affectations stables.
L’algorithme
L’algorithme utilisé par l’application Galaxie est un peu complexe, mais il est en fait équivalent à l’algorithme dit « d’acceptation différé » de D. Gale et L. Shapley (American Mathematical Monthly, 1962, vol. 69, 9-15).
Le principe de base de l’algorithme est que pour chaque candidat on va essayer de l’affecter à son premier vœu. Si cela n’est pas possible, on essaye le 2ème vœu, puis le 3ème, etc.
L’algorithme est le suivant :
1ere étape : Chaque candidat propose d’être affecté à son premier vœu. Si un poste se voit proposer une affectation par un ou plusieurs candidats (qui sont classés sur ce poste) alors le candidat le mieux classé sera temporairement affecté à ce poste.
2ème étape : Les candidats qui n’ont pu être affectés (temporairement) lors de la première étape proposent d’être affectés à leur 2ème vœu. Pour chaque poste, on considère l’ensemble des candidats qui proposent d’y être affecté ainsi que le candidat qui a été affecté à ce poste lors de l’étape précédente (si cela est le cas). Le candidat mieux classé sera celui qui sera affecté temporairement.
En général, étape k : Les candidats qui n’ont pas pu être affecté à l’étape précédente (c’est-à-dire rejetés) proposent une affectation au poste le mieux classé dans leurs vœux pour lequel ils n’ont pas encore proposé d’affectation. Chaque poste considère l’ensemble des candidats qui proposent d’y être affecté à l’étape k et le candidat affecté temporairement lors de l’étape k-1 (si un tel candidat existe). Le candidat affecté temporairement à l’étape k est le mieux classé parmi tous ces candidats.
Si un candidat n’a pas pu être affecté à aucun des postes dans sa liste de vœux l’algorithme se termine pour ce candidat.
L’algorithme s’arrête lorsqu’il n’y a plus de candidat rejeté. Les affectations temporaires deviennent définitives.
Au cours de l’algorithme, un candidat peu donc se voir affecté temporairement à son premier vœu lors de la première étape et rejeté lors de l’étape k. À l’étape k+1 il proposera alors une affectation à son 2ème vœu.
Comment classer ses vœux ?
La meilleure option pour un candidat est de classer ses vœux en fonction de ses vraies préférences, indépendamment de la position dans le classement pour ces postes. Dans la littérature sur les modèles d’appariement (matching theory) on dit que révéler ses vraies préférences est une stratégie dominante. En d’autres termes, quelques soient les vœux des autres candidats et des classements, il n’est pas possible de trouver une liste de vœux différente de celles des vraies préférences telle que l’on puisse être affecté à un poste préféré que celui obtenu en exprimant ses vraies préférences.
Ce résultat a été démontré par Alvin Roth (Mathematics of Operation Research, 1982, vol 7 (4)) et Dubins et Freedman (American Mathematical Monthly, 1981, vol 7).
Il existe une vaste littérature scientifique sur le problème d’affectation. Le prix 2012 de la Banque Royale de Suède en Sciences Économiques en mémoire d’Alfred Nobel a été décerné à Lloyd Shapley et Alvin Roth pour leurs travaux sur les procédures d’affectations du type de celle utilisée par l’application Galaxie.
Pour de plus amples informations :
- http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/popular.html
- G. Haeringer et V. Iehlé (2010), « Enjeux stratégiques du concours derecrutement des enseignants-chercheurs », Revue Économique, vol. 61, pp. 697-721.
Quelles sont les garanties d’obtenir un poste ?
Un candidat peut être certain d’être affecté à un poste seulement s’il a été classé 1er sur un poste et celui-ci figure dans sa liste de vœux.
Doit-on exprimer un vœu pour tous les postes où on est classé ?
Non. Mais on diminue ses chances d’être affecté à un poste. Cependant, il existe des situations où certains vœux ne sont pas pertinents. Prenons le cas d’un candidat classé sur plusieurs postes, quelques fois premier et quelques fois à des rangs inférieurs :
Poste A : 1er
Poste B : 3ème
Poste C : 1er
Poste D : 4ème
Poste E : 2ème
Les préférences vraies du candidat sont :
1er vœu : B
2ème vœu : D
3ème vœu : A
4ème vœu : E
5ème vœu : C
Supposons que le vœux du candidat correspondent à ses préférences : B, D, A, E, C.
Dans ce cas, seuls les 3 premiers vœux sont pertinents. L’algorithme d’affectation va tenter d’affecter ce candidat d’abord sur le poste B, puis le poste D, puis le poste A. Si les vœux des autres candidats et les classements des postes sont tels qu’il y a une étape de l’algorithme pour laquelle le candidat propose une affectation au poste A (il a été rejeté par les postes B et D), alors cette affectation sera l’affectation définitive pour ce candidat. Étant classé 1er, il sera impossible de rejeter ce candidat pour ce poste en faveur d’un autre candidat. Dans ce cas, ce candidat peut se contenter de mettre comme vœux B, D et A. Les vœux pour les postes E et C n’auront aucun impact.
Confidentialité : Les commissions peuvent-elles savoir quels sont mes vœux ?
En principe non, les vœux sont confidentiels. Mais il y a certaines manières de déduire, partiellement, les vœux des candidats si l’on connaît les classements et l’affectation finale. Prenons l’exemple précédent. Supposons que le candidat soit affecté au poste D (ou B). On saura alors que le poste A n’est pas le premier vœu. Si le poste A avait été son premier vœu il aurait affecté à ce poste, ce qui n’est pas le cas.
Si le candidat est affecté au poste A les choses sont différentes : il sera impossible de savoir si le candidat a mis le poste A en 1er , 2ème ou 3ème vœu. Il en est de même si le candidat émet comme les vœux suivants (dans l’ordre) D, B, A, ou B, A, ou D, A, ou A seulement. Étant affecté au poste A, chacune de ces quatre possibilités donneront la même affectation au candidat : le poste A. Mais cela n’est pas vrai pour les autres candidats : le candidat ne changera pas son affectation finale selon qu’il choisisse une de ces quatre possibilités (ou les « vrais » vœux B, D, A, E, C) mais peut modifier l’affectation d’autres candidats.