La vidéo du jour est un peu particulière. Je ne pensais pas avoir grand chose à dire sur le sujet…et pourtant elle fait 39 minutes !
On y parle de Parcoursup et plus généralement des procédures d’appariement qui existent notamment pour l’attribution des places dans l’enseignement supérieur, et ce dans de nombreux pays.
Tout d’abord, il me faut remercier 3 personnes avec qui j’ai eu le plaisir de discuter pour me documenter : Marc De Falco, Judicaël Courant et Julien Grenet.
D’ailleurs avant d’aborder quelques compléments sur les aspects scientifiques, voici quelques références sur les questions des procédures existantes, notamment en France avec APB et Parcoursup.
- Le rapport du Comité Ethique et Scientifique de Parcoursup : un rapport de 160 pages remis au parlement pour analyser la première année de fonctionnement de Parcoursup. Julien Grenet, Professeur à l’Ecole d’Economie de Paris y a notamment contribué.
- De façon générale, le site de Julien Grenet contient nombre de ses contributions au débat public sur la question. Je vous recommande en particulier cette série de diapos faisant une revue du sujet;
- Le site Matching in Practice, du « European network for research on matching practices in education and related markets », qui recense les pratiques d’appariement dans les différents pays, avec souvent un détail des procédures utilisées.
- Une présentation de Judicaël Courant
- Les articles du blog Ingénu Ingénieur, ainsi que ce fil Twitter de son auteur, Guillaume Ouattara.
Quelques compléments sur les questions scientifiques et académiques
Commençons d’abord par mentionner la source fondatrice, l’article de Gale et Shapley en 1962.
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
De façon assez étonnante, cet article est très court, et ne contient aucune équation, et même aucune bibliographie ! Les auteurs s’en amusent d’ailleurs en conclusion. Cet article aura quand même été à l’origine d’un champ de recherche qui aura valu à Lloyd Shapley le prix Nobel en 2012 ! David Gale était déjà décédé, mais le prix fut conjointement attribué à Alvin Roth, un autre chercheur qui a joué un rôle crucial dans le développement de ces travaux (comme nous le verrons plus loin).
De façon plus générale, ce domaine de recherche se connecte de près avec la théorie des jeux, notamment via les notions d’équilibre de Nash (un acteur peut-il améliorer sa position de façon unilatérale ?) et d’optimum de Pareto. Ce point est notamment plus subtil que ce que j’ai laissé sous-entendre dans la vidéo.
J’ai fait comme s’il y avait une notion naturelle de « meilleure solution », mais nous sommes dans un cas où l’on essaye d’optimiser simultanément la situation de plusieurs acteurs. Il faut donc raisonner du point de vues des optimums de Pareto. On dit qu’une configuration « Pareto-domine » une autre si elle est meilleure (ou équivalente) pour tous les acteurs. Donc en passant à la configuration dominante, on ne dégrade la situation de personne.
Une configuration est « Pareto-optimale » si elle n’est dominée par aucune autre. A priori, il peut exister plein de situations Pareto-optimales, et rien a priori ne permet de favoriser l’une sur l’autre. C’est le concept de frontière de Pareto.
Ce qu’il y a de remarquable avec l’algorithme de Gale-Shapley, c’est que pour les proposants, la solution trouvée Pareto-domine toutes les autres solutions stables. C’est donc la seule solution stable sur la frontière de Pareto. Ce qui est assez incroyable je trouve !
Malgré tout, comme je l’explique dans la vidéo, il existe potentiellement des solutions qui Pareto-dominent la solution de Gale-Shapley, mais ne sont pas stables.
Concernant les liens avec la théorie des jeux, j’ai expliqué que la procédure de GS n’est pas manipulable (pour les proposants). C’est-à-dire qu’aucun acteur ne peut améliorer sa situation en mentant sur ses préférences réelles. J’ai sous-entendu que c’était lié à l’idée d’optimalité, mais c’est un peu plus compliqué que ça.
Il a fallu attendre 1981 et l’article
Dubins, L. E., & Freedman, D. A. (1981). Machiavelli and the Gale-Shapley algorithm. The American Mathematical Monthly, 88(7), 485-494.
puis 1982 et l’article d’Alvin Roth
Roth, A. E. (1982). The economics of matching: Stability and incentives. Mathematics of operations research, 7(4), 617-628.
pour démontrer plusieurs choses :
- la procédure n’est pas manipulable par les proposants;
- elle ne l’est même pas en cas de coalition de proposants qui essayent collectivement d’améliorer leur sort;
- en revanche elle est manipulable par les « disposants », mais c’est particulièrement compliqué car cela nécessite de connaitre les préférences des autres.
- toutefois Roth a démontré qu’il n’existe aucune procédure qui serait à la fois stable, et non-manipulable par les deux camps.
Concernant la procédure des cycles d’échange optimaux, elle a été dévelopée par Gale, et publiée par Shapley et H.Scarf
Shapley, L., & Scarf, H. (1974). On cores and inpisibility. Journal of mathematical economics, 1(1), 23-37.
Cet algorithme est le « complémentaire » de GS, en ce sens qu’il est également non-manipulable, et qu’il fournit une solution Pareto-optimale mais sans garantie de stabilité. Il est notamment utilisé pour l’allocation des dons de reins quand on cherche à apparier des donneur et des receveurs.
Parmi les références académiques importantes, on peut aussi citer
Abdulkadiroğlu, A., & Sönmez, T. (2003). School choice: A mechanism design approach. American economic review, 93(3), 729-747.
qui aborde notamment la question des attributions de place dans les écoles primaires. Le problème est un peu différent car les écoles ne sont pas censées sélectionner leurs écoliers sur la base de « préférences », mais elles peuvent en revanche appliquer des règles de priorité pour refléter des choix politiques : rapprocher les enfants d’une même famille, favoriser les boursiers, etc. C’est notamment un mécanisme de ce type qui est utilisé pour la procédure Affelnet, qui est le pendant de Parcoursup pour le lycée.
Un autre résultat intéressant : il est fréquent que certains internes en médecine soient mariés (aux USA, mais aussi ailleurs…), ce qui complique la procédure d’affectation car on a alors deux étudiant(e)s dont les préférences sont interdépendantes. La valeur que l’un(e) ou l’autre attribuera à un hôpital dépendra fortement de la proximité avec son/sa conjoint(e). Et dans ce cas où il peut exister des préférences couplées, on perd la propriété de stabilité !
Klaus, B., & Klijn, F. (2005). Stable matchings and preferences of couples. Journal of Economic Theory, 121(1), 75-106.
Un point concernant les temps de calcul, et notamment le fait qu’APB ne prenne que quelques minutes : je tiens l’estimation de Judicaël Courant (voir ses diapos sur le sujet), qui m’a confirmé qu’avec une implémentation de son cru, sans optimisation particulière, pour le cas de 2 millions de candidats formulant 100 voeux parmi 1 million de places disponibles, cela prenait quelques minutes sur un PC portable.
Compléments sur APB
Je ne l’ai pas précisé dans la vidéo, mais tout comme Parcoursup, APB était un algorithme de Gale-Shapley dans sa version « formations proposantes ». Mais apparemment ce choix avait pour motivation des contraintes techniques liées au fait de faire plusieurs tours d’affectation.
Concernant le fait que les formations non-sélectives classaient en fonction du rang des voeux des candidats, et donc qu’il fallait parfois mentir sur ses préférences réelles afin d’éviter des déboires, le cas me semble d’autant plus scandaleux que le « Guide du candidat APB » disait en prime, dans la séction « Droits du candidat »
« J’ai le droit de classer mes vœux en toute liberté sans subir une quelconque pression, sachant que les établissements d’origine et d’accueil n’ont jamais connaissance de ma liste ordonnée de vœux. »
Ce qui est choquant, c’est que cette phrase est stricto-sensu vraie, mais induit totalement en erreur. En effet, les formations n’avaient pas accès à la liste ordonnée des voeux. MAIS pour les formations non-sélectives, cette liste était quand même utilisée pour classer les candidats, de façon automatique sur la plateforme, sans que les responsables des formations non-sélectives aient quoi que ce soit à faire.
Donc dans la phrase citée ci-dessus, on affirme quelque chose de vrai, mais que les étudiants interprètent comme « Ok je ne me ferai pas pénaliser par une formation qui serait vexée que je ne l’ai pas classée plus haut », et pourtant in fine c’est exactement ce qui se passe !
Sinon j’ai volontairement laissé de côté quelques détails sur les critères APB, comme le fait que ce qui comptait d’abord était le rang relatif du voeux (parmi les formations de même type), puis le rang absolu. Et aussi la prise en compte de cas particuliers comme la situation de famille, le handicap, les sportifs de haut-niveau…
Parcoursup : des spécifications aux algorithmes
Dans la vidéo, j’ai à plusieurs reprises pointé du doigt des éléments problématiques dans les procédures APB et Parcoursup. Pour bien éclairer le débat, il faut préciser deux choses.
D’une part, les algorithmes (et leurs concepteurs) ne sont pas intrinsèquement en cause. Un algorithme est conçu pour répondre un problème donné, avec des spécifications données. Les algorithmes derrière APB et Parcoursup font leur travail, et le font bien, en ce sens qu’ils répondent correctement aux spécifications qui ont été données par le commanditaire : le ministère de l’éducation nationale. S’il y a quelque chose à critiquer, ce sont les spécifications et pas l’algorithme.
D’autre part, ces spécifications sont en partie conditionnées par des obligations légales. Dans le cas d’APB, c’est bien parce que la loi interdisait le recours à toute forme de sélection qu’il a fallut adopter des critères comme le rang du voeu, et en dernier recours le tirage au sort. En un sens, étant donné le contexte légal, il n’y avait pas moyen de faire beaucoup mieux !
Une des évolutions de Parcoursup a été justement de permettre de dépasser cette contrainte réglementaire en modifiant la loi (notamment par la loi dite « ORE », relative à l’orientation et à la réussite des étudiants). Il me semble que cette loi autorise de facto la sélection à l’entrée à l’université, mais seulement en cas de tension (?)
Revenons sur un des points apparemment choquants de Parcoursup : le fait que les formations proposent et les élèves disposent, et que donc la solution soit « optimale » pour les formations, et « la pire possible parmi les solutions stables » pour les étudiants.
Il semble qu’en pratique cela ne pose pas un gros problème, car les deux solutions se ressemblent quand les « marchés » sont grands et que les classements des proposants (ici les formations) se ressemblent (ce qui est souvent le cas : tout le monde veut les bons élèves). Avec APB/Parcoursup, la différence entre les deux solutions ne concernerait que quelques centaines de cas seulement parait-il ? (je tiens ça d’une communication personnelle, je n’ai pas de source officielle).
Mais surtout la raison de ce choix « les formations proposent », c’est que si on faisait tourner Parcoursup, qui est un « Gale-Shapley au fil de l’eau très ralenti » dans l’autre sens, les étudiants commenceraient avec leur premier choix, qui ne pourrait au cours du temps que se dégrader, sans qu’on sache jamais jusqu’à la fin si on va garder son choix actuel. Encore plus infernal et anxiogène ! Bref, en quelque sorte, le choix de la non-hiérarchisation et de l’affectation au fil de l’eau impose de faire tourner l’algorithme dans le sens « les formations proposent ».
Malgré tout, notons que de nombreux pays pratiquent Gale-Shapley (avec hiérarchisation, donc automatisé) et sont passés de la version « optimale pour les formations », à la version « optimale pour les étudiants. Par exemple pour les internes aux USA, qui ont fait le changement en 1998.
Algorithmes « locaux » et transparence
Dernier point que j’ai occulté dans la vidéo, la question des procédures de classement « locales » qui sont appliquées par chaque formation. Première, cela génère un surcroit de travail important pour les responsables chargés de ce travail de classement. C’est également un jeu dangereux pour les formations, qui sont incitées à faire du « surbooking » dès le départ, pour anticiper les désistement et éviter de se retrouver en sous-nombre, mais avec le risque d’être obligés d’accepter plus d’étudiants que les capacités réelles de la formation. Bref, j’imagine que ce fut un casse-tête pour beaucoup !
Ensuite, on peut se demander comment se fait ce classement ? En principe, les formations font ce qu’elles veulent. Toutefois, elles reçoivent de la plateforme une liste (Excel j’imagine) de tous les candidats ayant postulé, avec les éléments de décision correspondant : notes, avis des professeurs etc. A cela s’ajoute les nouveaux éléments du dossier comme la lettre de motivation.
A priori, cette feuille Excel est là pour servir d’outil de décision, et permet aux formations de choisir des critère de pondération, et de faire un classement à partir de ça. Mais on ne sait rien des coefficients, des critères. Et en dernier ressort, les formations n’ont aucun compte à rendre, elles ont toute liberté.
En un sens, c’est bien pour la prise en compte de cas particuliers, qui ne peuvent se réduire à une série de notes (notamment pour prendre en compte des aspects comme le projet motivé, le handicap, etc.). Mais tout cela manque cruellement de transparence : aucun moyen de savoir ni comprendre pourquoi on n’a pas été pris alors que son voisin l’a été.
A cela s’ajoutent les conflits d’intérêt potentiels, et les inégalités créées par certains éléments du dossier comme la lettre de motivation. On sait très bien qu’elle sera rédigée par les parents, et favorisera les classes socioprofessionnelles plus élevées aux détriment des autres. A tel point qu’on trouve même maintenant des services de « coaching » (facturés fort cher) pour aider les étudiants à réussir leurs demandes Parcoursup. Encore un facteur d’inégalité.
Pour améliorer cela, on pourrait imaginer que chaque formation classe les étudiants à partir des notes auxquels sont appliqués des coefficients qui seraient publics (mais spécifique de chaque formation), et permettraient donc à chacun de comprendre a posteriori quelle a été son classement et pour quelle raison.
Cela n’a rien d’incongru, c’est pratiqué dans de nombreux pays, et cela peut même être implémenté sur la plateforme est pas au niveau local des formations. Les formations se contentent de fixer leurs coefficients et leurs critères, et c’est la plateforme qui établit les classements : simple, transparent, et permet d’éviter les magouilles et conflits d’intérêt.
Du point de vue de la transparence, on peut saluer le fait que le ministère est publié de façon ouverte le code de Parcoursup. On pourrait imaginer aller plus loin en publiant aussi les données de façon anonymisées, de façon à ce que chacun puisse vérifier les calculs de classement et les affectations. Cela permettrait de s’assurer de l’absence de bug ou de dysfonctionnement sur la machine qui fait tourner les algorithmes.
On pourrait même pousser plus loin en demandant l’établissement de preuve de programme par des méthodes formelles, comme cela existe (et la recherche académique française sur ce domaine est d’ailleurs très active).
Du classement local à la liste d’appel
Comme je l’ai expliqué dans la vidéo, une des forces de Parcoursup est de permettre la prise en compte de quota dans les formations : un quota minimum de boursier, et un quota maximum d’étudiants « hors académie », et ce de façon individualisée pour les formations.
Le travail des chercheurs Claire Mathieu et Hugo Gimbert a notamment été de travailler à la prise en compte de ces quotas. C’est-à-dire que leur algorithme prend en entrée le classement « local » établi par chaque formation, et produit en sortie la « liste d’appel », qui est une légère modification du classement local permettant de prendre en compte les quotas.
De façon générale, classement local et liste d’appel seront donc légèrement différents, c’est la liste d’appel qui sera utilisée pour faire des propositions.
35 Comments
Oula ! En voilà un sujet « à risque », j’espere qu’il n’y aura pas trop de commentaires polémiqueurs (ici, j’en doute, mais sur YT on devrait en avoir à la pelle…)
Bon, allez, ma calculette et ma feuille de papier sont prêts, c’est parti pour le visionnage, merci 🙂
Super vidéo ! J’adore le contenu scientifique de la vidéo, bravo ! J’avais juste une petite remarque : vous ne parlez pas du fait qu’APB avait plusieurs phases, avec notamment la démission automatique de tous les élèves qui n’obtiennent pas le bac, la durée de la procedure était donc de l’ordre du mois et non de la seconde. Un avantage (certes limité) de parcoursup est que ces nouvelles places (issues de démissions) sont directement remises à disposition de l’algorithme.
Je plussoie.
Un peu moins de 20% des candidats finissent par quitter la plateforme (déjà vrai sous APB, en baisse sous Parcoursup).
Pour cette raison des places se libèrent en permanence et pour allouer les places ainsi libérées
APB faisait tourner trois fois l’algorithme de Gale-Shapley la dernière fois en juillet.
De plus, afin de traiter les démissions post-troisième phase
APB employait un quatrième instrument appelé rappel de fin de liste et faisait des propositions en août.
Sous APB certains candidats ignoraient cette possibilité et acceptaient définitivement la proposition faite au premier tour,
potentiellement sous-optimale considérant les potentielles démissions futures.
Merci pour la vidéo et le billet !
Très intéressant, comme toujours 🙂
Faut-il privilégier les élèves ou les formations ? On pourrait imaginer un système où les élèves classent dès le début les formations, avec ensuite le système parcousup qui s’applique comme actuellement en laissant de côté au début le classement ; les formations répondent puis parcoursup détermine automatiquement la réponse de chaque élève, et les formations re-répondent, etc. (ce qui induit un délai, mais qui peut être raisonnable, du même type d’apb). Cependant les élèves devrait alors classer initialement les formations ; serait-il possible de permettre un second classement plus tard dans l’année, pour rendre le premier moins décisif ?
Pour se rendre compte du « mécontentement » général (j’imagine, la somme des différences entre le choix final et le choix préférentiel pour chaque élève et chaque formation), aurais-tu des infos sur le nombre moyen de choix par élève, le pourcentage d’élèves qui obtiennent leur choix n°1, n°2, etc ? Il est plus difficile de renverser la question vers les formations, qui évidemment ne classent pas l’ensemble des élèves entre eux, mais uniquement les candidats qui postulent.
Ce sujet amène un bon paquet de questions, merci de l’avoir abordé !
A+
PS, petite coquille « est » au lieu de « ait » : « on peut saluer le fait que le ministère est publié de façon ouverte le code de Parcoursup » (avant-dernier paragraphe de l’avant-dernière partie).
Hello ! Tu dis « Ce qu’il y a de remarquable avec l’algorithme de Gale-Shapley, c’est que pour les proposants, la solution trouvée Pareto-domine toutes les autres solutions stables. C’est donc la seule solution stable sur la frontière de Pareto », puis « il existe potentiellement des solutions qui Pareto-dominent la solution de Gale-Shapley, mais ne sont pas stables ». Comment une solution peut-elle Pareto-dominer celle de GS, lors même que celle-ci est sur la frontière de Pareto ? Ta vidéo va elle aussi dans le sens de dire que GS n’est pas Pareto-optimale, puisqu’on peut trouver mieux, mais dès lors que fait-elle sur la frontière de Pareto ?
Merci pour ta réponse et ton contenu extrêmement intéressant (et utile).
Ma compréhension est que GS donne une solution qui Pareto-domine (du point de vue des « proposants ») dans le sous-ensemble des solutions stables. Dans l’ensemble général GS ne donne *pas* une solution Pareto-optimale
En effet c’est cela, ma formulation porte à confusion !
Bonjour David,
Dans la vidéo vers 34:35 tu explique que la CNIL a interdit le recourt au tirage au sort, et tu ajoute « ce qu’on peut largement comprendre ».
Pourrais-tu expliquer en quoi c’est injuste car pour moi c’est la solution plus juste en cas d’ ex-æquo ?
Commentaire pertinent ! J’aimerais bien connaître l’avis de David là dessus.
Bonjour,
Je me permets de réagir sur la manipulabilité par les proposants « la procédure n’est pas manipulable par les proposants;
elle ne l’est même pas en cas de coalition de proposants qui essayent collectivement d’améliorer leur sort ».
La propriété de non manipulabilité par une coalition est subtile:
* Il est impossible pour une coalition de proposants de manipuler l’algorithme afin que TOUS les manipulateurs obtiennent une meilleur affectation.
* Or il est parfaitement possible que certains manipulateurs obtiennent une meilleur affectation, tandis que les autres conservent leur affectation.
C’est important lorsque on considère l’algorithme « formations proposantes » (car une école c’est une coalition de proposants). Dans l’exemple suivant :
Alice : Sciences > Économie > Lettres
Bob : Économie > Lettres > Sciences
Chloé : Lettres > Sciences > Économie
David : Lettres > Économie > Sciences
Fac de lettres (2 places) : Alice > Bob > Chloé > David
Fac d’économie (1 place) : Alice > Bob > Chloé > David
Fac de science (1 place) : Chloé > Alice > Bob > David
Si on utilise l’algorithme « formation proposantes », on obtient le matching stable suivant :
Lettres : Chloé, David
Économie : Alice
Sciences : Bob
Or la fac de lettre peut mentir et fournir le classement : Bob > David > Alice > Chloé. On obtient alors
Lettres : Bob, David
Économie : Alice
Sciences : Chloé
Conclusion, la fac de lettre peut manipuler avec succès dans l’algorithme « formations proposantes ».
PS : Bon, en pratique ce n’est pas un problème car effectivement ce genre de situation ne se produisent quasiment jamais (cf littérature sur les « grands marchés », https://www.aeaweb.org/articles?id=10.1257/aer.99.3.608)
Oui en effet, par « collectivement » j’entendais « où chacun s’améliore strictement »
Excellente vidéo, j’ignorais tous ces détails et événements autours d’APB et Parcoursup, merci !
Question : Pourquoi penses tu que la CNIL a rendu obligatoire l’intervention humaine dans le traitement des dossiers ? Par peur des algorithme ? De la part de la CNIL cela m’étonne.
Merci !
C’était tout simplement la loi de 1978 informatique et libertés qui interdisait de prendre une décision par l’action seule d’un système automatisé. Cette partie de la loi a été abrogée au moment de la transposition de la directive RGPD… pour la bonne et simple raison qu’elle était assez largement pas respectée, par exemple par les services des impôts !
Texte de la décision sur la base de l’article 10 de la loi du 6 janvier 1978 : https://www.legifrance.gouv.fr/affichCnil.do?id=CNILTEXT000035647959
Version du texte en vigueur en 2017 : https://www.legifrance.gouv.fr/affichTexte.do?cidTexte=JORFTEXT000000886460&dateTexte=20170110#LEGIARTI000006528078
Version du texte en vigueur aujourd’hui, où cette partie est maintenant à l’article 47, et assortie d’exceptions, entre autres quand l’algorithme est transmis au public : https://www.legifrance.gouv.fr/affichTexte.do?cidTexte=JORFTEXT000000886460&dateTexte=20200110#LEGIARTI000037823131
J’ai exagéré en écrivant abrogation, disons que c’est un vidage de substance 🙂
Merci pour cette réponse très détaillée !
Il me semble qu’on pourrait améliorer un peu encore le système de Gale-Shapley, en informant dans un tout premier tour, avant traitement de l’algorithme, chaque camps du classement, des « désirs bruts » en fait, de l’autre camp.
En effet le fait d’apprendre qu’un établissement qu’on a classé en premier dans nos choix, nous a classé, lui, en dernier, pourrait simplement nous faire abandonner cette idée apparemment saugrenue de vouloir y aller, et nous faire réviser notre classement de façon plus réaliste…
Et de l’autre côté il est très probable que le fait de se savoir très « désiré » par une fac ou une école puisse influencer le choix du candidat, donc faire progresser un peu son classement vers cet établissement… N’oublions pas que dans la vie, on cherche quand même un peu (c’est rien de le dire) une « valorisation » des autres, et on pourrait se diriger vers une spécialité dont les membres vous regardent avec « envie »…
Du côté des écoles cet étape initiale pourraient faire évoluer un peu dans leur classement ceux qui veulent vraiment venir chez eux et seront potentiellement très motivé pour réussir.
Ensuite on balance l’algorithme et s’il y a toujours des « inquiets méfiants » on leur fait voir cette excellente vidéo explicative ! (bravo !)
Mais bien sûr cet étape d’information initiale des parties ne fonctionnerait pas (mais pas du tout 🙂 ) en amour car dans ce domaine, au contraire, on a plutôt tendance, à vouloir ce qu’on à pas, ce qui nous résiste !… Ah l’Amour… 🙂
N’y a-t-il pas une forme de paradoxe de Condorcet?
> On pourrait même pousser plus loin en demandant l’établissement de preuve de programme par des méthodes formelles, comme cela existe (et la recherche académique française sur ce domaine est d’ailleurs très active).
Cela a été (partiellement) fait: https://hal.inria.fr/hal-02421484 😉
Ah merci, cette publication toute récente (20 décembre 2019 !) m’avait échappé !
Bonjour,
J’ai vu ceci… « Un point concernant les temps de calcul, et notamment le fait qu’APB ne prenne que quelques minutes ». Euh…. C’est un peu terrible d’écrire cela sans précision. C’est une assertion que je pense correcte d’un point de vue algorithmique mais ultra fausse d’un point de vue réalisation concrète.
En effet, assurer les mariages entre quelques millions de candidats et quelques millions de places disponibles est ultra rapide étant donnée nos machines de calcul actuelles (en simulation, je suis persuadé que les quelques minutes sont justes voire larges…). Une fois qu’on appuie sur la touche entrée, ok, ça va être très rapide. MAIS QUELS SONT LES PRÉREQUIS AVANT D’APPUYER SUR ENTRÉE ? Le prérequis simple est le suivant : les candidats ont fait leur choix (en plus, on a limité à 24…). L’autre prérequis qui fait mal : les formations ont fait un classement préalable de l’intégralité des millions de candidats qui pourraient postuler chez eux.
Malheureusement, le facteur limitant est souvent la capacité des formations à opérer ces classements. Les tris sont des opérations globales (et pas locales). Pour être équitable, un bon tri est souvent opéré par un seul humain (quand c’est un groupe d’enseignants évaluateurs, ces derniers doivent s’étalonner les uns les autres avant de procéder à une fusion (d’où le fait que le tri est global…)). Les responsables de formations sont en première ligne pour opérer ces tris qui sont relativement difficiles à opérer. Il n’y a ni méthode, ni formation pour opérer ces tris. Chaque formation fait le tri selon ses moyens et sa sauce… Certaines formations sont très performantes dans ces tris vis à vis des moyens alloués pour les opérer (des acharnés entêtés qui veulent bien faire leur travail et y laisse leur nuit, temps libres, etc… Il y a clairement des avenirs(des vies) en jeu).
On ne peut pas raisonner en partant du principe que l’intégralité des formations aura fait son propre classement de l’intégralité des candidats (pragmatiquement impossible). Je n’ai pas les nombres et donc je ne suis pas certain, mais je pense même qu’exiger des formations de trier le sous-ensemble des candidats ayant cité la formation dans leurs vœux imposerait des formations à opérer des tris sur des populations bien trop grandes (formation victime de leur succès, prépa célèbre, etc…).
La seule option pour rendre totalement opérable Gale-Shapley serait d’automatiser les classements (établir une fonction de fitness par formation pour opérer le tri sur machine) du coté des formations et c’est là que la CNIL va tiquer… Sinon, il ne faudrait pas quelques minutes mais un temps infini pour laisser les formations tout trier.
Je me demande à quel point le passage APB –> parcoursup à pour but d’alléger les besoins d’évaluation de dossiers de la part des formations. Je n’ai pas la réponse mais s’ils sont censés, les décisionnaires ont du se poser la question…
Il y a les modèles et les algos (heureusement !) mais étant donné la réalité du terrain, je ne crois pas qu’on puisse se passer de l’humain pour opérer ces mariages. L’humain sait prendre en compte toutes les situations (même les non-prévisibles) mais il est lent et pas fiable (il reste statistiquement infiniment mieux que le hasard dans la quasi-totalité des situations).
Bonjour David, il me semble que parcoursup rend la procédure manipulable par les formations à cause du biais qui fait que les étudiants vont plus facilement dans la formation qui dit oui en premier.
Ainsi si une formation a peu de places, elle a intérêt à surclasser des étudiants plus susceptibles de venir: par exemple des candidats locaux mois bons mais plus susceptibles de venir afin qu’ils reçoivent une proposition rapidement.
J’ai l’impression que ça optimise le recrutement de formations avec beaucoup de places et au recrutement national au détriment de formations au recrutement plus local.
PS: comme on peut le deviner je travaille dans une formation à recrutement »local »
Oui bien vu, c’est un biais intéressant !
<>
Oulah
《 saluer le fait que le ministère EST publié de façon ouverte le code 》
Attention
Au sujet de « On pourrait même pousser plus loin en demandant l’établissement de preuve de programme par des méthodes formelles, comme cela existe (et la recherche académique française sur ce domaine est d’ailleurs très active). » il y a justement un projet en cours sur la vérification du code de Parcoursup, qui rassemble des chercheurs du LRI et du LaBRI, avec l’appui du comité scientifique et éthique de Parcoursup (Gérard Berry en particulier) et le soutien financier du MESRI.
Bonjour David,
Merci beaucoup pour cette vidéo. J’espère sincèrement qu’elle sera visionnée par des membres du gouvernement actuel et des gouvernements futurs.
Je souhaitais revenir sur ton affirmation que le nouvel algorithme parcours-sup fait des étudiants des disposeurs, et donc leur fournit la pire solution stable de leur point de vue.
D’après ma compréhension du sujet, le désavantage associé à la position de disposeur vient du fait que ceux-ci n’ont pas la possibilité d’interroger leurs choix préférés, et doivent attendre que ceux-ci daignent les interroger. Cela n’arrivant pas forcément, l’espace des solutions ignore un certain nombre de bons choix, et la solution est donc sous-optimale de leur point de vue.
En revanche ici, les étudiants interrogent dès le premier tour l’ensemble de leurs choix, y compris leurs premiers choix. De ce fait j’ai du mal à imaginer un cas où les étudiants, via leurs réponses n’auraient pas la possibilité de retrouver la solution optimale qu’ils auraient obtenus en situation de demandeurs.
Qu’en penses-tu ?
Merci beaucoup !
Thibault
Bonjour,
Un article plus sociologique en complément sur l’utilisation de ces plateformes.
Bonne journée
Bonnjour,
Je remets mon commentaire car j’ai oublié le lien 🙂
https://www.cairn.info/revue-sociologie-2019-2-page-209.htm
Un article sociologique sur la naissance de ces plateformes et leurs usages.
Bonne journée
Wow, pour avoir pratiqué APB je n’imaginait pas qu’il y avait tant de choses à dire sur le sujet.
Il y a un axe de critique qui selon moi était plus politique, c’est le fait d’introduire à l’université la sélection sous la forme d’un faux dilemme de la part du gouvernement : sélection ou hasard. Les filière maintenant en tension le sont en partie à cause d’un sous-investissement dans les études supérieures que l’on masque par un debat technique.
Maintenant cela a introduit un précédent à une sélection universitaire qui avait été interdite pour éviter les biais que tu indiques quand aux choix opaques des établissements.
Tu proposes à la place de selctionner officiellement sur les notes, mais j’ai du mal à voir en quoi cela cela change grand chose quand à l’avantage que cela procure aux catégories socio-professionnelles plus élevées. Les parents paieront des cours particuliers, mettront leurs enfants dans de « meilleurs » établissement, je ne sais même pas pourquoi j’en parle au futur, c’est déjà le cas.
Là où le hasard est le choix qui paradoxalement ne favorise personne et semble donc léser tout le monde. C’était un palliatif au manque de place pour assurer que l’université était bien ouverte à tous avec les mêmes chances quelle que soit sa « réussite » scolaire (qui est déjà corrélée au milieu socio-professionnel).
Voir la vidéo d’Usul à ce sujet :
https://youtu.be/KUMW5bhCsgw
Bonjour et bravo pour cette vidéo très claire !!
Est-il vraiment exact de dire que Parcours sup utilise Gale-Shapley car il me semble qu’un candidat peut accepter définitivement un de ses choix au cours du process c’est à dire alors que l’algo n’a pas convergé vers une solution stable ?
Merci !
Bonjour, j’ai l’impression qu’il y a une erreur dans le raisonnement suivant :
« Ce qu’il y a de remarquable avec l’algorithme de Gale-Shapley, c’est que pour les proposants, la solution trouvée Pareto-domine toutes les autres solutions stables. C’est donc la seule solution stable sur la frontière de Pareto. Ce qui est assez incroyable je trouve ! »
J’ai l’impression qu’il faudrait plutôt dire : » C’est donc la seule solution de la frontière de Pareto parmi les solutions stables pour les proposants ». Cela revient certainement au même, mais les questions d’ordre non total n’étant pas si simples, cela me semblerait plus adapté à la proposition précédente. Qu’en pensez-vous ?
Vous remerciant par ailleurs de la qualité remarquable de votre travail, et vous souhaitant bonne continuation,
O. EVEILLEAU
La vidéo était super ! D’ailleurs c’est l’une des rares fois que je lis le billet de blog qui l’accompagne en entier, mais c’était tout aussi intéressant. J’ai commenté à la suite de ta vidéo une réflexion légèrement éditée ci-dessous :
J’ai toujours eu l’impression que l’absence de classement des voeux sur parcoursup était un minimum aberrant (du moins sur le principe, je ne suis pas assez documentée sur le sujet, apparemment ce n’est jamais le cas mais si juste une personne était défavorisée par le système ça me semblerait problématique). Je me demandais justement si demander aux élèves de classer leurs voeux sans que les universités n’en tiennent compte (n’y aient accès) n’était pas un bon moyen de continuer à utiliser Gale-Shapley à l’avantage des étudiants, sans pour autant perdre le temps de la procédure d’admission sans algorithme.
Les avantages énoncés dans ta vidéo (oui, si… et les quotas des établissement d’accueil) changent légèrement mon raisonnement, donc un système similaire à celui de l’Allemagne pourrait-t-il être envisagé ? à chaud j’ai l’impression qu’une procédure où les étudiants envoient d’abord leurs voeux (sans forcément les classer, car de toute façon le classement n’est pas définitif et pas déterminant pour cette étape, je crois). Les établissement répondent ensuite à base de oui ; oui, si… ; non et éventuellement liste d’attente (cette info étant potentiellement déterminante pour aider l’élève à choisir, mais potentiellement pas du tout, voire déstabilisante). à la suite de cette phase, les élèves pourraient donc effectuer un classement et le principe de Gale-Shapley pourrait être utilisé sans les inconvénients d’APB (cf. le classement stratégique pas forcément sincère).
C’est un premier jet et ça ne sert peut être à rien d’y réfléchir mais je me demandais si quelqu’un pouvait me montrer les failles de ce procédé ? J’ai d’ailleurs du mal à trouver comment conserver le respect des quotas de la part des établissements, si quelqu’un a un élément de réponse là-dessus aussi, je suis preneuse.
Pingback: PARCOURSUP 👩🏽🎓🏫 et les algorithmes de mariage stable ❤️ - Qualitay.fr
Bonjour David,
D’abord : excellente vidéo et quelle clarté, bravo franchement !
Perso je suis concerné par Affelnet, et si j’ai bien compris : l’algo d’Affelnet est un Gale-Shapley (« acceptation différée » selon le terme utilisée par J. Grenet) en version (hélas) « *lycée-proposants* ». C’est bien cela ?
C’est-à-dire que pour reprendre votre exemple de GoT où se pose le conflit suivant entre Cersei et Brienne (j’ai sorti par simplicité le couple Drogo/Daenerys car évident et indépendant de qui propose) :
• Cersei aimerait Jon mais ce dernier préfère Brienne
• Brienne aimerait Jaime mais ce dernier préfère Cersei.
Donc si Affelnet est « lycées-proposants » (ici : « femmes proposantes ») alors Jon est affecté à Cersei, et Jaime à Brienne. Si les hommes (élèves) avaient proposé, cela aurait été différent.Vous confirmez ?
Bonjour, le lien vers le site de Judicael Courant est obsolète.