Problème des colocataires

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

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

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

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 ${\displaystyle M}$ est faiblement stable si il n'existe pas deux participants ${\displaystyle x}$ et ${\displaystyle y}$ qui se préfèrent strictement à leurs partenaires
• la stabilité forte : un appariement ${\displaystyle M}$ est faiblement stable si il n'existe pas deux participants ${\displaystyle x}$ et ${\displaystyle y}$ tels que ${\displaystyle x}$ préfère strictement ${\displaystyle y}$ à son partenaire et ${\displaystyle y}$ soit préfère strictement ${\displaystyle x}$ à son partenaire soit est indifférent entre les deux.
• la super-stabilité : un appariement ${\displaystyle M}$ est faiblement stable s’il n'existe pas deux participants ${\displaystyle x}$ et ${\displaystyle 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[3]. Cepandant, 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].