Problème des colocataires

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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. 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 | modifier le code]

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 :

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

A, B et C sont chacun le préféré de quelqu'un d'autre. Si une solution existait, un du groupe A, B, C serait avec D et les deux autres ensemble : par exemple AD et BC. 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 | modifier le code]

Un algorithme efficace a été donnée par (Irving 1985). L'algorithme détermine, pour toute instance du problème, si un appariement stable existe, et si oui, trouve une telle correspondance à condition que les structures de données appropriées sont utilisées pour faciliter la manipulation des listes de préférences et d'identification des rotations.

Références[modifier | modifier le code]

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Stable roommates problem » (voir la liste des auteurs)
  • (en) Robert W. Irving, An efficient algorithm for the "stable roommates" problem, vol. 6,‎ 1985 (lien DOI?), p. 577-595
  • (en) Robert W. Irving et David F. Manlove, The Stable Roommates Problem with Ties, vol. 43,‎ 2002 (lien DOI?, lire en ligne), p. 85-105

Article connexe[modifier | modifier le code]

Problème d'affectation