Problème des mariages stables

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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. Il y a instabilité lorsqu'un homme et une femme préfèrent tous deux se mettre en couple l'un avec l'autre plutôt que de rester chacun avec son conjoint respectif. 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 tous 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 et 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],[3],[4].

L'une des façons de présenter cet algorithme est de fonctionner 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, étant donnés un ensemble d’hommes et un ensemble de femmes tous deux de cardinal et l’ensemble des couples engagés (homme ; femme) renvoyé par l’algorithme :

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é.


De manière plus formelle, on va montrer que tout élément de apparaît exactement une et une seule fois dans un couple de . Pour cela, on va montrer que la propriété
 : «  homme , est célibataire ne s’est pas proposé à toutes les femmes »
est un invariant de l’algorithme. Raisonnons par l’absurde et supposons que ne soit pas un invariant. Alors, est fausse à un instant donné, c’est-à-dire à un tour de boucle donné. Alors : un homme 0 , 0 est célibataire 0 s’est proposé à toutes les femmes . Donc, nécessairement, toutes les femmes sont engagées avec d’autres hommes. Or, les ensembles et étant de même cardinal et une même femme ne pouvant s’engager avec deux hommes différents d’après l’algorithme (voir fonction mariageStable ci-dessous), cela signifie que 0 est engagé avec une femme. On a donc une contradiction avec l’affirmation de départ : «  n’est pas un invariant ». C’est donc que est un invariant, et donc, celui-ci est vrai pour tous les tours de boucle de l’algorithme.
Ainsi, en quittant l’algorithme, la condition de la boucle est fausse. Donc : homme , est engagé s’est proposé à toutes les femmes . Soit . Si s’est proposé à toutes les femmes , alors comme est un invariant de cet algorithme, il est vrai à la fin de ce dernier. Donc, en particulier, comme :
«  est célibataire ne s’est pas proposé à toutes les femmes  », la contraposée nous affirme que est engagé. Par conséquent, à la fin de l’algorithme, tous les hommes sont engagés. Pour conclure, comme les ensembles et sont de même cardinal et qu’une même femme ne peut être engagée avec deux hommes différents, on en déduit que toutes les femmes sont également engagées. Ainsi, à la fin de l’algorithme, tout le monde finit par être en couple.
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.


De manière plus formelle, raisonnons par l’absurde et supposons qu’il existe une instabilité dans l’un des mariages. Alors, par définition, cela signifie qu’il existe tels que préfère à et préfère à . Comme et sont engagés ensemble, d’après l’algorithme, cela signifie que la dernière proposition de a été faite à . Y a-t-il eu une proposition de à  ?
·      S’il n’y en a pas eu, alors cela signifie que s’était déjà engagé avec une autre femme qui ne l’a pas rejeté, soit (car ils sont engagés ensemble à la fin de l’algorithme), et donc que préfère à . On a alors une contradiction avec l’affirmation de départ.
·      S’il y en a eu une, alors cela signifie que s’est fait rejeter par , car ils ne sont pas engagés ensemble. Donc, cela induit que a reçu une proposition d’un homme (qu’elle a acceptée). Ainsi, on en déduit que préfère à . Or, est le partenaire de à la fin de l’algorithme. Donc :
- Soit  ;
- Soit préfère à .
Mais, dans les deux cas, on obtient que préfère à . On a alors une contradiction avec l’affirmation de départ.
Par conséquent, dans tous les cas, on aboutit à une contradiction de l’affirmation de départ. C’est donc que celle-ci est fausse et qu’il n’y a pas d’instabilité dans l’un des mariages. Pour conclure, tous les mariages sont stables.
Le nombre d’itérations de la boucle de l’algorithme est d’au plus
Pour montrer cela, on va exhiber une quantité (entière) qui croît strictement à chaque itération de l’algorithme. Soient l’ensemble des couples a fait une proposition à entre le début de l’algorithme et la itération, et le cardinal de l’ensemble . De manière équivalente, l’ensemble correspond à l’ensemble des propositions qui ont été faites entre le début de l’algorithme et la itération. Alors, on a :
·      ;
·     .
Ainsi, il ne peut y avoir au plus que itérations dans l’algorithme.

Pseudo-code[modifier | modifier le code]

Entrée : Deux ensembles finis M (d’hommes) et W (de femmes) de cardinal n ;
Sortie : Un ensemble S de couples engagés (homme ; femme) ;
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
    }
    Retourner l’ensemble S des couples engagés
}

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 l'ordre des préférences respectif est :

 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 présenté ci-dessus en exemple de pseudo-code donne la première solution.

Applications[modifier | modifier le code]

L'Admission Post-Bac permettant entre 2009 et 2017 d'affecter les lycéens de terminale à la première année des formations de l'enseignement supérieur en France, utilisait l'algorithme de Gale-Shapley[5], les formations dans le rôle des prétendants et les étudiants dans celui des choisisseurs[6].

Implémentation dans les logiciels[modifier | modifier le code]

  • R : L'algorithme de Gale-Shapley pour le problème des mariages stables et le problème de l'admission à l'université sont disponibles dans le paquet matchingMarkets[7],[8].
  • API : L'API MatchingTools fournit une interface de programmation applicative pour l'algorithme.[9]
  • Python : L'algorithme de Gale-Shapley est disponible dans la librairie QuantEcon/MatchingMarkets.py

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).
  3. (en) Numberphile, « Stable Marriage Problem », sur Youtube.com, (consulté le 7 octobre 2014)
  4. . Donald Knuth, « Mariages Stables et leurs relations avec d'autres problèmes combinatoires », Montréal, Les Presses de l'Université de Montréal, (ISBN 2-7606-0529-9), p. 106
  5. https://www.lemonde.fr/idees/article/2017/12/06/cedric-villani-ce-qui-a-bugge-dans-apb-ce-n-est-pas-le-logiciel-mais-bien-l-etat_5225204_3232.html?xtmc=apb&xtcr=1
  6. https://www.ccomptes.fr/sites/default/files/2017-10/20171019-rapport-admission-post-bac_0.pdf "Admission Post-Bac et accès à l'Enseignement Supérieur", rapport de la Cour des Comptes, Annexe 4 page 118.
  7. T. Klein, « Analysis of Stable Matchings in R: Package matchingMarkets », Vignette to R Package matchingMarkets,‎ (lire en ligne)
  8. « matchingMarkets: Analysis of Stable Matchings », R Project
  9. « MatchingTools API »

Articles connexes[modifier | modifier le code]