Le problème de la coordination
Petit schéma des épisodes précédents : si les universités peuvent recruter à n'importe quel moment en France (postes dits « au fil de l'eau »), la plupart concentrent cette activité dans le cadre d'une campagne synchronisée, c'est-à-dire maintenant. Les postes sont donc publiés sur un serveur hébergé par le Ministère de l'enseignement supérieur et de la recherche (GALAXIE pour les intimes). Vous envoyez un dossier (papier ou électronique, c'est selon) sur tous les postes correspondant à votre profil. Cela, c'est courant mars.
Les universités réunissent ensuite les commissions de recrutement pour décider parmi les dossiers reçus quels candidats ils vont auditionner. Si certaines ont la bonne idée de préciser assez rapidement quel sera la date de la commission et celle des auditions, la plupart ne le font pas, ce qui rend un brin stressant le mois de mai pour les candidats. Vous recevez ensuite un mail, soit émanant de l'université elle-même (en général bon signe) ou de GALAXIE (plutôt mauvais signe) indiquant si et quand vous êtes convoqué pour une audition.
Les auditions étant rassemblées sur une période de deux semaines, il suffit de peu d'auditions pour en avoir deux (ou plus) le même jour, au point qu'il est souvent impossible de se rendre au deux et qu'il faut le plus souvent choisir a priori.
Le problème de l'allocation
Une fois les auditions passées, les commissions établissent pour chaque poste un classement des candidats. Ce classement est ensuite validé (ou non, mais c'est rare) par le Conseil d'administration de l'université concernée. Dans le cadre de la procédure synchronisée, si j'ai bien compris, les candidats peuvent alors, sur GALAXIE, donner leur ordre de préférence entre les universités qui les ont classés. Ils sont alors alloués en fonction des appariement compatibles
Pour les théoriciens, cela fait furieusement penser à une procédure de Gale-Shapley (tiens, pas d'article sur la Wikipédia francophone, ou il manque un interwiki), avec les université dans le rôle des hommes et les candidats dans le rôle des femmes (en suivant la présentation habituelle du problème). Il semble me souvenir qu'il est possible de prouver que parmi les allocations stables (il n'existe pas de paire de candidats prêts à échanger leurs places et que les universités soient d'accord), celle résultat de cette division des rôle est optimale pour les universités (elles ont le meilleur candidat que leur permet un arrangement stable) mais pessimal pour les candidats)
Je n'ai pas le temps de regarder cela en détail, mais :
- La procédure d'allocation des candidats correspond-elle bien à celle de Gale-Shapley ? Il ne me semble pas évident que l'expression directe de l'ordre de préférence des candidats soit équivalent à l'acceptation provisoire de l'algorithme de référence.
- Est-ce que je raconte n'importe quoi sur l'optimalité de l'allocation ?
7 réactions
1 De Pierre - 12/05/2011, 17:40
Mon intuition est que la question ne se pose pas vraiment: tout est réglé avant la procédure électronique. Quand bien même, les cas où plusieurs équilibres sont possibles sont probablement rarissimes.
(J'entends par là: en répétant la procédure "on supprime les cas où un premier choix de fac matche un premier choix de candidat, la fac et le candidat concerné des listes; et on recommence tant que c'est possible", on doit allouer le plus souvent tous les candidats)
2 De alexandre - 12/05/2011, 20:26
Mathieu,
Tel que tu décris le système, on ne sait rien de l'algorithme. On sait simplement que les deux côtés soumettent une liste de préférences, et que le mécanisme sélectionne un matching stable.
Si, comme tu le penses, l'algorithme fait jouer aux universités le rôle des hommes, alors en effet on aboutira au meilleur matching pour les universités et au pire pour les candidats.
Concernant la remarque de Pierre, le matching stable n'est pas unique en théorie. Le cas décrit (on retire successivement les paires qui se classent 1ères) produit une unique solution si par exemple tous les candidats sont d'accords sur les classements des universités, ou vice-versa (et c'est alors le seul matching stable).
Bon courage pour tes auditions!
3 De Mathieu P. - 12/05/2011, 21:40
J'ai trouvé une partie de la documentation dans l'aide de GALAXIE (ce n'était pas évident) : si on est classé sur plusieurs postes, il faut mettre son vrai ordre de préférence. L'application va attendre de savoir où est affecté le candidat classé premier sur mon poste favori. S'il n'est pas affecté sur ce poste, l'application regarde ce qu'à fait le second, etc., jusqu'à arriver éventuellement jusqu'à moi. Ils précisent également que si j'ai été classé premier quelque part, je suis sûr d'avoir au pire ce poste, du moment que je le classe dans ma liste de préférences. Il me semble qu'on n'a pas là toutes les informations nécessaires, en particulier comment ils bootsrappent le mécanisme.
4 De alexandre - 12/05/2011, 22:53
Dans ce cas ça a plutôt l'air d'être favorable aux candidats. Dans Gale-Shapley, révéler ses préférences est une stratégie dominante pour les hommes. J'ose espérer que s'ils conseillent aux gens d'être sincères c'est que c'est vraiment dans leur intérêt...
5 De Pierre - 13/05/2011, 11:11
Alexandre: J'en étais totalement conscient. Mais je me permettrai cependant d'émettre une conjoncture avec d'autant plus de confiance qu'elle est probablement invérifiable: "Dans galaxie, les préférences des différents candidats et sont suffisamment corrélées entre elles et les préférences des différentes universités sont suffisamment corrélées entre elles pour qu'il n'existe quasiment toujours qu'un unique équilibre".
Par ailleurs:
- Je ne vois pas dans ce que dit Mathieu quoi que ce soit (de factuel) qui informe sur l'allocation dans les cas où il existe plusieurs équilibres.
- S'il n'existe qu'un seul équilibre, les candidats ont intérêt à donner leurs vraies préférences (dites moi si je me trompe, mais ça me semble logique). Ca doit même pouvoir mettre la pagaille si on ne donne pas ses préférences.
- Il est très difficile d'avoir l'information sur l'existence de plusieurs équilibres, quand bien-même ces équilibres se limiteraient à un sous-ensemble de 3 candidats et 3 postes. (moins sûr ceci dit, car l'info circule). Dans ce cas, les universités ne pourront pas manipuler leurs préférences (fixées le jour des auditions), les candidats le pourront s'ils ont l'info.
- Sauf cas si il y a une info très précise, ne pas donner ses vraies préférences me semble être un jeu à haut risque...
6 De jean - 20/05/2011, 13:53
Il ya quelques années, Michel Balinski avait écrit un article dans Pour la Science dans lequel il affirmait que l'affectation des candidats se faisait selon un Gale-Shapley favorisant les universités. S'en était suivi une réponse vigoureuse du ministère affirmant que l'algorithme utilisé était équivalent à un GS favorisant les candidats.
Voilà deux liens à ce sujets:
http://cat.inist.fr/?aModele=affich...
http://ideas.repec.org/p/ner/dauphi...
7 De LDB - 27/05/2011, 13:59
Billet très intéressant et stimulant.
Il y a eu un papier dans la revue économique en 2009 qui montre effectivement que la procédure d'affectation finale correspond à l'algorithme de Gale et Shapley (Haeringer et Iehlé, 2009) et des travaux très connus de Roth et Niederlé sur différents marchés des emplois aux USA, assorties d'études empiriques et expérimentales.
Il me semble que le concours actuel de MCF est un mécanisme qui revient in fine à un Gale Shapley dans lequel les universités proposent et les candidats acceptent ou rejettent (puisque les universités classent les candidats et que ceux ci peuvent accepter ou refuser), ce qui est favorable aux universités d'un point de vue théorique (mais je ne suis pas un spécialiste). On peut néanmoins dire que en premier lieu, les candidats proposent, les universités rejettent ou acceptent, puis proposent (un ordre) et à la fin les candidats acceptent ou rejettent. Donc en fait c'est encore un peu plus compliqué, et je ne suis donc pas sur de ma réponse théorique . Toutefois la procédure d'appariement centralisée garantit la stabilité des appariements et est bien supérieure à toute procédure asynchrone et décentralisée d'affectation des postes.