Comment ça marche, précisément
Chacun classe TOUS les autres participants. Il n'y a qu'un seul groupe, donc aucune asymétrie entre proposants et receveurs.
Première phase : chacun propose au mieux classé qui ne l'a pas encore éconduit ; les propositions améliorantes sont provisoirement acceptées, les moins bonnes rejetées. On obtient une table réduite.
Seconde phase : on repère et supprime les rotations — des chaînes de préférences cycliques qui empêchent la stabilité — jusqu'à ce que chacun n'ait plus qu'un partenaire, ou que la table se vide, ce qui prouve l'absence de solution.
L'appariement obtenu est stable : aucune paire de personnes non appariées ensemble ne se préfère mutuellement à son partenaire actuel.
Un exemple chiffré
Quatre personnes à apparier en binômes, chacune ayant classé les trois autres.
| Personne | 1ᵉʳ | 2ᵉ | 3ᵉ |
|---|---|---|---|
| Chloé | Ali | Bruno | Dana |
| Ali | Chloé | Dana | Bruno |
| Bruno | Dana | Chloé | Ali |
| Dana | Bruno | Ali | Chloé |
- Chloé et Ali se placent mutuellement en premier : la paire s'impose.
- Bruno et Dana font de même : seconde paire.
- Aucune paire extérieure ne se préfère mutuellement : l'appariement est stable.
Ici, les préférences s'emboîtent parfaitement. Modifiez un seul classement et l'appariement stable peut disparaître complètement — c'est la fragilité propre à ce problème.
D'où ça vient
Le problème est posé en 1962 par David Gale et Lloyd Shapley, à la toute fin de leur article fondateur sur le mariage stable : et si, au lieu de deux groupes distincts, tout le monde appartenait au même ensemble ? Ils signalent que leur algorithme ne s'y applique pas, et laissent la question ouverte.
Ils démontrent au passage qu'un appariement stable peut tout bonnement NE PAS EXISTER — différence essentielle avec le mariage stable, où il en existe toujours un.
Robert Irving publie en 1985 le premier algorithme en temps polynomial : il détermine si une solution stable existe et la construit le cas échéant, en deux phases dont la seconde élimine méthodiquement des « rotations ».
Où on s'en sert
- Constituer des binômes de travail, de relecture ou de pair programming.
- Attribuer des colocataires ou des compagnons de chambre.
- Apparier des partenaires d'entraînement ou de tournoi.
- Organiser du mentorat entre pairs, sans hiérarchie entre les deux rôles.
Limites et pièges
- Aucune paire n'a envie de « fuguer »
- Fondé sur les préférences des deux côtés
- Détecte honnêtement les cas impossibles
- Un appariement stable n'existe pas toujours
- Exige un effectif pair
- Classer tout le monde peut être long
Questions fréquentes
Que se passe-t-il si aucune solution stable n'existe ?
L'outil le dit franchement. C'est une information réelle sur le groupe : les préférences forment un cycle irréductible. À vous d'ajuster — apparier par affinité déclarée, ou accepter une instabilité assumée.
Quelle différence avec Gale-Shapley deux groupes ?
Gale-Shapley suppose deux ensembles distincts qui se classent mutuellement (candidats et formations) et garantit toujours une solution. Ici, tout le monde est dans le même ensemble, il n'y a pas de côté avantagé — mais la garantie d'existence disparaît.
Que signifie « stable » exactement ?
Qu'il n'existe aucune paire de personnes qui, sans être appariées ensemble, se préféreraient mutuellement à leur partenaire actuel. Une telle paire quitterait le dispositif : c'est précisément ce que la stabilité empêche.
Sources
Les références primaires sur lesquelles s'appuie cette fiche.
- Gale, David et Shapley, Lloyd S., College Admissions and the Stability of Marriage, The American Mathematical Monthly, 69(1), 9-15, 1962. DOI ↗
- Irving, Robert W., An Efficient Algorithm for the « Stable Roommates » Problem, Journal of Algorithms, 6(4), 577-595, 1985. DOI ↗
- Gusfield, Dan et Irving, Robert W., The Stable Marriage Problem: Structure and Algorithms, MIT Press, Cambridge, 1989.