Wikipédia

Problème des colocataires

En mathématiques et en algorithmique, le problème des colocataires consiste à trouver, étant donné un nombre pair d'individus, une façon stable de former des paires d'individus. Chaque individu a classé les autres individus selon un ordre de préférence. La stabilité signifie qu'il n'existe pas deux couples (a,b) et (a',b') tels que a préférerait être avec a’ qu’avec b, et a’ préférerait être avec a qu'avec b’. Ce problème diffère du problème des mariages stables par le fait que les individus ne sont pas séparés en deux ensembles, les hommes et les femmes, tels qu'un homme ne peut s'apparier qu'avec une femme et réciproquement.

Solution modifier

Contrairement au problème des mariages stables, le problème des colocataires n'a pas toujours une solution stable[1]. Par exemple, si A, B, C et D sont quatre individus ayant pour préférences : 

A : B, C, D
B : C, A, D
C : A, B, D
D : A, B, C

Les individus A, B et C sont chacun le préféré de quelqu'un d'autre : A est le préféré de C et D, B le préféré de A, et C le préféré de B. Montrons qu'il n'existe pas de solution stable pour cet exemple. Considérons n'importe quelle solution. Un du groupe A, B, C serait avec D et les deux autres ensemble : par exemple AD et BC. Mais alors C préférerait être avec A qu'avec B, et A préférerait être avec C qu'avec D. Donc il n'y a pas de solution stable.

Algorithme modifier

Un algorithme efficace a été donné par (Irving 1985). L'algorithme détermine, pour toute instance du problème, si un appariement stable existe ou non. Si oui, il donne un appariement stable. L'algorithme peut s'implémenter en temps O(n2) en utilisant des structures de données appropriées pour faciliter la manipulation des listes de préférences et d'identification des rotations[Quoi ?].

Cet algorithme s'effectue en deux phases. Dans la première phase, les individus se font des propositions entre eux à l'instar de l'algorithme de Gale-Shaley pour le problème des mariages stables. La deuxième phase consiste en la suppression des cycles[Quoi ?].

La phase 1 de l'algorithme s’arrête dans trois cas différents :

  • une ou plusieurs listes de préférence sont vides, dans quel cas on peut directement conclure qu'il n'existe pas d'appariement stable
  • chaque liste de préférence contient exactement un élément, dans quel cas on a trouvé un appariement stable
  • l'algorithme atteint un état stable dans lequel aucune liste n'est vide et certaines listes ont au moins 2 éléments, dans ce cas on passe à la deuxième phase de l'algorithme.


‎

Phase 1 de l'algorithme
Entrée = Les listes de préférences des participants
Sortie = Les listes réduites des participants
tant que un participant p n'a pas de liste vide et n'est pas assigné à quelqu'un :
    pour tout q à la tête de la liste de p :
        assigner p à q;
        pour tout successeur strict r de p dans la liste de q :
            si r est assigné à q :
                supprimer l'assignation;
            fin si;
            supprimer la paire {q,r};
            si la liste de r est vide :
                il n'existe pas d'appariement stable (arrêt de l'algorithme);
            fin si;
        fin pour;
    fin pour;
fin tant que;


À noter ici que la relation d'assignation n'est pas symétrique. De plus, afin de garder la consistance des listes, on dit que l'on supprime une paire   lorsqu'on supprime   de la liste de   et   de la liste de  .


‎

Phase 2 de l'algorithme
Entrée = Les listes réduites des participants
Sortie = Un appariement stable des participants
pour tout cycle (p_1,...,p_n) et (q_1,...,q_n) tels que q_i est le second de préférence de p_i et p_{i+1} est le dernier de préférence de q_i :
    pour i = 1, ... , n-1 :
        supprimer la paire {q_i,p_i+1} :
        si la liste de q_i ou de p_{i+1} est vide :
            il n'existe pas d'appariement stable (arrêt de l'algorithme);
        fin si;
    fin pour;
fin pour


Exemple d’exécution modifier

Phase 1 modifier

 
Légende de la phase 1
 

Au début de la phase 1, chaque personne donne sa liste de préférence (1). Ensuite, A va faire une proposition à B (2). Comme B n'a pas reçu d'autres propositions, il accepte; tous les éléments qui suivent A dans la liste de B sont donc rejetés : On supprime C de la liste de B et réciproquement B de la liste de C. Autrement dit, on barre la paire (B,C). Après, B fait à son tour une proposition à D, son premier choix (3). Comme ce dernier n'a pas reçu d'autres demandes, il accepte.

 

C va ensuite proposer à D (4). Se pose alors un problème : D a déjà reçu une proposition de B.. Comme D a placé C avant B dans sa liste de préférences, C est accepté et B rejeté : (D,B), ce dernier va alors devoir refaire une proposition. On va aussi barrer les couples (D,E) et (D,A) car ils sont, comme B, placés après C dans la liste de préférences de D. B va alors faire une proposition à E, son deuxième choix (5). Comme E n'a pas d'autres propositions, celle-ci est acceptée. Puis c'est au tour de D de faire une proposition à F (6) qui accepte et rejette alors C et E : (F,C), (F,E).

 

Ensuite, E fait une proposition à C (7), qui accepte et rejette A : (C,A). Et pour finir, F propose à A qui accepte (8).

Finalement, Chaque personne a bien fait une proposition (en bleu) et a reçu une demande (en rose).

La table est donc stable (i.e. certaines lignes ont plus d'une lettre associée, et aucune ligne n'est vide), on peut passer à la phase 2.

Phase 2 modifier

 

On retrouve en (9) le tableau allégé après la phase 1, on a supprimé les couples barrés pour y voir plus clair. Le but de la phase 2 est de trouver et supprimer tous les cycles de préférences. Pour cela, commençons par prendre la première personne qui a plus d'un choix sans sa liste, ici A. On note en dessous son 2ème choix : F, puis le dernier choix de F en diagonale : D. On continue ainsi jusqu'à retrouver A (Cf. (10)). On a trouvé le cycle de préférence de A, que l'on va supprimer en barrant toutes les paires en diagonales : (F,D), (C,E), (B,A) (Cf. (11)). Finalement, on va répéter ce procédé jusqu'à ce qu'il n'y ait plus de cycle de préférence (12).

 

Finalement, chaque personne se retrouve bien avec un unique choix (13); On a trouvé un appariement stable : (A,F), (B,E) et (C,D).

Extensions modifier

Extension pour listes incomplètes modifier

La présence de listes de préférence incomplètes change la définition de stabilité d'un appariement. En effet, si un participant   n'appartient pas à la liste de préférence de  , alors on dit que   n'est pas acceptable par  . Ainsi, on rajoute une condition à la stabilité d'un appariement  ,   implique que   est acceptable par   et inversement. Ainsi, contrairement à l'algorithme de base, un appariement avec listes incomplète peut ne pas contenir tous les participants. L'algorithme ne doit donc plus s'arrêter dès qu'une liste d'un participant est vide. Les conditions d'arrêt de la phase 1 de l'algorithme modifié sont donc :

  • chaque liste de préférence contient au plus un élément, dans quel cas on a trouvé un appariement stable
  • l'algorithme atteint un état stable dans lequel au moins une liste est vide et ce participant a reçu une proposition durant la phase 1, dans quel cas on peut conclure qu'il n'existe pas d'appariement stable.
  • l'algorithme atteint un état stable qui n'appartient pas aux deux cas précédents, dans ce cas on passe à la deuxième phase de l'algorithme en supprimant les participants qui ont des listes vides.

La phase 2 de l'algorithme est quant à elle pas changée puisque l'on retrouve une instance du problème de base.

Extension pour gérer des égalités modifier

La présence d'égalités dans les listes de préférence change aussi la définition de stabilité, de même que pour le problème des mariages stables [2]. On peut maintenant définir 3 types de stabilités :

  • la stabilité faible : un appariement   est faiblement stable si il n'existe pas deux participants   et   qui se préfèrent strictement à leurs partenaires
  • la stabilité forte : un appariement   est faiblement stable si il n'existe pas deux participants   et   tels que   préfère strictement   à son partenaire et   soit préfère strictement   à son partenaire soit est indifférent entre les deux.
  • la super-stabilité : un appariement   est faiblement stable s’il n'existe pas deux participants   et   qui se préfèrent à leurs partenaires ou se sentent indifférent entre les deux.

On montre que le problème de savoir si une instance du problème des colocataires avec égalités possède un appariement faiblement stable est NP-complet[3]. Cependant, Irving et Manlove présente une variante de son algorithme de base qui permet de trouver, s’il existe, un appariement super-stable d'une instance du problème des colocataires avec égalités[4].

Implémentation dans les progiciels modifier

  • Python: Une implémentation de l'algorithme d'Irving est disponible dans la bibliothèque matching[5]
  • Java: Une solution programmation par contraintes pour le problème de colocataires avec liste incomplètes est disponible sous la licence CRAPL[6],[7].
  • R: Une solution programmation par contraintes pour le problème des colocataires stables est implémentée dans le paquet R matchingMarkets[8],[9].
  • API: La API MatchingTools fournit une interface de programmation applicative pour l'algorithme[10].
  • Matlab: L'algorithme est implémenté dans la fonction assignStableRoommates qui fait partie de la bibliothèque libre Tracker Component Library du United States Naval Research Laboratory[11]

Références modifier

  1. ↑ Jérôme Cottanceau, Le choix du meilleur urinoir : Et 19 autres problèmes amusants qui prouvent que les maths servent à quelque chose !, Paris, Belin, coll. « Science à plumes », , 216 p. (ISBN 978-2-7011-9766-1), chap. 15 (« À quoi servent les maths... À former des couples que nul ne saurait séparer ? »).
  2. ↑ (en) Robert W. Irving, « Stable marriage and indifference. », Discrete Applied Mathematics, no 48,‎ , p. 261–272
  3. ↑ (en) E. Ronn, « NP-complete stable matching problems.. », Journal of Algorithms, no 11,‎ , p. 285-304
  4. ↑ (en) Robert W. Irving et David F. Manlove, The Stable Roommates Problem with Ties, vol. 43, (DOI 10.1006/jagm.2002.1219, lire en ligne), p. 85-105
  5. ↑ (en) H. Wilde, V. Knight et J. Gillard, « Matching: A Python library for solving matching games », Journal of Open Source Software, no 48,‎ (DOI 10.21105/joss.02169  )
  6. ↑ P. Prosser, « Stable Roommates and Constraint Programming », Lecture Notes in Computer Science, CPAIOR 2014 Edition, Springer International Publishing, vol. 8451,‎ , p. 15–28 (lire en ligne)
  7. ↑ « Constraint encoding for stable roommates problem », sur Java release
  8. ↑ (en) T. Klein, « Analysis of Stable Matchings in R: Package matchingMarkets », Vignette to R Package matchingMarkets,‎ (lire en ligne)
  9. ↑ (en) « matchingMarkets: Analysis of Stable Matchings », R Project
  10. ↑ « MatchingTools API »
  11. ↑ « Tracker Component Library », sur Matlab Repository (consulté le )

Articles connexes modifier

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Problème_des_colocataires&oldid=213953838 ».