A.P.B. : La vie après le bac

2016-10-17T13:21:37Z

A.P.B. : La vie après le Bac.

Cet article a été co-rédigé par Clémence Réda, étudiante à l'ENS Cachan en collaboration avec le blog Binaire.

D'un côté, quelques mois avant l'examen du bac, les lycéens postent sur le site d'Admission Post-Bac la liste de leurs choix d'enseignement supérieur, dans l'ordre de préférence, et limitée à une quarantaine de possibilités ; ce qui représente plusieurs centaines de milliers de listes. De l'autre, les différentes formations indiquent le nombre de places disponibles, ainsi que les conditions d'admission ; plus de dix mille d'entre elles transmettent ces informations au site. Le jour J arrivé, la moulinette (un algorithme) tâchera d'affecter les élèves aux formations, en satisfaisant « au mieux » les attentes de chaque partie. Nous avons donc délégué cette tâche des plus importantes, qui ne décide de rien de moins que de l'avenir de nos propres enfants, à un simple algorithme. Mais pas de panique !

Avant tout, évitons-le : « C'était mieux avant »

Avant, sans outil de centralisation, il était indispensable de fouiller les recoins des sites des diverses possibilités post-bac, afin d'en extraire les modalités d'une candidature, qui étaient évidemment loin d'être similaires d'une formation à l'autre.

Avant, les élèves étaient encore plus mal informés.
Avant, les « on-dit » précipitaient déjà des bataillons d'élèves vers quelques formations prestige ou à la mode.

L'appréhension que ressentait un élève d'hier, vis-à-vis des retours de ses multiples candidatures, vaut bien celle de celui qui, aujourd'hui, attend la réponse d'un algorithme. Les dilemmes d'aujourd'hui, pour spécifier l'ordre de la liste des préférences, ne sont pas plus cornéliens que ceux d'hier, qui précédaient un choix entre plusieurs offres.

Traité par des administrations débordées, ou par un programme informatique, le problème est délicat, et on peut évidemment comprendre l'énorme frustration de l'élève qui a candidaté pour la formation de ses rêves, et qui s'en trouve exclu par un simple tirage au sort. Mais la faute ne doit pas être imputée à l'algorithme lui-même. Elle vient d'un choix sociétal de privilégier des filières pour le supérieur non sélectives, où le nombre de candidats dépasse parfois largement celui des places disponibles. À défaut de réelle sélection, on laisse le hasard décider, que ce soit via un algorithme, ou une personne qui joue à pile ou face.

Les avantages de l'algorithme

De plus, si la procédure est émaillée de maladresses qui pourraient être évitées, l'utilisation d'un algorithme présente des avantages. Avec l'aide de l'informatique, la méthode d'affectation est bien plus efficace, en temps, et en ressources techniques et humaines. Nous verrons d'ailleurs que, d'un point de vue purement algorithmique, le problème est relativement simple. Il est même possible de garantir que l'affectation soit « optimale », c'est-à-dire qu'elle satisfasse un maximum de contraintes parmi celles données par à la fois les élèves et les formations, ce qu'une méthode « à la main » ne permettait pas au bon vieux temps.

Surtout, il est possible d'aussi garantir l'équité des affectations, de ne pas favoriser ou défavoriser un élève en se basant sur son origine ethnique, son genre, etc. Nous n'avons plus besoin de devoir nous fier à la conscience morale des jurys : l'algorithme ne se réfère qu'au code qui l'implémente, au programme explicitement écrit, aux règles et non à des interprétations plus ou moins osées.

La difficulté n'est pas tant de trouver un algorithme efficace, que de définir les règles propres à la sélection de candidats. Leur choix est avant tout sociétal.

Est-ce que nous voulons, par exemple, que les candidates soient exclues des filières scientifiques ? Est-ce que nous considérons que les sciences fondamentales ou expérimentales ne leur sont pas destinées ? Ou voulons-nous, au contraire, appuyer la candidature des jeunes filles, plutôt que celles de leurs camarades masculins avec des dossiers sensiblement proches, dans les formations scientifiques de prestige, pour essayer de rattraper le déséquilibre actuel ? Ou encore, souhaitons-nous que l'algorithme ne prenne pas en compte le genre ? Toutes ces règles peuvent être incluses dans l'algorithme (mais pas en même temps). La difficulté est de choisir !

Le principal problème d'A.P.B. est son opacité !

@Maev59

La confiance, dans les règles régissant ce processus d'affectation, est essentielle. Les règles adoptées doivent pouvoir être discutées, contestées, approuvées. Mais comment les approuver, comment les contester, comment les discuter, si elles restent confidentielles ?

On connaît les arguments : le code est trop complexe pour être montré ; s'il est connu, les élèves tenteront de contourner le système. Mais aucun n'est vraiment solide. D'ailleurs, le gouvernement a annoncé que les textes qui spécifient l'algorithme en question seraient publiés : « Nous allons donc dévoiler l'un des secrets défense les mieux gardés : l'algorithme d'A.P.B. ! », a affirmé Thierry Mandon, avec un certain humour. Pour nous, il ne suffit pas d'en dévoiler les grandes lignes, que les spécialistes connaissent déjà plus ou moins. Il faut mettre le programme informatique sur la place publique, pour qu'il puisse être débattu, peut-être corrigé, afin que la société l'accepte.

Le gouvernement ouvert

De manière générale, les gouvernements, les administrations, s'appuient de plus en plus sur des algorithmes, qui prennent ainsi une place de plus en plus grande dans notre vie quotidienne. Leur but est d'améliorer le fonctionnement des institutions. Néanmoins, les algorithmes ne décideront jamais à notre place : c'est bien nous qui choisirons les règles qui les déterminent. Il faut bien garder à l'esprit que les choix effectués par un algorithme sont à l'origine implémentés, programmés, écrits, par des humains. Dans une approche « ouverte » du gouvernement (ou de la démocratie), le fonctionnement précis des logiciels qui nous gouvernent n'a pas à être secret. Et effectivement, le Projet de Loi sur la République numérique inclut un article créant « un droit d'accès aux règles définissant les traitements algorithmiques utilisés par les administrations publiques et aux principales caractéristiques de leur mise en œuvre, lorsque ces traitements débouchent sur des décisions individuelles ».

Il faut encore aller plus loin ! Nous devrions aussi pouvoir consulter les entrailles des logiciels, au niveau de l'algorithme même, pour pouvoir vérifier les règles sur lesquelles ils prétendent se fonder, et aussi pour pouvoir discuter d'éventuelles modifications. Ceci est nécessaire si nous voulons qu'une réelle confiance règne entre toutes les parties concernées, entre les institutions et les individus.

Il y a toujours un aspect un peu magique dans l'utilisation d'un algorithme dont on n'a pas le début d'une idée quant à son fonctionnement. Pour conclure cet article, nous voudrions vous convaincre qu'un tel algorithme n'a pas besoin d'être super compliqué. Laissez-nous vous expliquer la démarche générale pour résoudre un « problème d'affectation ». Ce problème est également connu sous le nom de « problème des mariages stables », c'est bien d'A.P.B. dont il s'agit.

L'algorithme de Gale-Shapley (1962)

@Maev59

Lloyd Shappley a obtenu le Prix Nobel d'Économie en 2012 pour ses recherches sur la théorie des jeux collaboratifs, et ses travaux sur… les mariages stables. La question des mariages stables en informatique, loin d'être une affaire de mœurs plus ou moins libres, intervient assez régulièrement dans des domaines divers de notre vie quotidienne, d'Admission Post Bac aux sites de rencontres amoureuses par exemple. Le point commun est de former de façon optimale, c'est-à-dire en essayant de satisfaire au mieux les participants, des couples d'éléments de deux groupes distincts d'individus ou d'entités.

En l'occurrence, pour Admission Post Bac, nous chercherons à apparier futurs bacheliers et établissements de l'enseignement supérieur. Pour l'optimalité dans un mariage, il s'agit, par tradition, d'éviter que l'un des partenaires n'ailler chercher son bonheur ailleurs ; il faudra donc s'assurer notamment qu'il n'existe pas deux lycéens associés à deux formations distinctes qui auraient pu échanger leurs affectations pour aboutir à plus de satisfaction pour tous.

Imaginez-vous quelques instants être devenu l'incarnation humaine d'A.P.B. (oui, oui). Vous êtes chargé d'affecter un petit groupe de lycéens, Alice, Bob et Charlie, à un ensemble de formations post-bac, intitulées sobrement A, B et C. On supposera ici que A, B et C n'acceptent qu'un seul étudiant dans leur établissement. Vous connaissez les préférences des participants pour pouvoir réaliser l'affectation.

Pensons d'abord à une méthode naïve : vous affectez les lycéens à des formations au hasard. Supposons que vous ayez affecté Alice en A, Bob en B, et Charlie en C. Il se peut très bien que Charlie ait un dossier qui convient mieux à la formation A, et que Charlie lui-même ne rêve que d'aller dans cet établissement. Autrement dit, il existe deux couples lycéens/formations tels que la formation dans le premier couple préférait le lycéen du deuxième couple, et que réciproquement, ce dernier avait placé plus haut dans ses choix l'établissement du premier couple, par rapport à celui où il se trouve actuellement. C'est un mariage instable, et donc non optimal. Vous avez fait un travail de cochon et il y a de grandes chances pour qu'on se passe de vos services l'année prochaine.

La lourde tâche vous revient donc de « marier » de façon optimale, donc sans cas d'instabilité comme vu précédemment, formations et lycéens.
Commençons par Alice : sa liste indique qu'elle voudrait entrer d'abord en A, sinon en C, sinon en B. Pour l'instant, nous n'avons pas plus d'informations. Puisque tel est le souhait d'Alice, pour le moment nous allons l'associer à la formation A – c'est-à-dire que nous l'affecterons à la formation A si nous ne trouvons pas de meilleure configuration.

Passons à la liste de Bob, qui, lui, voudrait aller d'abord en C, sinon en B, sinon en A. La formation C n'étant affectée à personne pour le moment, nous faisons comme pour Alice : nous associons Bob à C, faute de mieux.

Enfin, Charlie indique sur sa liste qu'il préférerait aller d'abord en C, sinon en A, sinon en B. Vous pourriez affecter Charlie à la dernière formation restante, c'est-à-dire B. Mais, si la formation C avait placé Charlie avant Bob dans son classement ? (Il fallait bien que les classements des formations interviennent quelque part. Quand même.) Vous retomberiez alors sur la situation décrite dans le paragraphe précédent, que vous voulez à tout prix éviter.

Ainsi, dans le cas où la formation C a classé Charlie avant Bob, la meilleure configuration rompt le couple Bob/C, et préfère associer Charlie à C. Finalement, comme il n'y a pas d'autre meilleure configuration et que tous les lycéens ont été affectés à une formation, les couples associés sont alors définitifs. Vous obtenez un mariage stable. Victoire !