Il faut revoir le modèle algorithmique…

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 {\displaystyle \textstyle O(n^{2})}, il y a de nombreuses solutions !

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 :

[Note 2] : Pour entrer dans le problème nous vous conseillons la lecture de :

[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 :

Une réflexion au sujet de « Il faut revoir le modèle algorithmique… »

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s