Comment ça marche, précisément
Chacun part avec une dotation : sa mission actuelle, son bureau, son créneau. Le nombre de personnes et de biens doit donc être égal.
Chacun pointe le bien qu'il préfère. On suit les flèches : elles finissent toujours par former au moins un cycle — éventuellement une boucle sur soi, quand quelqu'un a déjà ce qu'il préfère.
Les cycles sont exécutés : chacun reçoit ce qu'il pointait. Les personnes servies sortent avec leur bien, puis l'on recommence avec les autres, jusqu'à épuisement.
Trois propriétés démontrées : le résultat est Pareto-efficace, individuellement rationnel (personne ne repart avec moins bien que sa dotation), et le mécanisme est non manipulable.
Un exemple chiffré
Trois personnes, chacune avec un créneau, chacune en voulant un autre.
| Personne | Créneau actuel | Créneau visé | Obtient |
|---|---|---|---|
| Chloé | Lundi | Mardi | Mardi |
| Ali | Mardi | Lundi | Lundi |
| Bruno | Mercredi | Mercredi | Mercredi |
- Chloé pointe le créneau d'Ali, Ali pointe celui de Chloé : c'est un cycle de longueur 2.
- Le cycle est exécuté : les deux échangent et sortent satisfaits.
- Bruno pointe son propre créneau : boucle sur soi, il le conserve.
Deux échanges, aucun perdant. C'est la garantie centrale de la méthode : on ne peut jamais y sortir moins bien loti qu'on y est entré.
D'où ça vient
Lloyd Shapley et Herbert Scarf publient en 1974, dans le Journal of Mathematical Economics, l'article fondateur sur le « housing market ». Ils y attribuent l'algorithme des cycles d'échange les plus élevés à David Gale, et démontrent qu'il produit toujours une allocation dans le cœur du marché.
Atila Abdulkadiroğlu et Tayfun Sönmez l'étendent en 1999 aux situations mixtes, où certains occupants sont en place et d'autres arrivent — le cas concret des résidences universitaires américaines.
Son application la plus spectaculaire est médicale : les programmes d'échange de reins entre paires donneur-receveur incompatibles, formalisés par Roth, Sönmez et Ünver au début des années 2000, reposent sur cette mécanique de cycles. Alvin Roth et Lloyd Shapley reçoivent le prix Nobel d'économie 2012 pour l'ensemble de ces travaux.
Où on s'en sert
- Échanger des créneaux de garde, des astreintes ou des jours de congé.
- Réattribuer des bureaux, du matériel ou des places de parking déjà occupés.
- Permuter des missions ou des portefeuilles clients au sein d'une équipe.
- Échanges de reins entre paires incompatibles — l'application qui a valu un Nobel.
Limites et pièges
- Personne ne finit pire qu'au départ
- Classer sincèrement est toujours le mieux
- Tous les échanges gagnant-gagnant sont réalisés
- Il faut une possession de départ pour chacun
- Exactement autant de choses que de personnes
- Le résultat dépend fortement des dotations
Questions fréquentes
Puis-je y perdre par rapport à ma situation actuelle ?
Non, jamais, et c'est démontré : la rationalité individuelle est une propriété prouvée de l'algorithme. Si aucun échange ne vous convient, vous conservez votre dotation — c'est la boucle sur soi.
Ai-je intérêt à déclarer un faux ordre de préférence ?
Non. Le mécanisme est non manipulable : mentir ne peut pas améliorer votre résultat, et peut vous faire manquer un cycle qui vous convenait.
Et si personne ne veut échanger ?
Tout le monde pointe son propre bien, tous les cycles sont des boucles, et rien ne bouge. Le résultat est valide : il dit que la répartition actuelle est déjà optimale.
Sources
Les références primaires sur lesquelles s'appuie cette fiche.
- Shapley, Lloyd et Scarf, Herbert, On Cores and Indivisibility, Journal of Mathematical Economics, 1(1), 23-37, 1974. DOI ↗
- Roth, Alvin E., Incentive compatibility in a market with indivisible goods, Economics Letters, 9(2), 127-132, 1982. DOI ↗
- Abdulkadiroğlu, Atila et Sönmez, Tayfun, House Allocation with Existing Tenants, Journal of Economic Theory, 88(2), 233-260, 1999. DOI ↗
- Roth, Alvin E., Sönmez, Tayfun et Ünver, M. Utku, Kidney Exchange, Quarterly Journal of Economics, 119(2), 457-488, 2004. DOI ↗