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 vignette|David Gale vignette|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 D. Gale et L. S. Shapley, « College Admissions and the Stability of Marriage », dans Amer. Math. Month., vol. 69, 1962, . , « The Stable Marriage Problem », dans The Brandeis Review, vol. 12, 1992 (version en ligne)... ..

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 un ensemble d’hommes et un ensemble de femmes tous deux de cardinal et supposés disjoints. On appelle ensemble de couples engagés un ensemble tel que tout élément de n’apparaît au plus que dans un seul couple de . Cela revient à dire que la polygamie n’est pas prise en compte dans l’étude des problèmes des mariages stables. Pour tout homme , on appelle relation de préférence de une relation d’ordre total stricte sur , notée . Si et , on dit que préfère à si : . On définit, pour toute femme , la relation de préférence de , notée , comme ci-dessus.

On note la famille des relations de préférence de tous les hommes de et de toutes les femmes de , c’est-à-dire que : Étant donnés une famille et un ensemble de couples engagés , on dit qu’un couple est une instabilité pour s’il existe des couples et tels que : et .

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 , un ensemble de femmes tous deux de cardinal et supposés disjoints, une famille de relations de préférences et un ensemble des couples engagés (homme ; femme) renvoyé par l’algorithme. :

Au plus n2 itérations Le nombre d’itérations de la boucle de l’algorithme est d’au plus . On commence par faire quelques remarques qui découlent immédiatement d’observations de l’algorithme de Gale-Shapley : Toute femme 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 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 . En d’autres termes, à chaque fois que change de partenaire pour un partenaire au cours d’une exécution de l’algorithme, on a : . Tout homme 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 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 . En d’autres termes, à chaque fois que change de partenaire pour une partenaire au cours d’une exécution de l’algorithme, on a : .

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 l’ensemble des couples où 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.

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 , est célibataire 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-dessus), cela signifie que 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.

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 :

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 est une partenaire stable d’un homme s’il existe un ensemble de couples engagés (homme ; femme) contenant tous les individus et sans instabilité qui contient . La meilleure partenaire de , notée , est l’unique partenaire stable de telle que : , est une partenaire stable de préfère à On note = {( ; ) / } en tant qu’ensemble de couples engagés.

On va montrer que toute exécution de l’algorithme de Gale-Shapley retourne .

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

Raisonnons par l’absurde et supposons que ait une instabilité avec . Alors, par définition d’une instabilité, cela signifie que préfère à . Cela contredit la définition de , car est alors une partenaire stable de préférée à . Ainsi, n’a pas d’instabilité.