Algorithme de Gale et Shapley

En informatique, l'algorithme de Gale et Shapley est un algorithme qui résout le problème des mariages stables. Il est nommé d'après ses inventeurs David Gale et Lloyd Shapley tous deux mathématiciens et économistes. Dans ce problème, il y a un même nombre d'hommes et de femmes. Chaque homme a des préférences sur les femmes : chaque femme a des préférences sur les hommes. L'objectif est de marier hommes et femmes de façon stable, c'est-à-dire sans qu'il y ait un homme et une femme qui préféreraient quitter leurs partenaires pour se mettre ensemble. Le principe de l'algorithme de Gale et Shapley est le suivant : chaque homme fait des propositions en commençant par la femme qu'il préfère ; les femmes, elles, disposent en fonction de leurs propres préférences.

Principe et algorithme

David Gale

Lloyd Shapley

Principe et définitions

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.

Afin d'écrire formellement l'algorithme de Gale-Shapley, on définit ci-dessous les notions intervenant dans l'écriture de l'algorithme et dans son étude. Soient ${\displaystyle \textstyle M}$ un ensemble d’hommes et ${\displaystyle \textstyle W}$ un ensemble de femmes tous deux de cardinal ${\displaystyle \textstyle n}$ et supposés disjoints.

• On appelle ensemble de couples engagés un ensemble ${\displaystyle \textstyle S\subset M\times W}$ tel que tout élément de ${\displaystyle \textstyle M\cup W}$ n’apparaît au plus que dans un seul couple de ${\displaystyle \textstyle S}$. Cela revient à dire que la polygamie n’est pas prise en compte dans l’étude des problèmes des mariages stables.
• Pour tout homme ${\displaystyle \textstyle m\in M}$, on appelle relation de préférence de ${\displaystyle \textstyle m}$ une relation d’ordre total stricte sur ${\displaystyle \textstyle W}$, notée ${\displaystyle \textstyle >_{m}}$. Si ${\displaystyle \textstyle w\in W}$ et ${\displaystyle \textstyle w'\in W}$, on dit que ${\displaystyle \textstyle m}$ préfère ${\displaystyle \textstyle w}$ à ${\displaystyle \textstyle w'}$ si : ${\displaystyle \textstyle w>_{m}w'}$. On définit, pour toute femme ${\displaystyle \textstyle w\in W}$, la relation de préférence de ${\displaystyle \textstyle w}$, notée ${\displaystyle \textstyle >_{w}}$, comme ci-dessus.

On note ${\displaystyle \textstyle L}$ la famille des relations de préférence de tous les hommes de ${\displaystyle \textstyle M}$ et de toutes les femmes de ${\displaystyle \textstyle W}$, c’est-à-dire que : ${\displaystyle \textstyle L=((>_{m})_{m\in M}\,;(>_{w})_{w\in W})}$

• Étant donnés une famille ${\displaystyle \textstyle L}$ et un ensemble de couples engagés ${\displaystyle \textstyle S}$, on dit qu’un couple ${\displaystyle \textstyle (m;w')\in M\times W}$ est une instabilité pour ${\displaystyle \textstyle S}$ s’il existe des couples ${\displaystyle \textstyle (m;w)\in S}$ et ${\displaystyle \textstyle (m';w')\in S}$ tels que : ${\displaystyle \textstyle w'>_{m}w}$ et ${\displaystyle \textstyle m>_{w'}m'}$.

Pseudo-code

Entrée : Deux ensembles finis M (d’hommes) et W (de femmes) de cardinal n ;
         Une famille L de relations de préférences ;
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
}

Exemple d'exécution

Propriétés

Cet algorithme assure que, étant donnés un ensemble d’hommes ${\displaystyle \textstyle M}$, un ensemble de femmes ${\displaystyle \textstyle W}$ tous deux de cardinal ${\displaystyle \textstyle n}$ et supposés disjoints, une famille ${\displaystyle \textstyle L}$ de relations de préférences et ${\displaystyle \textstyle S}$ un ensemble des couples engagés (homme ; femme) renvoyé par l’algorithme[5] :

Au plus n^2 itérations

Le nombre d’itérations de la boucle de l’algorithme est d’au plus ${\displaystyle \textstyle n^{2}}$ : On commence par faire quelques remarques qui découlent immédiatement d’observations de l’algorithme de Gale-Shapley :

• Toute femme ${\displaystyle \textstyle w\in W}$ reste engagée jusqu’à la fin d’une exécution de l’algorithme dès qu’elle a reçu une première proposition d’engagement. De plus, la liste de partenaires de ${\displaystyle \textstyle w}$ engagés avec elle au cours d’une exécution de l’algorithme devient « de mieux en mieux » au sens de la relation de préférence de ${\displaystyle \textstyle w}$. En d’autres termes, à chaque fois que ${\displaystyle \textstyle w}$ change de partenaire ${\displaystyle \textstyle m\in M}$ pour un partenaire ${\displaystyle \textstyle m'\in M}$ au cours d’une exécution de l’algorithme, on a : ${\displaystyle \textstyle m'>_{w}m}$.
• Tout homme ${\displaystyle \textstyle m\in M}$ peut alterner entre engagement et célibat, du début d’une exécution de l’algorithme jusqu’à la fin de cette dernière. De plus, la liste de partenaires de ${\displaystyle \textstyle m}$ engagées avec lui au cours d’une exécution de l’algorithme devient « de pire en pire » au sens de la relation de préférence de ${\displaystyle \textstyle m}$. En d’autres termes, à chaque fois que ${\displaystyle \textstyle m}$ change de partenaire ${\displaystyle \textstyle w\in W}$ pour une partenaire ${\displaystyle \textstyle w'\in W}$ au cours d’une exécution de l’algorithme, on a : ${\displaystyle \textstyle w>_{m}w'}$.

Afin de montrer la propriété énoncée ci-dessus, on va exhiber une quantité (entière) qui croît strictement à chaque itération de l’algorithme. Soient ${\displaystyle \textstyle C(t)}$ l’ensemble des couples ${\displaystyle \textstyle (m;w)}$ où ${\displaystyle \textstyle m}$ a fait une proposition à ${\displaystyle \textstyle w}$ entre le début de l’algorithme et la ${\displaystyle \textstyle t^{\text{ème}}}$ itération, et ${\displaystyle \textstyle n(t)}$ le cardinal de l’ensemble ${\displaystyle \textstyle C(t)}$. De manière équivalente, l’ensemble ${\displaystyle \textstyle C(t)}$ correspond à l’ensemble des propositions qui ont été faites entre le début de l’algorithme et la ${\displaystyle \textstyle t^{\text{e}}}$ itération. Alors, on a :

• ${\displaystyle \forall }$ ${\displaystyle \textstyle t,}$ ${\displaystyle n(t)<n(t+1)}$ ;
• ${\displaystyle \forall }$ ${\displaystyle \textstyle t,}$ ${\displaystyle n(t)\leq n^{2}}$.

Ainsi, il ne peut y avoir au plus que ${\displaystyle \textstyle n^{2}}$ itérations dans 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 ${\displaystyle \textstyle M\cup \textstyle W}$apparaît exactement une et une seule fois dans un couple de ${\displaystyle \textstyle S}$. Pour cela, on va montrer que la propriété

${\displaystyle \textstyle (P)}$ : « ${\displaystyle \forall }$ homme ${\displaystyle \textstyle m\in \textstyle M}$, ${\displaystyle \textstyle m}$ est célibataire ${\displaystyle \Rightarrow \textstyle m}$ ne s’est pas proposé à toutes les femmes ${\displaystyle \textstyle w\in \textstyle W}$» est un invariant de l’algorithme. Raisonnons par l’absurde et supposons que ${\displaystyle \textstyle (P)}$ ne soit pas un invariant. Alors, ${\displaystyle \textstyle (P)}$ est fausse à un instant donné, c’est-à-dire à un tour de boucle donné. Alors : ${\displaystyle \exists }$ un homme ${\displaystyle \textstyle m_{0}}$ ${\displaystyle \in \textstyle M}$, ${\displaystyle \textstyle m_{0}}$ est célibataire ${\displaystyle \land }$ ${\displaystyle \textstyle m_{0}}$ s’est proposé à toutes les femmes ${\displaystyle \textstyle w\in \textstyle W}$. Donc, nécessairement, toutes les femmes ${\displaystyle \textstyle w\in \textstyle W}$ sont engagées avec d’autres hommes. Or, les ensembles ${\displaystyle \textstyle M}$ et ${\displaystyle \textstyle W}$ é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-dessus), cela signifie que ${\displaystyle \textstyle m_{0}}$ est engagé avec une femme. On a donc une contradiction avec l’affirmation de départ : « ${\displaystyle \textstyle (P)}$ n’est pas un invariant ». C’est donc que ${\displaystyle \textstyle (P)}$ 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 : ${\displaystyle \forall }$ homme ${\displaystyle \textstyle m\in \textstyle M}$, ${\displaystyle \textstyle m}$ est engagé ${\displaystyle \lor }$ ${\displaystyle \textstyle m}$ s’est proposé à toutes les femmes ${\displaystyle \textstyle w\in \textstyle W}$. Soit ${\displaystyle \textstyle m\in \textstyle M}$. Si ${\displaystyle \textstyle m}$ s’est proposé à toutes les femmes ${\displaystyle \textstyle w\in \textstyle W}$, alors comme ${\displaystyle \textstyle (P)}$ est un invariant de cet algorithme, il est vrai à la fin de ce dernier. Donc, en particulier, comme : « ${\displaystyle \textstyle m}$ est célibataire ${\displaystyle \Rightarrow \textstyle m}$ ne s’est pas proposé à toutes les femmes ${\displaystyle \textstyle w\in \textstyle W}$ », la contraposée nous affirme que ${\displaystyle \textstyle m}$ est engagé. Par conséquent, à la fin de l’algorithme, tous les hommes ${\displaystyle \textstyle m\in \textstyle M}$ sont engagés. Pour conclure, comme les ensembles ${\displaystyle \textstyle M}$ et ${\displaystyle \textstyle W}$ 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 ${\displaystyle \textstyle (m;w),(m';w')\in \textstyle S}$ tels que ${\displaystyle \textstyle m}$ préfère ${\displaystyle \textstyle w'}$ à ${\displaystyle \textstyle w}$ et ${\displaystyle \textstyle w'}$ préfère ${\displaystyle \textstyle m}$ à ${\displaystyle \textstyle m'}$. Comme ${\displaystyle \textstyle m}$ et ${\displaystyle \textstyle w}$ sont engagés ensemble, d’après l’algorithme, cela signifie que la dernière proposition de ${\displaystyle \textstyle m}$ a été faite à ${\displaystyle \textstyle w}$. Y a-t-il eu une proposition de ${\displaystyle \textstyle m}$ à ${\displaystyle \textstyle w'}$ ?

• S’il n’y en a pas eu, alors cela signifie que ${\displaystyle \textstyle m}$ s’était déjà engagé avec une autre femme qui ne l’a pas rejeté, soit ${\displaystyle \textstyle w}$ (car ils sont engagés ensemble à la fin de l’algorithme), et donc que ${\displaystyle \textstyle m}$ préfère ${\displaystyle \textstyle w}$ à ${\displaystyle \textstyle w'}$. On a alors une contradiction avec l’affirmation de départ.
• S’il y en a eu une, alors cela signifie que ${\displaystyle \textstyle m}$ s’est fait rejeter par ${\displaystyle \textstyle w'}$, car ils ne sont pas engagés ensemble. Donc, cela induit que ${\displaystyle \textstyle w'}$ a reçu une proposition d’un homme ${\displaystyle \textstyle m''\in \textstyle M}$ (qu’elle a acceptée). Ainsi, on en déduit que ${\displaystyle \textstyle w'}$ préfère ${\displaystyle \textstyle m''}$ à ${\displaystyle \textstyle m}$. Or, ${\displaystyle \textstyle m'}$ est le partenaire de ${\displaystyle \textstyle w'}$ à la fin de l’algorithme. Donc :
• Soit ${\displaystyle \textstyle m'=m''}$ ;
• Soit ${\displaystyle \textstyle w'}$ préfère ${\displaystyle \textstyle m'}$ à ${\displaystyle \textstyle m''}$.

Mais, dans les deux cas, on obtient que ${\displaystyle \textstyle w'}$ préfère ${\displaystyle \textstyle m'}$ à ${\displaystyle \textstyle m}$. 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.

Optimalité de la solution

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.

En reprenant les mêmes notations que dans les sections ci-dessus, nous allons montrer que[5] :

Chaque homme est engagé avec sa partenaire préférée parmi toutes ses partenaires stables

On commence par définir quelques notions :

• On dit qu’une femme ${\displaystyle \textstyle w\in W}$ est une partenaire stable d’un homme ${\displaystyle \textstyle m\in M}$ s’il existe un ensemble ${\displaystyle \textstyle S}$ de couples engagés (homme ; femme) contenant tous les individus et sans instabilité qui contient ${\displaystyle \textstyle (m;w)}$.
• La meilleure partenaire de ${\displaystyle \textstyle m\in M}$, notée ${\displaystyle \textstyle best(m)\in W}$, est l’unique partenaire stable de ${\displaystyle \textstyle m}$ telle que :
  ${\displaystyle \forall }$ ${\displaystyle \textstyle w\in W\setminus \{best(m)\}}$, ${\displaystyle \textstyle (w}$ est une partenaire stable de ${\displaystyle \textstyle m\Rightarrow m}$ préfère ${\displaystyle \textstyle best(m)}$ à ${\displaystyle \textstyle w)}$
• On note ${\displaystyle \textstyle S^{*}}$ = {(${\displaystyle \textstyle m}$ ; ${\displaystyle \textstyle best(m)}$) / ${\displaystyle \textstyle m\in M}$} en tant qu’ensemble de couples engagés.

On va montrer que toute exécution de l’algorithme de Gale-Shapley retourne ${\displaystyle \textstyle S^{*}}$.

${\displaystyle \textstyle S^{*}}$ contient tous les hommes et toutes les femmes : En effet, par définition de ${\displaystyle \textstyle S^{*}}$, il contient tous les hommes ${\displaystyle \textstyle m\in M}$. De plus, un homme ${\displaystyle \textstyle m\in M}$ a une unique meilleure partenaire ${\displaystyle \textstyle best(m)\in W}$ par définition. Donc, ${\displaystyle \textstyle m}$ ne peut être engagé avec deux femmes différentes. Il reste à voir qu’une même femme préférée ${\displaystyle \textstyle best(m)\in W}$, où ${\displaystyle \textstyle m\in M}$, ne peut être engagée avec un autre homme ${\displaystyle \textstyle m'\in M}$ différent de ${\displaystyle \textstyle m}$ dans ${\displaystyle \textstyle S^{*}}$. C’est immédiat par définition d’un ensemble de couples engagés. En effet sinon, on pourrait avoir : ${\displaystyle \textstyle best(m)=best(m')}$, c’est-à-dire que ${\displaystyle \textstyle m}$ et ${\displaystyle \textstyle m'}$ préfèreraient tous les deux la même femme. Mais alors, ${\displaystyle \textstyle best(m)}$ apparaîtrait au moins deux fois dans ${\displaystyle \textstyle S^{*}}$, ce qui est impossible car ${\displaystyle \textstyle S^{*}}$ est un ensemble de couples engagés. Ainsi, comme les ensembles ${\displaystyle \textstyle M}$ et ${\displaystyle \textstyle W}$ sont de même cardinal, ${\displaystyle \textstyle S^{*}}$ contient également toutes les femmes.

${\displaystyle \textstyle S^{*}}$ n’a pas d’instabilité : Raisonnons par l’absurde et supposons que ${\displaystyle \textstyle S^{*}}$ ait une instabilité ${\displaystyle \textstyle (m;w)\in M\times W}$ avec ${\displaystyle \textstyle w\neq best(m)}$. Alors, par définition d’une instabilité, cela signifie que ${\displaystyle \textstyle m}$ préfère ${\displaystyle \textstyle w}$ à ${\displaystyle \textstyle best(m)}$. Cela contredit la définition de ${\displaystyle \textstyle best(m)}$, car ${\displaystyle \textstyle w}$ est alors une partenaire stable de ${\displaystyle \textstyle m}$ préférée à ${\displaystyle \textstyle best(m)}$. Ainsi, ${\displaystyle \textstyle S^{*}}$ n’a pas d’instabilité.

L’algorithme renvoie ${\displaystyle \textstyle S^{*}}$ : Raisonnons par l’absurde et supposons qu’il existe une exécution de l’algorithme qui retourne un ensemble ${\displaystyle \textstyle S\neq S^{*}}$. Alors, il existe un homme ${\displaystyle \textstyle m\in M}$ tel que ${\displaystyle \textstyle (m;best(m))\notin S}$. On en déduit immédiatement que ${\displaystyle \textstyle m}$ a été rejeté par une femme au cours de l’algorithme (car sinon, ${\displaystyle \textstyle m}$ serait engagé avec une femme ${\displaystyle \textstyle w\neq best(m)}$, et d’après l’algorithme, ${\displaystyle \textstyle w}$ serait alors une partenaire stable de ${\displaystyle \textstyle m}$ préférée à ${\displaystyle \textstyle best(m)}$, ce qui est impossible par définition). Considérons le premier moment ${\displaystyle \textstyle t_{0}}$ où un certain homme ${\displaystyle \textstyle m_{0}\in M}$ a été rejeté par une certaine femme ${\displaystyle \textstyle w_{0}\in W}$ valide. Alors, d’après l’algorithme, comme ${\displaystyle \textstyle m_{0}}$ fait sa première proposition à ${\displaystyle \textstyle best(m_{0})}$, on a nécessairement que : ${\displaystyle \textstyle w_{0}=best(m_{0})}$. En effet sinon, cela signifie que ${\displaystyle \textstyle m_{0}}$ préfère ${\displaystyle \textstyle w_{0}}$ à ${\displaystyle \textstyle best(m_{0})}$, ce qui est impossible par définition de cette dernière. D’après l’algorithme, il y a deux cas possibles qui permettent le rejet de ${\displaystyle \textstyle m_{0}}$ par ${\displaystyle \textstyle best(m_{0})}$ :

• Soit ${\displaystyle \textstyle m_{0}}$ a fait une proposition à ${\displaystyle \textstyle best(m_{0})}$ qui est déjà engagée avec un homme ${\displaystyle \textstyle m'\in M}$ à l’instant ${\displaystyle \textstyle t_{0}}$ et ${\displaystyle \textstyle best(m_{0})}$ préfère ${\displaystyle \textstyle m'}$ à ${\displaystyle \textstyle m_{0}}$ ;
• Soit ${\displaystyle \textstyle best(m_{0})}$ était engagée avec ${\displaystyle \textstyle m_{0}}$ et a reçu à l’instant ${\displaystyle \textstyle t_{0}}$ une proposition d’un homme ${\displaystyle \textstyle m''\in M}$ qu’elle a acceptée. Donc, cela signifie que ${\displaystyle \textstyle best(m_{0})}$ préfère ${\displaystyle \textstyle m''}$ à ${\displaystyle \textstyle m_{0}}$.

Dans les deux cas, cela signifie qu’il existe un homme ${\displaystyle \textstyle m_{1}\in M}$ tel que ${\displaystyle \textstyle best(m_{0})}$ préfère ${\displaystyle \textstyle m_{1}}$ à ${\displaystyle \textstyle m_{0}}$. Après le rejet de ${\displaystyle \textstyle m_{0}}$ par ${\displaystyle \textstyle best(m_{0})}$ (donc à l’instant ${\displaystyle \textstyle t_{0}}$), on a alors l’engagement (homme ; femme) : ${\displaystyle \textstyle (m_{1};best(m_{0}))\in M\times W}$. Or, par définition de ${\displaystyle \textstyle best(m_{0})}$, c’est une partenaire stable pour ${\displaystyle \textstyle m_{0}}$. Donc, par définition d’une partenaire valide, cela induit l’existence d’un ensemble de couples engagés (homme ; femme) ${\displaystyle \textstyle S'}$ sans instabilité, tel que : ${\displaystyle \textstyle (m_{0};best(m_{0}))\in S'}$. Soit ${\displaystyle \textstyle w_{1}\in W}$ la femme engagée avec ${\displaystyle \textstyle m_{1}}$ dans ${\displaystyle \textstyle S'}$, c’est-à-dire telle que : ${\displaystyle \textstyle (m_{1};w_{1})\in S'}$. D’après l’algorithme, on a : ${\displaystyle \textstyle w_{1}\neq best(m_{0})}$. On reprend l’étude de l’exécution de l’algorithme de Gale-Shapley permettant d’obtenir l’ensemble ${\displaystyle \textstyle S}$. Comme ${\displaystyle \textstyle m_{0}}$ est le premier homme à être rejeté au cours de l’exécution de l’algorithme (car associé à l’instant ${\displaystyle \textstyle t_{0}}$) et qu’à la fin de l’instant ${\displaystyle \textstyle t_{0}}$, ${\displaystyle \textstyle m_{1}}$ est engagé avec ${\displaystyle \textstyle best(m_{0})}$, on en déduit que ${\displaystyle \textstyle m_{1}}$ n’a pas été rejeté avant l’instant ${\displaystyle \textstyle t_{0}}$, et donc que sa première proposition a été faite à ${\displaystyle \textstyle best(m_{0})}$. Ainsi, ${\displaystyle \textstyle m_{1}}$ préfère ${\displaystyle \textstyle best(m_{0})}$ à ${\displaystyle \textstyle w_{1}}$. Pour résumé, on a donc :

• ${\displaystyle \textstyle (m_{1};w_{1})\in S'}$ ;
• ${\displaystyle \textstyle (m_{0};best(m_{0}))\in S'}$ ;
• ${\displaystyle \textstyle best(m_{0})}$ préfère ${\displaystyle \textstyle m_{1}}$ à ${\displaystyle \textstyle m_{0}}$ ;
• ${\displaystyle \textstyle m_{1}}$ préfère ${\displaystyle \textstyle best(m_{0})}$ à ${\displaystyle \textstyle w_{1}}$.

Donc, par définition, ${\displaystyle \textstyle (m_{1};best(m_{0}))}$ est une instabilité pour ${\displaystyle \textstyle S'}$. Or, ${\displaystyle \textstyle S'}$ est défini sans instabilité. On aboutit donc à une contradiction avec la définition de ${\displaystyle \textstyle S'}$. C’est donc que l’hypothèse de départ est fausse et qu’il n’y a pas d’exécution de l’algorithme de Gale-Shapley qui ne retourne un ensemble de couples engagés (homme ; femme) différent de ${\displaystyle \textstyle S^{*}}$. Par conséquent, toutes les exécutions de cet algorithme retournent ${\displaystyle \textstyle S^{*}}$.

Chaque femme est engagée avec son partenaire le moins aimé parmi tous ses partenaires stables

On commence par définir quelques notions :

• On dit qu’un homme ${\displaystyle \textstyle m\in M}$ est un partenaire stable d’une femme ${\displaystyle \textstyle w\in W}$ s’il existe un ensemble ${\displaystyle \textstyle S}$ de couples engagés (homme ; femme) contenant tous les individus et sans instabilité qui contient ${\displaystyle \textstyle (m;w)}$.
• Le pire partenaire de ${\displaystyle \textstyle w\in W}$, noté ${\displaystyle \textstyle worst(w)\in M}$, est l’unique partenaire stable de ${\displaystyle \textstyle w}$ tel que :
  ${\displaystyle \forall }$ ${\displaystyle \textstyle m\in M\setminus \{worst(w)\}}$, ${\displaystyle \textstyle (m}$ est un partenaire stable de ${\displaystyle \textstyle w\Rightarrow w}$ préfère ${\displaystyle \textstyle m}$ à ${\displaystyle \textstyle worst(w))}$

On va montrer que, dans l’ensemble ${\displaystyle \textstyle S^{*}}$, chaque femme est engagée avec son pire partenaire parmi ses partenaires stables.

Raisonnons par l’absurde et supposons qu’il existe ${\displaystyle \textstyle (m;w)\in S^{*}}$ tel que : ${\displaystyle \textstyle m\neq worst(w)}$. Alors, par définition de ${\displaystyle \textstyle worst(w)}$, il existe un partenaire stable ${\displaystyle \textstyle m'\in M}$ de ${\displaystyle \textstyle w}$ tel que ${\displaystyle \textstyle w}$ préfère ${\displaystyle \textstyle m}$ à ${\displaystyle \textstyle m'}$. En effet, sinon, ${\displaystyle \textstyle m}$ serait le partenaire stable le moins aimé de ${\displaystyle \textstyle w}$, et donc on aurait : ${\displaystyle \textstyle m=worst(w)}$. Comme ${\displaystyle \textstyle m'}$ est un partenaire valide de ${\displaystyle \textstyle w}$, par définition, il existe un ensemble de couples engagés ${\displaystyle \textstyle S'}$ sans instabilité tel que : ${\displaystyle \textstyle (m';w)\in S'}$. Soit ${\displaystyle \textstyle w'\in W}$ la femme engagée avec ${\displaystyle \textstyle m}$ dans ${\displaystyle \textstyle S'}$, c’est-à-dire telle que : ${\displaystyle \textstyle (m;w')\in S'}$. Donc, ${\displaystyle \textstyle w'}$ est une partenaire stable de ${\displaystyle \textstyle m}$ et on a : ${\displaystyle \textstyle w'\neq w}$. Par ailleurs, comme ${\displaystyle \textstyle (m;w)\in S^{*}}$, on en déduit que ${\displaystyle \textstyle w=best(m)}$ et donc que ${\displaystyle \textstyle m}$ préfère ${\displaystyle \textstyle w}$ à ${\displaystyle \textstyle w'}$. Pour résumé, on a donc :

• ${\displaystyle \textstyle (m';w)\in S'}$ ;
• ${\displaystyle \textstyle (m;w')\in S'}$ ;
• ${\displaystyle \textstyle w}$ préfère ${\displaystyle \textstyle m}$ à ${\displaystyle \textstyle m'}$ ;
• ${\displaystyle \textstyle m}$ préfère ${\displaystyle \textstyle w}$ à ${\displaystyle \textstyle w'}$.

Donc, par définition, ${\displaystyle \textstyle (m;w)}$ est une instabilité pour ${\displaystyle \textstyle S'}$. Or, ${\displaystyle \textstyle S'}$ est défini sans instabilité. On aboutit donc à une contradiction avec la définition de ${\displaystyle \textstyle S'}$. C’est donc que l’hypothèse de départ est fausse et qu’il n’y a pas de femme qui ne soit engagée dans ${\displaystyle \textstyle S^{*}}$ avec un homme différent de son pire partenaire. Par conséquent, dans l’ensemble ${\displaystyle \textstyle S^{*}}$, chaque femme est engagée avec son pire partenaire parmi ses partenaires stables.

Implémentation

L'algorithme de Gale-Shapley peut être implémenté par exemple en Java. Il a une complexité de ${\displaystyle \textstyle O(n^{2})}$ en temps, où ${\displaystyle \textstyle n}$ est le nombre d'hommes et de femmes considéré pour le problème des mariages stables[5] :

public static int[] Gale_Shapley(int[] M, int[] W, int[][] MPref, int[][] WPref) {
		int n = M.length;
		LinkedList<Integer> Libre= new LinkedList<Integer>();
		int[] Prochain = new int[n] ;
		int[] Actuel = new int[n];
		for (int i = 0 ; i<n ; i++) {
			Libre.add(M[i]);
			Prochain[i] = 0;
			Actuel[i] = 0;
		}
		while (!Libre.isEmpty()) {
			int m = Libre.get(0);
			int w = MPref[m-1][Prochain[m-1]];
			if (Actuel[w-1] == 0) {
				Actuel[w-1] = m;
				Libre.remove(0);
			} else {		
				int i = 0;
				int m0 = Actuel[w-1];
				while (WPref[w-1][i] != m && WPref[w-1][i] != m0) {
					i++;
				}
				if (WPref[w-1][i] == m) {
					Actuel[w-1] = m;
					Libre.remove(0);
					Libre.add(m0);
				}
			}
			Prochain[m-1]++;
		}
		return Actuel;
	}

On décrit ci-dessous les différents objets intervenant dans cette fonction, et on explique son fonctionnement.

Éléments de la fonction Gale-Shapley

• Les éléments ${\displaystyle \textstyle M}$ et ${\displaystyle \textstyle W}$ sont des tableaux d'entiers de taille ${\displaystyle \textstyle n}$ contenant les entiers de 1 jusqu'à ${\displaystyle \textstyle n}$ dans cet ordre pour les deux tableaux. Ces deux tableaux représentent les ensembles d'hommes ${\displaystyle \textstyle M'}$ et de femmes ${\displaystyle \textstyle W'}$ considérés pour le problème des mariages stables.
• Les éléments ${\displaystyle \textstyle MPref}$ et ${\displaystyle \textstyle WPref}$ sont des tableaux bidimensionnels d'entiers de taille ${\displaystyle \textstyle n\times n}$ et contenant des entiers entre 1 et ${\displaystyle \textstyle n}$ pour les deux tableaux. Ils représentent la famille des préférences de tous les hommes de ${\displaystyle \textstyle M'}$ (pour ${\displaystyle \textstyle MPref}$) et la famille des préférences de toutes les femmes de ${\displaystyle \textstyle W'}$ (pour ${\displaystyle \textstyle WPref}$). Chaque ligne de l'un des deux tableaux correspond à la relation de préférence d'un individu. Si ${\displaystyle \textstyle m\in \{1;\ldots ;n\}}$ et ${\displaystyle \textstyle i\in \{1;\ldots ;n\}}$, alors ${\displaystyle \textstyle MPref[m-1][i-1]}$ est l'entier ${\displaystyle \textstyle j\in \{1;\ldots ;n\}}$ correspondant à la ${\displaystyle \textstyle i}$-ème femme préférée de ${\displaystyle \textstyle m}$ dans ${\displaystyle \textstyle W'}$. Il en est de même pour ${\displaystyle \textstyle WPref}$.
• L'élément ${\displaystyle \textstyle Libre}$ est une liste chaînée stockant l'ensemble des hommes de ${\displaystyle \textstyle M'}$ qui sont célibataires (identifiés par leur nombre dans ${\displaystyle \textstyle M}$).
• L'élément ${\displaystyle \textstyle Prochain}$ est un tableau d'entiers de taille ${\displaystyle \textstyle n}$. Il permet de déterminer à quelle femme un homme doit se présenter au prochain tour de boucle de la fonction. Ainsi, si ${\displaystyle \textstyle m\in \{1;\ldots ;n\}}$, ${\displaystyle \textstyle Prochain[m-1]}$ est le rang dans la relation de préférence de l'homme associé à ${\displaystyle \textstyle m}$ dans ${\displaystyle \textstyle M'}$. En d'autres termes, à chaque tour de boucle de la fonction, l'homme associé à ${\displaystyle \textstyle m}$ dans ${\displaystyle \textstyle M'}$ (si c'est lui qui est choisi) propose à la femme dans ${\displaystyle \textstyle W'}$ associée à ${\displaystyle \textstyle MPref[m-1][Prochain[m-1]]}$. ${\displaystyle \textstyle Prochain[m-1]}$ est ensuite incrémenté de 1 à la fin du tour de boucle. Au début de la fonction, avant d'entrer dans la boucle, ${\displaystyle \textstyle Prochain}$ est donc initialisé avec des 0 partout (ce qui signifie que chaque homme va faire sa première proposition à la femme qu'il préfère).
• L'élément ${\displaystyle \textstyle Actuel}$ est un tableau d'entiers de taille ${\displaystyle \textstyle n}$. Il stocke les partenaires actuels (identifiés par leur nombre dans ${\displaystyle \textstyle M}$) de toutes les femmes de ${\displaystyle \textstyle W'}$ (identifiées par leur nombre dans ${\displaystyle \textstyle W}$). Donc, si ${\displaystyle \textstyle w\in \{1;\ldots ;n\}}$, ${\displaystyle \textstyle Actuel[w-1]}$ est le nombre associé au partenaire de la femme associée à ${\displaystyle \textstyle w}$, si cette femme est engagée avec un homme, ou 0 si elle célibataire. Au début de la fonction, avant d'entrer dans la boucle, ${\displaystyle \textstyle Actuel}$ est donc initialisé avec des 0 partout, car toutes les femmes sont célibataires.

Explication de la fonction Gale-Shapley

L'explication de la fonction est la suivante :

Tant que la liste ${\displaystyle \textstyle Libre}$ n'est pas vide, c'est-à-dire tant qu'il reste au moins un homme célibataire, on choisit un tel homme (${\displaystyle \textstyle m}$ dans la fonction). On considère la femme qu'il préfère parmi toutes celles à qui il ne s'est pas proposé (${\displaystyle \textstyle w}$ dans la fonction).

• Si ${\displaystyle \textstyle w}$ est célibataire ${\displaystyle \textstyle (Actuel[w-1]==0)}$, alors ${\displaystyle \textstyle m}$ et ${\displaystyle \textstyle w}$ s'engagent ensemble ${\displaystyle \textstyle (Actuel[w-1]=m)}$ et ${\displaystyle \textstyle m}$ n'est plus célibataire, donc il quitte la liste ${\displaystyle \textstyle Libre}$.
• Sinon, ${\displaystyle \textstyle w}$ est engagée avec un autre homme (${\displaystyle \textstyle m0}$ dans la fonction). On recherche alors son partenaire préféré entre ${\displaystyle \textstyle m}$ et ${\displaystyle \textstyle m0}$. Pour cela, on recherche le plus petit indice ${\displaystyle \textstyle i\in \{1;\ldots ;n\}}$ tel que ${\displaystyle \textstyle WPref[w-1][i-1]}$ soit ${\displaystyle \textstyle m}$ ou ${\displaystyle \textstyle m0}$, par définition de ${\displaystyle \textstyle WPref}$. Si elle préfère ${\displaystyle \textstyle m}$ à ${\displaystyle \textstyle m0}$ ${\displaystyle \textstyle (WPref[w-1][i-1]==m)}$, alors ${\displaystyle \textstyle w}$ s'engage avec ${\displaystyle \textstyle m}$ ${\displaystyle \textstyle (Actuel[w-1]=m)}$ et ${\displaystyle \textstyle m}$ quitte la liste ${\displaystyle \textstyle Libre}$ car il n'est plus célibataire alors que ${\displaystyle \textstyle m0}$ devient célibataire et rejoint la liste ${\displaystyle \textstyle Libre}$. Si ${\displaystyle \textstyle w}$ préfère ${\displaystyle \textstyle m0}$ à ${\displaystyle \textstyle m}$, alors rien ne change, ${\displaystyle \textstyle w}$ reste engagée avec ${\displaystyle \textstyle m0}$ et ${\displaystyle \textstyle m}$ reste célibataire, donc dans la liste ${\displaystyle \textstyle Libre}$.

Pour finir, quelle que soit la situation de ${\displaystyle \textstyle m}$ vis-à-vis de ${\displaystyle \textstyle w}$ à la fin du tour de boucle (célibataire ou engagé avec ${\displaystyle \textstyle w}$), s'il reste célibataire dans la suite de l'exécution de la fonction, alors il devra faire une nouvelle proposition à une autre femme qu'il aimera moins que ${\displaystyle \textstyle m}$ ${\displaystyle \textstyle (Prochain[m-1]++)}$. La fonction rend enfin le tableau ${\displaystyle \textstyle Actuel}$, ce qui permet de lire directement les couples formés.

On voit ainsi que l'on obtient bien une implémentation de l'algorithme de Gale-Shapley en Java. De plus, on remarque que le coût de cette fonction est bien en ${\displaystyle \textstyle O(n^{2})}$.

Bibliothèques

• 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[6],[7].
• API : L'API MatchingTools fournit une interface de programmation applicative pour l'algorithme[8].
• Python : L'algorithme de Gale-Shapley est disponible dans la librairie QuantEcon/MatchingMarkets.py
• Julia : L'algorithme de Gale-Shapley est disponible dans les librairies[9],[10].

Notes et références

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, 4 septembre 2014 (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, 1976, 106 p. (ISBN 978-2-7606-0529-9, présentation en ligne).
5. (en) Jon Kleinberg et Éva Tardos, Algorithm Design, Addison Wesley, 2005, 838 p. (ISBN 978-0-321-29535-4), p. 1.
6. T. Klein, « Analysis of Stable Matchings in R: Package matchingMarkets », Vignette to R Package matchingMarkets,‎ 2015 (lire en ligne).
7. « matchingMarkets: Analysis of Stable Matchings », R Project.
8. « MatchingTools API ».
9. « MatchingMarkets.jl »
10. « DeferredAcceptance.jl »