L'Algorithme d'optimalisation des préférences

  Le texte explicatif qui suit se comprend en lisant le tableau suivant (.xlsx).

La CoGI commence par classer les élèves dans chacune des écoles qu’elle traite.
 
Dans chaque école considérée, selon l’ordre issu du classement, elle commence par attribuer éventuellement des places aux ISEF manquants et aux prioritaires dont la priorité n’aurait pas pu être satisfaite dans le cadre des 80 % de places que les écoles réputées complètes attribuent.
 
Ensuite, la CoGI procède à l’optimalisation des préférences comme telle. Cette dernière se fait selon un algorithme utilisé dans plusieurs pays ou villes confrontés à une tension entre la demande d’inscriptions et l’offre de places. Cet algorithme vise à rapprocher chacun de sa meilleure préférence, sans jamais porter préjudice à quiconque par rapport à son classement.
 
De manière imagée, on peut dire que la CoGI se trouve face à un grand tableau avec des boutons lumineux où :

• chaque colonne représente une école traitée par la CoGI. Les colonnes représentent donc les écoles complètes qui ont réservé 22 % des places et les écoles incomplètes où la CoGI pourra ajouter des élèves sur la base des préférences exprimées dans le volet confidentiel du formulaire ;
• les élèves sont classés dans un maximum de 10 écoles (colonnes) sur la base de leur indice composite et d’un départage des ex-æquo ; dans chaque école (colonne), chaque élève porte la mention de sa préférence (de 1 à 10). Chaque préférence est codifiée par une couleur : 1^re préférence = bleu, 2^e préférence = jaune vif, 3^e préférence = jaune clair ;
• dans chaque école (colonne), il y a une ligne de « démarcation » entre l’ordre utile (OU) et la liste d’attente (LA). Attention, dans chaque école (colonne), la ligne de démarcation ne se trouve pas à la même hauteur, elle dépend du nombre de places restées disponibles dans la « petite école » concernée.

Avec ce tableau, où chaque bouton de couleur représente un choix d’élève, la CoGI procède par étapes, en partant d’un état initial où tous les boutons sont en « veilleuse ». L’état de veille est symbolisé par la couleur correspondant à la préférence et sur laquelle apparaît le N° de l’élève et son ordre de préférence en italique noir justifié à gauche.
 
La CoGI commence par traiter les 1^res préférences. Pour cela, on peut imaginer que dans le tableau lumineux, on « active » (= ON, symbolisé par le N° de l’élève et sa préférence en noir gras justifié à droite) toutes les 1^res préférences jusqu’à la ligne de démarcation OU-LA. S’il y a 7 places dans la petite école, quand on traite les 1^res préférences, la ligne de démarcation se trouve provisoirement juste après le 7^e élève pour lequel cette école constitue la 1^re préférence. S’il y en a moins que sept, la ligne de démarcation se situe en dessous du dernier élève dont c’est la 1^re préférence. Toutes les autres préférences sont maintenues en veilleuse, strictement à leur place dans le tableau. Ne restent donc « ON » que les boutons correspondant à la 1^re préférence situés au-dessus de la ligne de démarcation provisoire. Les 1^res préférences situées en dessous de la ligne de démarcation OU-LA provisoire, sont également en veilleuse. On sait déjà que la 1^re préférence de ces élèves ne pourra être satisfaite, car au mieux on pourra satisfaire toutes les 1^res préférences qui se situent au dessus de la ligne de démarcation provisoire.
 
Pour chaque élève dont la 1^re préférence se trouve au-dessus de la ligne de démarcation provisoire « OU-LA », on va provisoirement systématiquement masquer (= OFF se traduit par le remplacement du fond de couleur par un fond blanc) tous les boutons de 2^e, 3^e, ….jusqu’éventuellement de 10^e préférence, qu’ils soient en OU ou en LA, tout en les maintenant strictement à leur place dans le tableau. Les boutons blancs ne comptent provisoirement plus, mais pourraient être remis en veilleuse ou réactivés ultérieurement.
 
Par définition toutes les 1^res préférences au-dessus de la ligne de démarcation sont provisoirement en OU, mais le traitement des autres préférences restées en place (veilleuse ou OFF) va en faire repasser certains en LA.
 
La CoGI passe ensuite aux 2^e préférences. Pour cela, on peut imaginer que dans le tableau lumineux, on « active » (= ON) toutes les 2^e préférences des élèves dont la 1^re préférence n’a pas pu être satisfaite et ce jusqu’à la nouvelle ligne de démarcation OU-LA. S’il y a 7 places dans la petite école, quand on traite les 2^e préférences, la nouvelle ligne de démarcation se trouve juste après le 7^e élève pour lequel cette école constitue la 1^re préférence ou la 2^e préférence d’un élève dont la 1^re n’a pas pu être satisfaite. S’il y en a moins que sept, la ligne de démarcation se situe en dessous du dernier élève dont c’est la 1^re ou la 2^e préférence. Toutes les autres préférences sont maintenues en veilleuse, strictement à leur place dans le tableau. Ne restent donc « ON » que les boutons correspondant à la 1^re ou 2^e préférence situés au-dessus de la nouvelle ligne de démarcation provisoire. Les 1^res et 2^e préférences situées en dessous de la nouvelle ligne de démarcation OU-LA provisoire, sont également en veilleuse. On sait déjà que, selon le cas, la 1^re préférence ou la 2^e préférence de ces élèves ne pourra être satisfaire, car au mieux on pourra satisfaire toutes les celles qui sont « ON » au dessus de la ligne de démarcation provisoire.
 
Attention, la mise en « ON » de 2^e préférences situées au-dessus ou entre des 1^res préférences provisoirement en OU, va, dans certains cas, faire repasser en mode veilleuse des 1^res préférences au-delà de la nouvelle ligne de démarcation. Pour les repérer, il faut ajuster la ligne de démarcation. Pour ces élèves passés, dans leur 1^re préférence, de l’état « ON » à l’état « veilleuse », il est nécessaire de remettre les autres préférences en mode « veilleuse ».
 
Pour chaque élève dont la 2^e préférence se trouve au-dessus de la ligne de démarcation provisoire « OU-LA », on va provisoirement mettre en « OFF » tous les boutons de 3^e, 4^e, ….jusqu’éventuellement de 10^e préférence, qu’ils soient en OU ou en LA, tout en les maintenant strictement à leur place dans le tableau. Les boutons blancs ne comptent provisoirement plus, mais pourraient être remis en veilleuse ou réactivés ultérieurement.
 
Par définition toutes les 1^res et 2^e préférences au-dessus de la ligne de démarcation sont provisoirement en OU, mais le traitement des autres préférences restées en place (veilleuse ou OFF) va en faire repasser certains en LA.
 
La CoGI passe ensuite aux 3^e préférences. Pour cela, on peut imaginer que dans le tableau lumineux, on « active » (= ON) toutes les 3^e préférences des élèves dont ni la 1^re préférence, ni la 2^e préférence n’ont pu être satisfaites et ce jusqu’à la nouvelle ligne de démarcation OU-LA. S’il y a 7 places dans la petite école, quand on traite les 3^e préférences, la nouvelle ligne de démarcation se trouve juste après le 7^e élève pour lequel cette école constitue la 1^re , la 2^e ou la 3^e préférence d’un élève dont la 1^re ou la 2^e n’ont pas pu être satisfaites. S’il y en a moins que sept, la ligne de démarcation se situe en dessous du dernier élève dont c’est la 1^re, la 2^e, ou la 3^e préférence. Toutes les autres préférences sont maintenues en veilleuse, strictement à leur place dans le tableau. Ne restent donc « ON » que les boutons correspondant à la 1^re, 2^e ou 3^e préférence situés au-dessus de la nouvelle ligne de démarcation provisoire. Les 1^res, 2^e et 3^e préférences situées en dessous de la nouvelle ligne de démarcation OU-LA provisoire, sont également en veilleuse. On sait déjà que, selon le cas, la 1^re, la 2^e ou la 3^e préférence de ces élèves ne pourra être satisfaire, car au mieux on pourra satisfaire toutes les celles qui sont « ON » au dessus de la ligne de démarcation provisoire.
 
Attention, la mise en « ON » de 3^e préférences situées au-dessus ou entre des 1^res ou des 2^e préférences provisoirement en OU, va, dans certains cas, faire repasser en mode veilleuse des 1^res ou 2^e préférences au-delà de la nouvelle ligne de démarcation. Pour les repérer, il faut ajuster la ligne de démarcation. Pour ces élèves passés, dans leur 1^re ou leur 2^e préférence, de l’état « ON » à l’état « veilleuse », il est nécessaire de remettre les autres préférences en mode « veilleuse ».
 
Pour chaque élève dont la 3^e préférence se trouve au-dessus de la ligne de démarcation provisoire « OU-LA », on va provisoirement mettre en « OFF » tous les boutons de 4^e, 5^e, ….jusqu’éventuellement de 10^e préférence, qu’ils soient en OU ou en LA, tout en les maintenant strictement à leur place dans le tableau. Les boutons blancs ne comptent provisoirement plus, mais pourraient être remis en veilleuse ou réactivés ultérieurement.
 
Par définition toutes les 1^res, 2^e et 3^e préférences au-dessus de la ligne de démarcation sont provisoirement en OU, mais le traitement des autres préférences restées en place (veilleuse ou OFF) va en faire repasser certains en LA.
 
… Et ainsi de suite, si nécessaire, jusqu’aux 10^e préférences.
 
Cette procédure est connue dans la littérature sous le nom de AAD-élève (algorithme d'allocation différée avec préférence aux élèves).