Bonjour je bloque... Je dois modifier l'algo de Gale-Shapley pour calculer un mariage stable avec une paire que l'on force.

En pseudo-code, voilà l'algo pour calculer un mariage stable qui est optimal pour les hommes !

Et j'aimerai justement calculer le mariage avantageant les hommes et contenant une paire (m-w) que l'on force.

Mon problème c'est de définir cette condition tout en préservant la stabilité du mariage.

Il ne doit pas y avoir pour une paire (m-w) de paire bloquante cad un couple (m'-w) tq w préfère m' à m ou encore un couple (m-w') tq m préfére w' à w.

J'essaie de modifier l'algo JAVA de cette page. Je détaille mes tentatives en dessous

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
}

J'arrive sans problème à créer des mariages contenant une paire forcée mais ils ne sont pas stables (ils contiennent une paire bloquante).

Je force le couple avec m et w. Je fais refuser toute proposition demandant à se marier soit avec m soit avec w.

J'insère la condition que w' accepte de se marier si ce partenaire est meilleur que son partenaire actuel et aussi m (qui appartient à la paire forcée).

Comment savoir s'il existe un mariage contenant une paire (m-w) cad que l'algo s'arrête et qui ne boucle pas indéfiniment ?

Qu'est ce qui ne va pas dans ma démarche ?

-
Edité par LeCastorBricolor 1 avril 2019 à 18:06:41