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