# 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

Contrairement au problème des mariages stables, le problème des colocataires n'a pas toujours une solution stable. Par exemple, si A, B, C et D sont quatre individus ayant pour préférences :
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

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(n$^2$) en utilisant des structures de données appropriées pour faciliter la manipulation des listes de préférences et d'identification des rotations.
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.
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 $(x,y)$ lorsqu'on supprime $x$ de la liste de $y$ et $y$ de la liste de $x$.
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
### 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

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
### Extension pour listes incomplètes

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 $p$ n'appartient pas à la liste de préférence de $q$, alors on dit que $p$ n'est pas acceptable par $q$. Ainsi, on rajoute une condition à la stabilité d'un appariement $M$, $\{x,y\}\in M$ implique que $x$ est acceptable par $y$ 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

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. On peut maintenant définir 3 types de stabilités :
* la stabilité faible : un appariement $M$ est faiblement stable s'il n'existe pas deux participants $x$ et $y$ qui se préfèrent strictement à leurs partenaires
* la stabilité forte : un appariement $M$ est faiblement stable s'il n'existe pas deux participants $x$ et $y$ tels que $x$ préfère strictement $y$ à son partenaire et $y$ soit préfère strictement $x$ à son partenaire soit est indifférent entre les deux.
* la super-stabilité : un appariement $M$ est faiblement stable s’il n'existe pas deux participants $x$ et $y$ 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. 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.

## Implémentation dans les progiciels

* Python: Une implémentation de l'algorithme d'Irving est disponible dans la bibliothèque matching
* Java: Une solution programmation par contraintes pour le problème de colocataires avec liste incomplètes est disponible sous la licence CRAPL$^,$.
* R: Une solution programmation par contraintes pour le problème des colocataires stables est implémentée dans le paquet R matchingMarkets$^,$.
* API: La API MatchingTools fournit une interface de programmation applicative pour l'algorithme.
* 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