Problème des mariages stables

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques et en informatique, le problème des mariages stables consiste à trouver, étant donné n hommes et n femmes, une façon stable de les mettre en couple. La stabilité signifie que chaque femme et chaque homme préfère rester avec son conjoint présent plutôt que d'être avec quelqu'un d'autre. Un exemple de situation instable serait que Monsieur Dupont préfère Madame Durand à Madame Dupont, et Madame Durand préfère Monsieur Dupont à Monsieur Durand.

Plus formellement, on se donne deux ensembles A et B ayant chacun n éléments. On se donne aussi, pour chaque élément de A et B, une fonction de préférence, qui classe les éléments de l'autre ensemble. On cherche alors à associer de façon bijective les éléments de A avec ceux de B, pour qu'il n'existe pas a \in A et b \in B tels que a préfère b à l'élément qui lui est associé, et b préfère a à l'élément qui lui est associé.

Les algorithmes de résolution du problème des mariages stables trouvent des applications dans de nombreux domaines.

Algorithme de Gale-Shapley[modifier | modifier le code]

Principe et propriétés[modifier | modifier le code]

En 1962, David Gale et Lloyd Shapley ont prouvé qu'il était toujours possible de résoudre le problème des mariages stables. Ils ont de plus présenté un algorithme permettant de trouver une solution[1],[2].

Celui-ci fonctionne par étapes. À chaque étape, chaque homme célibataire se propose à la femme qu'il préfère parmi celles à qui il ne s'est jamais proposé (sans regarder si elle est déjà en couple). Chaque femme considère alors les propositions qui lui sont faites (en incluant éventuellement celui avec qui elle est déjà), puis dit « peut-être » à l'homme qu'elle préfère et « non » à tous les autres.

Cet algorithme assure que :

Tout le monde finit par être en couple 
Si une femme est déjà en couple (après avoir dit « peut-être » à un homme), elle le reste pour toute la suite de l'algorithme. À la fin, il ne peut donc pas y avoir un homme et une femme célibataires, puisque l'homme se sera forcément proposé à la femme à un moment donné.
Les mariages sont stables 
Donnons-nous, à la fin de l'algorithme, une femme Alice et un homme Bob tous les deux mariés, mais pas ensemble. Si Bob préfère Alice à sa femme, cela veut dire qu'il s'était proposé à Alice avant de se proposer à sa femme. Si Alice avait accepté, puisqu'elle n'est plus avec lui à la fin, c'est qu'elle l'a remplacé par quelqu'un qu'elle préférait et donc qu'elle ne préfère pas Bob à son mari. Si Alice avait refusé, c'est qu'elle était déjà avec quelqu'un qu'elle préférait à Bob.

Pseudo-code[modifier | modifier le code]

fonction mariageStable {
    Initialiser tous les m ∈ M et w ∈ W à célibataire
    tant que ∃ homme célibataire m qui peut se proposer à une femme w {
       w = femme préférée de m parmi celles à qui il ne s'est pas déjà proposé
       si w est célibataire
         (m, w) forment un couple
       sinon un couple (m', w) existe
         si w préfère m à m'
           (m, w) forment un couple
            m' devient célibataire
         sinon
           (m', w) restent en couple
    }
}

Optimalité de la solution[modifier | modifier le code]

Bien que la solution soit stable, ce n'est pas nécessairement une solution optimale pour tous les individus. La forme traditionnelle de l'algorithme est optimale pour ceux qui se proposent mais pas forcément pour ceux qui choisissent. Voici un exemple :

Il y a trois prétendants A, B et C et trois choisisseurs X, Y et Z dont les préférences sont :

 A : YXZ, B : ZYX, C : XZY, X : BAC, Y : CBA, Z: ACB

Il y a trois solutions stables à ce problème de mariages :

  • les prétendants ont leur premier choix et les choisisseurs leur troisième (AY, BZ, CX)
  • tous les participants ont leur deuxième choix (AX, BY, CZ)
  • les choisisseurs ont leur premier choix et les prétendants leur troisième (AZ, BX, CY)

L'algorithme ci-dessus donne la première solution.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Stable marriage problem » (voir la liste des auteurs)

  1. (en) D. Gale et L. S. Shapley, « College Admissions and the Stability of Marriage », dans Amer. Math. Month., vol. 69, 1962, p. 9-14
  2. (en) Harry Mairson (en), « The Stable Marriage Problem », dans The Brandeis Review, vol. 12, 1992 (version en ligne).

Articles connexes[modifier | modifier le code]