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. 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[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
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
Un algorithme efficace a été donné 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 soient utilisées pour faciliter la manipulation des listes de préférences et d'identification des rotations.
Implémentation dans les progiciels
- R: Une solution programmation par contraintes pour le problème des colocataires stables est implémentée dans le paquet R
matchingMarkets[2],[3]. - API: La API MatchingTools fournit une interface de programmation applicative pour l'algorithme.[4]
Références
- (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, (DOI 10.1016/0196-6774(85)90033-1), p. 577-595
- (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
- 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 ? »).
- (en) T. Klein, « Analysis of Stable Matchings in R: Package matchingMarkets », Vignette to R Package matchingMarkets, (lire en ligne)
- (en) « matchingMarkets: Analysis of Stable Matchings », R Project
- « MatchingTools API »
