Accueil🇫🇷Chercher

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.

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] - [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 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
}

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[5] :

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

contient tous les hommes et toutes les femmes : 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.

n’a pas d’instabilité : 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é.

L’algorithme renvoie : Raisonnons par l’absurde et supposons qu’il existe une exécution de l’algorithme qui retourne un ensemble . Alors, il existe un homme tel que . On en déduit immédiatement que a été rejeté par une femme au cours de l’algorithme (car sinon, serait engagé avec une femme , et d’après l’algorithme, serait alors une partenaire stable de préférée à , ce qui est impossible par définition). Considérons le premier moment où un certain homme a été rejeté par une certaine femme valide. Alors, d’après l’algorithme, comme fait sa première proposition à , on a nécessairement que : . En effet sinon, cela signifie que préfère à , 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 par :

  • Soit a fait une proposition à qui est déjà engagée avec un homme à l’instant et préfère à ;
  • Soit était engagée avec et a reçu à l’instant une proposition d’un homme qu’elle a acceptée. Donc, cela signifie que préfère à .

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

  • ;
  • ;
  • préfère à ;
  • préfère à .

Donc, par définition, est une instabilité pour . Or, est défini sans instabilité. On aboutit donc à une contradiction avec la définition de . 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 . Par conséquent, toutes les exécutions de cet algorithme retournent .

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 est un partenaire stable d’une femme s’il existe un ensemble de couples engagés (homme ; femme) contenant tous les individus et sans instabilité qui contient .
  • Le pire partenaire de , noté , est l’unique partenaire stable de tel que :
    , est un partenaire stable de préfère à

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

Raisonnons par l’absurde et supposons qu’il existe tel que : . Alors, par définition de , il existe un partenaire stable de tel que préfère à . En effet, sinon, serait le partenaire stable le moins aimé de , et donc on aurait : . Comme est un partenaire valide de , par définition, il existe un ensemble de couples engagés sans instabilité tel que : . Soit la femme engagée avec dans , c’est-à-dire telle que : . Donc, est une partenaire stable de et on a : . Par ailleurs, comme , on en déduit que et donc que préfère à . Pour résumé, on a donc :

  • ;
  • ;
  • préfère à ;
  • préfère à .

Donc, par définition, est une instabilité pour . Or, est défini sans instabilité. On aboutit donc à une contradiction avec la définition de . 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 avec un homme différent de son pire partenaire. Par conséquent, dans l’ensemble , 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 en temps, où 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 et sont des tableaux d'entiers de taille contenant les entiers de 1 jusqu'à dans cet ordre pour les deux tableaux. Ces deux tableaux représentent les ensembles d'hommes et de femmes considérés pour le problème des mariages stables.

- Les éléments et sont des tableaux bidimensionnels d'entiers de taille et contenant des entiers entre 1 et pour les deux tableaux. Ils représentent la famille des préférences de tous les hommes de (pour ) et la famille des préférences de toutes les femmes de (pour ). Chaque ligne de l'un des deux tableaux correspond à la relation de préférence d'un individu. Si et , alors est l'entier correspondant à la -ème femme préférée de dans . Il en est de même pour .

- L'élément est une liste chaînée stockant l'ensemble des hommes de qui sont célibataires (identifiés par leur nombre dans ).

- L'élément est un tableau d'entiers de taille . Il permet de déterminer à quelle femme un homme doit se présenter au prochain tour de boucle de la fonction. Ainsi, si , est le rang dans la relation de préférence de l'homme associé à dans . En d'autres termes, à chaque tour de boucle de la fonction, l'homme associé à dans (si c'est lui qui est choisi) propose à la femme dans associée à . est ensuite incrémenté de 1 à la fin du tour de boucle. Au début de la fonction, avant d'entrer dans la boucle, 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 est un tableau d'entiers de taille . Il stocke les partenaires actuels (identifiés par leur nombre dans ) de toutes les femmes de (identifiées par leur nombre dans ). Donc, si , est le nombre associé au partenaire de la femme associée à , 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, 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 n'est pas vide, c'est-à-dire tant qu'il reste au moins un homme célibataire, on choisit un tel homme ( dans la fonction). On considère la femme qu'il préfère parmi toutes celles à qui il ne s'est pas proposé ( dans la fonction).

- Si est célibataire , alors et s'engagent ensemble et n'est plus célibataire, donc il quitte la liste .

- Sinon, est engagée avec un autre homme ( dans la fonction). On recherche alors son partenaire préféré entre et . Pour cela, on recherche le plus petit indice tel que soit ou , par définition de . Si elle préfère à , alors s'engage avec et quitte la liste car il n'est plus célibataire alors que devient célibataire et rejoint la liste . Si préfère à , alors rien ne change, reste engagée avec et reste célibataire, donc dans la liste .

Pour finir, quelle que soit la situation de vis-à-vis de à la fin du tour de boucle (célibataire ou engagé avec ), 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 . La fonction rend enfin le tableau , 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 .

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

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, (consulté le ).
  4. . Donald Knuth, Mariages Stables et leurs relations avec d'autres problèmes combinatoires, Montréal, Les Presses de l'Université de Montréal, , 106 p. (ISBN 978-2-7606-0529-9, présentation en ligne).
  5. (en) Jon Kleinberg et Éva Tardos, Algorithm Design, Addison Wesley, , 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,‎ (lire en ligne).
  7. « matchingMarkets: Analysis of Stable Matchings », R Project.
  8. « MatchingTools API ».
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.