Cycles de transactions optimales
- Introduite par
- Lloyd Shapley, Herbert Scarf
- Année
- 1974
- Type
- algorithm
- Famille
- Game-theoretic
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
Les Cycles de transactions optimales (TTC) sont un algorithme d'allocation de biens indivisibles à des agents, de manière à ce que l'allocation soit Pareto-efficace et individuellement rationnelle.
Développé par Lloyd Shapley et Herbert Scarf en 1974, l'algorithme identifie des cycles d'échanges dans un graphe orienté des préférences, exécute ces échanges et se répète itérativement jusqu'à ce qu'aucun échange supplémentaire ne soit bénéfique. Les TTC sont largement utilisés dans les échanges de reins et l'allocation de logements en raison de leur efficacité et de la simplicité de leur mise en œuvre.
L’intuition derrière la méthode
Imaginez un groupe de personnes possédant chacune une maison, et chaque personne classant toutes les maisons par ordre de préférence. L'algorithme TTC demande : qui est ma personne préférée ? Désignez-la. Regardez maintenant qui vous a désigné. S'il s'agit d'un cycle (A désigne B, B désigne C, C désigne A), exécutez ces échanges : A obtient la maison de B, B obtient la maison de C, C obtient la maison de A. Tout le monde dans le cycle est satisfait car il obtient la maison de quelqu'un qu'il préfère à sa maison actuelle. Supprimez le cycle et répétez jusqu'à ce qu'il n'y ait plus de cycles. Le résultat est efficace car tous les échanges bénéfiques sont réalisés.
Histoire
Lloyd Shapley et Herbert Scarf ont introduit l'algorithme des Cycles de transactions optimales en 1974 comme solution au problème du marché du logement, prouvant qu'il produit des allocations Pareto-efficaces uniques. L'algorithme a pris une importance pratique grâce aux travaux d'Alvin Roth sur l'échange de reins, où il est devenu central pour l'appariement des donneurs et des receveurs. Le prix Nobel 2012 décerné à Roth a validé l'importance des TTC pour la conception de marchés réels, en particulier dans le domaine de la transplantation d'organes.
Quand l’utiliser
Appliquer les TTC lors de l'allocation de biens indivisibles (logements, organes, places scolaires) entre agents ayant des préférences strictes sur des paniers. Utiliser lorsque l'efficacité de Pareto est essentielle et qu'aucun transfert monétaire n'est disponible ou souhaitable. Les TTC sont idéaux pour les marchés décentralisés où les agents peuvent identifier localement des échanges bénéfiques. Fonctionne mieux lorsque les agents disposent d'informations complètes et acycliques sur leurs préférences.
Limites et points d’attention
- Nécessite des ordres de préférence stricts sans indifférence ; les extensions aux préférences faibles sont complexes
- Pas coalitionnellement résistant : des coalitions d'agents peuvent déformer leurs préférences pour améliorer le résultat collectif
- Sensibilité aux cycles de préférences : l'inexistence de cycles peut laisser certains agents non échangés
- Limité à l'appariement sans transferts monétaires ; inefficace pour les valorisations hétérogènes
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Pareto-efficace : aucune amélioration sans échange n'est possible ; tous les échanges mutuellement bénéfiques sont exécutés
- Individuellement rationnel : chaque agent préfère faiblement l'allocation finale à son dotation initiale
- Stratégiquement résistant dans certains contextes : les agents ne peuvent pas s'améliorer en rapportant faussement leurs préférences
- Calculatoirement efficace : temps polynomial avec une mise en œuvre simple
- Transparent : les agents comprennent comment leur choix désigné mène à l'allocation
Applications
- Échange de reins : appariement des donneurs et receveurs d'organes pour augmenter la compatibilité des greffons par des échanges multipartites
- Allocation de logements : attribution efficace de chambres de dortoirs universitaires ou de logements sociaux
- Choix d'écoles : attribution d'élèves à des écoles avec des contraintes de capacité et une diversité de préférences
- Échange de lobes hépatiques : facilitation d'échanges par don apparié pour la transplantation hépatique par donneur vivant
- Échanges de meubles et de biens : organisation d'échanges efficaces par troc sur des plateformes de partage communautaires
Comment ça marche
Comment ça marche
Créer un graphe orienté où chaque agent désigne son agent le plus préféré parmi ceux encore sur le marché.
Trouver tous les cycles dans le graphe orienté (séquences où A désigne B, B désigne C, ..., retour à A).
Pour chaque cycle identifié, exécuter les échanges : chaque agent reçoit le bien de l'agent qu'il a désigné.
Retirer les agents échangés et leurs biens du marché. Reconstruire le graphe orienté des préférences parmi les agents restants et répéter jusqu'à ce qu'aucun autre cycle n'existe.
Pièges courants
- Confondre l'efficacité de Pareto avec l'équité ou la justice ; les TTC maximisent l'efficacité mais pas l'égalité des résultats
- Supposer la résistance stratégique dans tous les contextes ; les TTC sont véridiques uniquement dans certains contextes (par exemple, les marchés du logement, pas les échanges de reins avec priorisation)
- Oublier que l'algorithme se termine lorsqu'il n'y a plus de cycles profitables, laissant potentiellement des agents non appariés
- Oublier que les TTC nécessitent des préférences strictes sans indifférence ; leur application avec des préférences faibles nécessite une extension
Questions fréquentes
Pourquoi l'efficacité de Pareto est-elle importante dans l'allocation des ressources ?
L'efficacité de Pareto garantit qu'aucun agent ne peut être amélioré sans en dégrader un autre. C'est une exigence minimale pour une 'bonne' allocation ; la violer signifie que des ressources sont gaspillées et pourraient être réaffectées pour bénéficier à quelqu'un.
Les TTC peuvent-ils produire plusieurs allocations différentes ?
Non. L'algorithme TTC, avec son graphe orienté de préférences unique, produit une allocation Pareto-efficace unique. Le chemin vers cette allocation (ordre d'identification et d'exécution des cycles) peut varier, mais le résultat final est toujours le même.
Comment les TTC sont-ils modifiés pour l'échange de reins lorsque toutes les paires donneur-receveur ne sont pas compatibles ?
Dans l'échange de reins, le graphe orienté des préférences est construit uniquement sur les paires compatibles. L'algorithme identifie ensuite des cycles et des chaînes d'échanges entre agents compatibles, étendant les TTC originaux pour tenir compte des contraintes biologiques.
Méthodes associées
Sources
Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.
Ouvrir la référence DOICopié.Roth, A. E., Sönmez, T., & Ünver, M. U. (2008). Efficient kidney exchange: Coincidence of wants in markets with compatibility. American Economic Review, 97(3), 828-851.
Ouvrir la référence DOICopié.