Le problème des mariages stables (Théorie des graphes)

Deux groupes se font face : hommes et femmes, chacun portant le rêve d’un autre.
Chercher l’âme sœur devient un jeu de regards et de désirs.
Parfois, deux cœurs se trouvent plus attirés ailleurs : le couple se brise.
Un mariage stable est un calme où aucun cœur n’est tenté de fuir.
Gale et Shapley ont montré que cet équilibre, fragile, existe toujours.
Les propositions et refus tissent une danse lente vers l’harmonie.
Dans ce ballet des cœurs, le bonheur de l’un peut être le sacrifice de l’autre.

🌍 Le contexte :

Imagine qu’on a autant d’hommes que de femmes, et que chacun classe les personnes du sexe opposé selon ses préférences (de la plus à la moins aimée).
Le but est de former des couples (des mariages) de sorte que tout le monde soit apparié — c’est-à-dire qu’il n’y ait pas de célibataires.

💔 Le problème de l’instabilité :

Parfois, dans un mariage donné, il existe un homme et une femme qui se préfèrent mutuellement à leur partenaire actuel.
Ce duo forme ce qu’on appelle un “couple bloquant”, car ils menacent la stabilité du système : ils voudraient divorcer pour être ensemble.
Un mariage stable, c’est donc une situation où aucun couple bloquant n’existe.

🔄 Les “divorces spontanés” :

Si on laisse ces couples bloquants se former naturellement (et donc d’autres divorces se produire), on pourrait croire qu’au bout d’un moment, tout va se stabiliser.
Mais le mathématicien Donald Knuth a montré qu’en réalité, il est possible que ça tourne en boucle : les gens se quittent et se remettent ensemble à l’infini, sans jamais atteindre une stabilité.

🧠 La découverte de Gale et Shapley (1962) :

Heureusement, deux mathématiciens, David Gale et Lloyd Shapley, ont prouvé qu’il existe toujours au moins un mariage stable, quelles que soient les préférences.
Ils ont même inventé un algorithme pour le trouver, appelé l’algorithme de Gale–Shapley.

⚙️ L’algorithme (version simple) :

Chaque homme propose à la femme qu’il préfère.
Chaque femme garde le meilleur prétendant parmi ceux qui lui ont fait une proposition et rejette les autres.
Les hommes rejetés proposent ensuite à leur deuxième choix, et ainsi de suite.
On répète le processus jusqu’à ce que tout le monde soit en couple.

➡️ Résultat : on obtient un mariage stable.

⚖️ Deux versions :

Si les hommes proposent, ils obtiennent le meilleur mariage possible pour eux, mais le pire pour les femmes.
Si les femmes proposent, c’est l’inverse.

Autrement dit : le meilleur équilibre pour un groupe est le moins bon pour l’autre.

🔁 Les cycles et cas étranges :

Knuth pensait qu’on ne pouvait pas avoir de situation où les mariages tournent forcément en boucle.
Mais plus tard, un autre mathématicien, Akihisa Tamura, a trouvé un exemple où c’est exactement ce qui se passe : un véritable enfer d’instabilité où tout le monde divorce et se remet ensemble sans fin.

💡 La solution : autoriser le célibat

Si on autorise la possibilité de rester célibataire, alors ces boucles disparaissent : il y aura toujours une suite d’actions possible qui mène à une situation stable.

🧩 D’autres résultats intéressants :

On peut représenter toutes les solutions stables comme un graphe de transformations (chaque rotation de couples en crée une nouvelle).
Certaines configurations ont beaucoup (même un nombre exponentiel) de mariages stables possibles.
Le théorème de Roth montre qu’il est impossible d’avoir un mécanisme “parfaitement honnête” : quelqu’un a toujours intérêt à mentir sur ses préférences pour obtenir mieux.
Et, fait ironique : dans toutes les solutions stables, ce sont toujours les mêmes personnes qui restent célibataires.

🏠 Et pour finir, le “problème des colocataires” :

Si on supprime la distinction hommes/femmes (tout le monde peut se mettre avec tout le monde), alors il n’y a plus de garantie qu’une solution stable existe.
Certains groupes d’amis se séparent et se reforment sans fin.
Heureusement, un autre mathématicien, Robert Irving, a trouvé un algorithme pour déterminer si une solution stable existe ou non.

🧭 En résumé :

Le problème des mariages stables est une façon mathématique d’étudier comment former des couples durables quand tout le monde a des préférences personnelles.
👉 Il montre que :

une solution stable existe toujours,
mais qu’elle dépend de qui fait les propositions,
et que même dans un monde d’équations, l’amour reste une affaire complexe ❤️