Claire Mathieu est une femme très intelligente et qui connaît très bien ces problèmes. J'ai été très déçu qu'elle participe à la caution de l'algorithme de Parcoursup. Parce que l'algorithme de Parcoursup ressemble de loin dans le brouillard à l'algorithme de Gale-Shapley, sauf que pas du tout. Il manque en effet une hypothèse extrêmement forte qui est que l'information des classements de part et d'autre est connue. C'était le cas dans APB, ce qui fait que dès le premier tour, la quasi totalité des étudiants avait une affectation. Ce n'est plus le cas avec Parcoursup puisque les candidats ne font plus de classement des formations (ce classement est uniquement dans leur tête) et on peut se retrouver avec des interblocages.
Par exemple, si un étudiant A a dans l'idée d'aller à X puis Y, et qu'un étudiant B veut aller à Y puis X, et que X a classé B avant A, et que Y a classé A avant B, on se retrouve avec un blocage. Parce que l'algo va proposer à A d'aller à Y et à B d'aller à X. Ils vont tous les deux dire "OK mais j'attends mieux" et ça ne libère pas une place et donc, l'autre ne peut pas avoir cette place. Au final, ils ont les deux leur deuxième choix alors qu'ils attendaient leur premier choix. Avec APB, et la connaissance complète, ils auraient eu leur premier choix.
[^] # Re: Analyse statique
Posté par rewind (Mastodon) . En réponse à la dépêche Audit du code source de Parcoursup par la Cour des comptes. Évalué à 3.
Claire Mathieu est une femme très intelligente et qui connaît très bien ces problèmes. J'ai été très déçu qu'elle participe à la caution de l'algorithme de Parcoursup. Parce que l'algorithme de Parcoursup ressemble de loin dans le brouillard à l'algorithme de Gale-Shapley, sauf que pas du tout. Il manque en effet une hypothèse extrêmement forte qui est que l'information des classements de part et d'autre est connue. C'était le cas dans APB, ce qui fait que dès le premier tour, la quasi totalité des étudiants avait une affectation. Ce n'est plus le cas avec Parcoursup puisque les candidats ne font plus de classement des formations (ce classement est uniquement dans leur tête) et on peut se retrouver avec des interblocages.
Par exemple, si un étudiant A a dans l'idée d'aller à X puis Y, et qu'un étudiant B veut aller à Y puis X, et que X a classé B avant A, et que Y a classé A avant B, on se retrouve avec un blocage. Parce que l'algo va proposer à A d'aller à Y et à B d'aller à X. Ils vont tous les deux dire "OK mais j'attends mieux" et ça ne libère pas une place et donc, l'autre ne peut pas avoir cette place. Au final, ils ont les deux leur deuxième choix alors qu'ils attendaient leur premier choix. Avec APB, et la connaissance complète, ils auraient eu leur premier choix.