Utilisateur:Durandem/Brouillon

• Gérer mon brouillon
• Demander une relecture (voir les demandes)
• Publier mon brouillon

Cette page est un brouillon appartenant à Durandem

Conseils de rédaction

• → N'hésitez pas à publier sur le brouillon un texte inachevé et à le modifier autant que vous le souhaitez.
• → Pour enregistrer vos modifications au brouillon, il est nécessaire de cliquer sur le bouton bleu : « Publier les modifications ». Il n'y a pas d'enregistrement automatique.

Si votre but est de publier un nouvel article, votre brouillon doit respecter les points suivants :

• Respectez le droit d'auteur en créant un texte spécialement pour Wikipédia en français (pas de copier-coller venu d'ailleurs).
• Indiquez les éléments démontrant la notoriété du sujet (aide).
• Liez chaque fait présenté à une source de qualité (quelles sources  – comment les insérer).
• Utilisez un ton neutre, qui ne soit ni orienté ni publicitaire (aide).
• Veillez également à structurer votre article, de manière à ce qu'il soit conforme aux autres pages de l'encyclopédie (structurer – mettre en page).

• → Si ces points sont respectés, pour transformer votre brouillon en article, utilisez le bouton « publier le brouillon » en haut à droite. Votre brouillon sera alors transféré dans l'espace encyclopédique.

Algorithme d'affectation de candidats après concours multiples

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 filières différentes. Les filières possèdent chacune un nombre de places qui est généralement limité. Les étudiants ont passé des concours et ont donc obtenu chacun un rang de classement dans chacune des filières (un concours par filière). Les étudiants vont devoir exprimer un choix et donc classer chacun 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ère 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 bien classé dans une filière (mais en préférant une autre) aurait tendance à la choisir plutôt que celle qui a sa préférence pour éviter de lâcher la proie pour l’ombre.

Ce problème c’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 des mariages hétérosexuels). 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 aequo). L’algorithme va ensuite permettre d’obtenir 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 marie à 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)

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 classement 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ème en médecine et affecté à la dernière (100ème) place disponible en médecine mais il préférerait pharmacie (où il est classé 151ème).
• l’étudiant B est classé 150ème en pharmacie et affecté à la dernière (100ème) place disponible en pharmacie mais il préférerait médecine (où il est classé 151ème).

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 filières 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 filières, 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 que A est mieux classé que B dans cette filière ou affecté dans une autre filière qu’il préfère.

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 jeux d’affectations dans d’autres filières), il s 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.