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

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]Modèle:,^[2]Modèle:,^[3]Modèle:,^[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 $M$ un ensemble d’hommes et $W$ un ensemble de femmes tous deux de cardinal $n$ et supposés disjoints.

On appelle ensemble de couples engagés un ensemble $S \subset M \times W$ tel que tout élément de $M \cup W$ n’apparaît au plus que dans un seul couple de $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 $m \in M$ , on appelle relation de préférence de $m$ une relation d’ordre total stricte sur $W$ , notée $>_{m}$ . Si $w \in W$ et $w^{'} \in W$ , on dit que $m$ préfère $w$ à $w^{'}$ si : $w >_{m} w^{'}$ . On définit, pour toute femme $w \in W$ , la relation de préférence de $w$ , notée $>_{w}$ , comme ci-dessus.

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

Étant donnés une famille $L$ et un ensemble de couples engagés $S$ , on dit qu’un couple $(m; w^{'}) \in M \times W$ est une instabilité pour $S$ s’il existe des couples $(m; w) \in S$ et $(m^{'}; w^{'}) \in S$ tels que : $w^{'} >_{m} w$ et $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

Modèle:Section vide ou incomplète

Propriétés

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

Au plus n² itérations

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

Toute femme $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 $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 $w$ . En d’autres termes, à chaque fois que $w$ change de partenaire $m \in M$ pour un partenaire $m^{'} \in M$ au cours d’une exécution de l’algorithme, on a : $m^{'} >_{w} m$ .
Tout homme $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 $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 $m$ . En d’autres termes, à chaque fois que $m$ change de partenaire $w \in W$ pour une partenaire $w^{'} \in W$ au cours d’une exécution de l’algorithme, on a : $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 $C (t)$ l’ensemble des couples $(m; w)$ où $m$ a fait une proposition à $w$ entre le début de l’algorithme et la $t^{ème}$ itération, et $n (t)$ le cardinal de l’ensemble $C (t)$ . De manière équivalente, l’ensemble $C (t)$ correspond à l’ensemble des propositions qui ont été faites entre le début de l’algorithme et la $t^{e}$ itération. Alors, on a :

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

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

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

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

Mais, dans les deux cas, on obtient que $w^{'}$ préfère $m^{'}$ à $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 $w \in W$ est une partenaire stable d’un homme $m \in M$ s’il existe un ensemble $S$ de couples engagés (homme ; femme) contenant tous les individus et sans instabilité qui contient $(m; w)$ .
La meilleure partenaire de $m \in M$ , notée $b e s t (m) \in W$ , est l’unique partenaire stable de $m$ telle que :
$\forall$ $w \in W ∖ {b e s t (m)}$ , $(w$ est une partenaire stable de $m \Rightarrow m$ préfère $b e s t (m)$ à $w)$
On note $S^{*}$ = {( $m$ ; $b e s t (m)$ ) / $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 $S^{*}$ .

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

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

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

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

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

$(m_{1}; w_{1}) \in S^{'}$ ;
$(m_{0}; b e s t (m_{0})) \in S^{'}$ ;
$b e s t (m_{0})$ préfère $m_{1}$ à $m_{0}$ ;
$m_{1}$ préfère $b e s t (m_{0})$ à $w_{1}$ .

Donc, par définition, $(m_{1}; b e s t (m_{0}))$ est une instabilité pour $S^{'}$ . Or, $S^{'}$ est défini sans instabilité. On aboutit donc à une contradiction avec la définition de $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 $S^{*}$ . Par conséquent, toutes les exécutions de cet algorithme retournent $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 $m \in M$ est un partenaire stable d’une femme $w \in W$ s’il existe un ensemble $S$ de couples engagés (homme ; femme) contenant tous les individus et sans instabilité qui contient $(m; w)$ .
Le pire partenaire de $w \in W$ , noté $w o r s t (w) \in M$ , est l’unique partenaire stable de $w$ tel que :
$\forall$ $m \in M ∖ {w o r s t (w)}$ , $(m$ est un partenaire stable de $w \Rightarrow w$ préfère $m$ à $w o r s t (w))$

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

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

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

Donc, par définition, $(m; w)$ est une instabilité pour $S^{'}$ . Or, $S^{'}$ est défini sans instabilité. On aboutit donc à une contradiction avec la définition de $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 $S^{*}$ avec un homme différent de son pire partenaire. Par conséquent, dans l’ensemble $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 $O (n^{2})$ en temps, où $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 $M$ et $W$ sont des tableaux d'entiers de taille $n$ contenant les entiers de 1 jusqu'à $n$ dans cet ordre pour les deux tableaux. Ces deux tableaux représentent les ensembles d'hommes $M^{'}$ et de femmes $W^{'}$ considérés pour le problème des mariages stables.
Les éléments $M P r e f$ et $W P r e f$ sont des tableaux bidimensionnels d'entiers de taille $n \times n$ et contenant des entiers entre 1 et $n$ pour les deux tableaux. Ils représentent la famille des préférences de tous les hommes de $M^{'}$ (pour $M P r e f$ ) et la famille des préférences de toutes les femmes de $W^{'}$ (pour $W P r e f$ ). Chaque ligne de l'un des deux tableaux correspond à la relation de préférence d'un individu. Si $m \in {1; \dots; n}$ et $i \in {1; \dots; n}$ , alors $M P r e f [m - 1] [i - 1]$ est l'entier $j \in {1; \dots; n}$ correspondant à la $i$ -ème femme préférée de $m$ dans $W^{'}$ . Il en est de même pour $W P r e f$ .
L'élément $L i b r e$ est une liste chaînée stockant l'ensemble des hommes de $M^{'}$ qui sont célibataires (identifiés par leur nombre dans $M$ ).
L'élément $P r o c h a i n$ est un tableau d'entiers de taille $n$ . Il permet de déterminer à quelle femme un homme doit se présenter au prochain tour de boucle de la fonction. Ainsi, si $m \in {1; \dots; n}$ , $P r o c h a i n [m - 1]$ est le rang dans la relation de préférence de l'homme associé à $m$ dans $M^{'}$ . En d'autres termes, à chaque tour de boucle de la fonction, l'homme associé à $m$ dans $M^{'}$ (si c'est lui qui est choisi) propose à la femme dans $W^{'}$ associée à $M P r e f [m - 1] [P r o c h a i n [m - 1]]$ . $P r o c h a i n [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, $P r o c h a i n$ 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 $A c t u e l$ est un tableau d'entiers de taille $n$ . Il stocke les partenaires actuels (identifiés par leur nombre dans $M$ ) de toutes les femmes de $W^{'}$ (identifiées par leur nombre dans $W$ ). Donc, si $w \in {1; \dots; n}$ , $A c t u e l [w - 1]$ est le nombre associé au partenaire de la femme associée à $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, $A c t u e l$ 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 $L i b r e$ n'est pas vide, c'est-à-dire tant qu'il reste au moins un homme célibataire, on choisit un tel homme ( $m$ dans la fonction). On considère la femme qu'il préfère parmi toutes celles à qui il ne s'est pas proposé ( $w$ dans la fonction).

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

Pour finir, quelle que soit la situation de $m$ vis-à-vis de $w$ à la fin du tour de boucle (célibataire ou engagé avec $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 $m$ $(P r o c h a i n [m - 1] + +)$ . La fonction rend enfin le tableau $A c t u e l$ , 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 $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]Modèle:,^[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]Modèle:,^[10].

Notes et références

Modèle:Références

Modèle:Portail

↑ Modèle:En D. Gale et L. S. Shapley, « College Admissions and the Stability of Marriage », dans Amer. Math. Month., vol. 69, 1962, Modèle:P..
↑ Modèle:En Modèle:Lien, « The Stable Marriage Problem », dans The Brandeis Review, vol. 12, 1992 (version en ligne).
↑ Modèle:Lien web.
↑ . Modèle:Ouvrage.
↑ ^5,0 ^5,1 et ^5,2 Modèle:Ouvrage.
↑ Modèle:Article.
↑ Modèle:Lien web.
↑ Modèle:Lien web.
↑ Modèle:Lien web
↑ Modèle:Lien web

[1] Modèle:En D. Gale et L. S. Shapley, « College Admissions and the Stability of Marriage », dans Amer. Math. Month., vol. 69, 1962, Modèle:P..

[2] Modèle:En Modèle:Lien, « The Stable Marriage Problem », dans The Brandeis Review, vol. 12, 1992 (version en ligne).

[3] Modèle:Lien web.

[4] . Modèle:Ouvrage.

[Propriétés-5] 5,0 ^5,1 et ^5,2 Modèle:Ouvrage.

[6] Modèle:Article.

[7] Modèle:Lien web.

[8] Modèle:Lien web.

[9] Modèle:Lien web

[10] Modèle:Lien web

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Algorithme de Gale et Shapley

Sommaire

Principe et algorithme

Principe et définitions

Pseudo-code

Exemple d'exécution

Propriétés

Au plus n² itérations

Tout le monde finit par être en couple

Les mariages sont stables

Optimalité de la solution

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

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

Implémentation

Éléments de la fonction Gale-Shapley

Explication de la fonction Gale-Shapley

Bibliothèques

Notes et références

Menu de navigation

Algorithme de Gale et Shapley

Principe et algorithme

Principe et définitions

Pseudo-code

Exemple d'exécution

Propriétés

Au plus n2 itérations

Tout le monde finit par être en couple

Les mariages sont stables

Optimalité de la solution

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

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

Implémentation

Éléments de la fonction Gale-Shapley

Explication de la fonction Gale-Shapley

Bibliothèques

Notes et références

Menu de navigation

Rechercher

Au plus n² itérations