Un grand nombre des spécialistes de l’algorithme vous diront qu’il faut faire migrer Affelnet – basé sur l’algorithme de Gale et Shapley de 1962 – d’un modèle d’acceptation différée école-proposant vers un modèle d’acceptation différée élève-proposant [voir Note 1]. En effet, il existe toujours plusieurs solutions d’associations élèves – lycée (on appelle cela des mariages stables).
Or l’algorithme de Gale et Shapley ne donne pas forcément le meilleur ensemble d’associations. Certes il garantit d’en donner une pour chacun des deux modes, mais le modèle élève-proposant donnera de meilleurs résultats pour les élèves. Il aurait été donc juste d’inverser le sens de traitement, et de commencer par analyser les choix des élèves. Le théorème de McVitie-Wilson (1970) montre que les non affectés seront les mêmes dans les deux modes.
A noter que d’autres algorithmes existent, comme justement celui de McVitie-Wilson, mais aussi de nombreux autres algorithmes fournissent des résultats soit plus rapides, soit plus stables (c’est à dire résistants à des combinaisons ou coalitions) [voir Note 2], voire avec des « regrets » minimaux (algorithme de Stan Selkow) [voir Note 2b]
Enfin, pour problématiser encore, le think tank Terra Nova a aussi consacré une étude à Affelnet [voir Note 3], qui même si elle a vieilli en 3 ans pose les bases du problème de manière sociologique.
Eléments de discussion :
Il est regrettable que l’état se satisfasse d’un algorithme daté, ayant près de 60 ans maintenant, alors que la recherche mathématique et informatique a bien évolué. La note [voir Note 2] donne quelques éléments dont la lecture nous a semblé pertinente, mais dans le spectre des algorithmes dont le coût est en 
Enfin pour ceux qui veulent survoler l’algorithme, la page Wikipédia Algorithme_de_Gale_et_Shapley servira de bon point d’introduction. Cette page a aussi l’intérêt de proposer plusieurs bibliothèques de code. Nous pouvons vous conseiller :
- L’API MatchingTools (https://matchingtools.com/) fournit une interface de programmation applicative pour l’algorithme, et permet de tester les algorithmes d’acceptation différée comme ceux de Roth, d’Irving ou encore « Top-Trading ».
- Langage Python : L’algorithme de Gale-Shapley est disponible dans la librairie QuantEcon/MatchingMarkets.py sur GitHub : https://github.com/QuantEcon/MatchingMarkets.py .
En tout cas elle explique l’algorithme bien mieux que ne le fait la démonstration poussive de J. GRENET sur youtube (Exposé « La transparence et l’obstacle : les algorithmes d’affectation des élèves aux établissements d’enseignement », 11 mai 2017, https://www.youtube.com/watch?v=oprFPrZcNq4).
[Note 1] : De nombreux auteurs se sont exprimés sur ce point et la littérature et les auteurs foisonnent, comme J. GRENET, V. HILLER et O. TERCIEUX, Julien COMBE, Thierry MAGNAC et d’autres :
- Julien GRENET, « La transparence et l’obstacle : Les algorithmes d’affectation des élèves aux établissements d’enseignement », Paris 2 Panthéon-Assas, 30 mai 2017, https://f.hypotheses.org/wp-content/blogs.dir/2818/files/2017/03/Slides_seminaire_Codes_Sources.pdf
- Victor HILLER, Olivier TERCIEUX, « Choix d’écoles en France : Une évaluation de la procédure Affelnet », Revue économique 2014/3 (Vol. 65), pages 619 à 656, https://www.cairn.info/revue-economique-2014-3-page-619.htm#
- Thierry MAGNAC, « Quels étudiants pour quelles universités ? Analyses empiriques de mécanismes d’allocation centralisée. », Toulouse School of Economics, WP n°18‐899, mars 2018, https://core.ac.uk/download/pdf/300464677.pdf
[Note 2] : Pour entrer dans le problème nous vous conseillons la lecture de :
- D. Gale and L. S. Shapley, « College Admissions and the Stability of Marriage », The American Mathematical Monthly, Vol. 69, No. 1 (Jan., 1962), pp. 9-15 (7 pages), Published By Taylor & Francis, Ltd., https://www.jstor.org/stable/2312726
- Katarína Cechlárová & David F. Manlove, « The exchange-stable marriage problem », Discrete Applied Mathematics, Volume 152, Issues 1–3, 1 November 2005, Pages 109-122, https://www.sciencedirect.com/science/article/pii/S0166218X05001435
- R.W. Irving, « An efficient algorithm for the “stable roommates” problem », Journal of Algorithms, Volume 6, Issue 4, December 1985, Pages 577-595, https://www.sciencedirect.com/science/article/abs/pii/0196677485900331
[Note 2b] : Lire à ce sujet le rapport de Stage de L3 sur Le Problème des Mariages Stables de Marguerite Flammarion (8 au 26 juin 2015) : https://flammarion.eu/uploads/stage.pdf
[Note 3] : De nombreux auteurs se sont exprimés sur ce point et la littérature et les auteurs foisonnent, comme J. GRENET, V. HILLER et O. TERCIEUX, Julien COMBE, Thierry MAGNAC et d’autres :
- Julien COMBE, Victor HILLER, Olivier TERCIEUX, Camille TERRIER : « Faut-il sauver les algorithmes d’affectation ? Affelnet, mouvement des enseignants et Parcoursup », Terra Nova, 6 juin 2018, https://tnova.fr/system/contents/files/000/001/571/original/Terra_Nova_Rapport__Algorithmes_060618.pdf
Une réflexion au sujet de « Il faut revoir le modèle algorithmique… »