problème des mariages stables

Trois hommes et trois femmes classent chacun les personnes de l'autre groupe. On cherche à former trois couples sans laisser deux personnes séparées qui préféreraient toutes deux être ensemble plutôt qu'avec leur partenaire attribué. Une telle paire mécontente rendrait l'appariement instable.

L'acceptation différée évite ce défaut par des choix provisoires. Une personne peut garder sa meilleure proposition du moment, puis en recevoir une qu'elle préfère. Les refus font avancer les propositions jusqu'à ce qu'aucun proposant ne soit libre.

Dans sa forme classique, le problème des mariages stables porte sur deux groupes de même taille : n hommes et n femmes. Chaque personne classe strictement toutes les personnes de l'autre groupe. Un appariement associe chaque homme à une femme. Il est stable lorsqu'il n'existe aucune paire non associée dont les deux membres préfèrent l'autre à leur partenaire actuel ; une telle paire serait dite bloquante.

L'algorithme d'acceptation différée de Gale et Shapley, proposé en 1962, construit toujours un appariement stable sous ces hypothèses. Tant qu'un homme est libre, il propose à la femme qu'il préfère parmi celles qui ne l'ont pas encore refusé. Chaque femme conserve provisoirement son meilleur candidat parmi son partenaire retenu et ses nouvelles propositions, puis rejette les autres. Comme chaque homme propose au plus une fois à chacune des n femmes, le processus s'arrête après au plus n² propositions.

Quand les hommes proposent, le résultat est optimal pour chacun d'eux parmi tous les appariements stables et, symétriquement, le moins favorable possible pour chaque femme parmi ces appariements. La version duale, où les femmes proposent, inverse ces deux propriétés. Les admissions universitaires et la formation de groupes conduisent à des variantes ; les préférences incomplètes, les ex æquo ou l'absence de deux groupes distincts exigent cependant d'adapter le modèle et parfois la notion de stabilité.

Prenons les hommes a, b, c et les femmes α, β, γ. Les préférences sont : a : α, β, γ ; b : α, γ, β ; c : β, α, γ ; α : c, b, a ; β : a, c, b ; γ : b, a, c. Les hommes proposent.

1. Au premier tour, a et b proposent à α, tandis que c propose à β. La femme α retient b et rejette a ; la femme β retient c.

2. L'homme a, redevenu libre, propose à β. Comme β classe a avant c, elle retient a et rejette c.

3. L'homme c propose alors à α. Comme α classe c avant b, elle retient c et rejette b. Enfin, b propose à γ, qui le retient. La figure récapitule ces quatre tours et les trois couples obtenus.

4. Le résultat est (a, β), (b, γ), (c, α), après six propositions. Contrôlons : a préférerait α, mais α préfère c ; b préférerait α, mais α préfère c ; c préférerait β, mais β préfère a. Les autres paires écartées ne sont pas souhaitées par l'homme concerné. Aucune paire n'est bloquante.

Pour une admission universitaire, les candidats classent des établissements et chaque établissement classe les candidatures. L'acceptation différée convient lorsque l'objectif est d'éviter qu'un candidat et un établissement se préfèrent mutuellement à leur affectation ; si les établissements disposent de plusieurs places, on utilise la variante avec capacités.

Pour former des binômes entre deux groupes, recueillez des classements avant de lancer les propositions. Si certaines associations sont interdites ou si les listes sont incomplètes, la variante à listes incomplètes, qui interdit les associations non acceptées, est préférable au modèle complet. Certaines personnes peuvent alors rester sans partenaire.

Pour contrôler un résultat, inspectez chaque paire non formée. Dès que ses deux membres préfèrent l'autre à leur partenaire, vous avez trouvé une paire bloquante et prouvé l'instabilité. Cette vérification teste la stabilité, mais ne dit pas si le résultat favorise le côté qui a proposé.

Appariement stable et appariement de poids maximal. Le premier exclut les paires bloquantes selon des classements individuels ; le second maximise une somme de scores. Un couple de personnes peut bloquer une solution pourtant excellente au total : les deux critères ne coïncident donc pas.

Mariages stables et colocataires stables. Le premier modèle sépare les participants en deux groupes et n'autorise que les couples croisés. Le problème des colocataires autorise des paires dans un groupe unique ; contrairement au modèle biparti classique, une solution stable n'y existe pas toujours.

Préférences ex æquo. Si une personne place deux candidats au même rang, l'ordre strict requis par le modèle classique manque. Le résultat peut dépendre du départage, et plusieurs définitions de stabilité deviennent possibles ; il faut annoncer la convention choisie avant d'appliquer l'algorithme.

Listes incomplètes. Une personne peut juger certains partenaires inacceptables. Une absence dans la liste ne doit pas être interprétée comme un dernier choix : on interdit cette paire et l'on accepte que l'appariement stable laisse éventuellement des personnes seules.

Stabilité sans unicité. L'algorithme garantit un appariement stable, pas nécessairement un résultat unique. Dans l'exemple, inverser le côté qui propose ne change pas les trois couples, mais d'autres listes produisent plusieurs appariements stables. Il faut préciser le côté proposant pour interpréter l'optimalité.

Préférences déclarées. La garantie porte sur les classements fournis à l'algorithme. Si une liste ne reflète pas les préférences utilisées pour juger le résultat, l'absence de paire bloquante dans les données ne suffit plus ; il faut d'abord valider ou mettre à jour ces listes.

algorithme — Replacer l'acceptation différée dans une suite finie d'instructions, avec un état provisoire et une condition d'arrêt.

R.O. et santé : les problèmes d'affectation — Observer comment des contraintes et des préférences deviennent un problème d'affectation dans un domaine concret.

analyse combinatoire — Situer la recherche d'appariements parmi les méthodes qui organisent, dénombrent et examinent des configurations finies.