Saltar al contenido
Volver a los resultados

Ciclos de Intercambio Superiores

Propuesto por
Lloyd Shapley, Herbert Scarf
Año
1974
Tipo
algorithm
Familia
Game-theoretic

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

Ciclos de Intercambio Superiores (TTC) es un algoritmo para asignar bienes indivisibles a agentes de tal manera que la asignación sea Pareto eficiente e individualmente racional. Desarrollado por Lloyd Shapley y Herbert Scarf en 1974, el algoritmo identifica ciclos de intercambios en un digrafo de preferencias, ejecuta esos intercambios y se repite iterativamente hasta que no haya más intercambios beneficiosos.

El TTC es ampliamente utilizado en el intercambio de riñones y la asignación de viviendas debido a su eficiencia y simplicidad de implementación.

La intuición detrás del método

Imagine un grupo de personas, cada una propietaria de una casa, y cada persona clasificando todas las casas por preferencia. El algoritmo TTC pregunta: ¿quién es mi favorito? Apunte hacia ellos. Ahora mire quién le apuntó a usted. Si es un ciclo (A apunta a B, B apunta a C, C apunta a A), ejecute esos intercambios: A obtiene la casa de B, B obtiene la casa de C, C obtiene la casa de A. Todos en el ciclo están contentos porque obtuvieron la casa de alguien que prefieren a la suya actual. Elimine el ciclo y repita hasta que no existan más ciclos. El resultado es eficiente porque se realizan todos los intercambios beneficiosos.

Historia

Lloyd Shapley y Herbert Scarf introdujeron el algoritmo de Ciclos de Intercambio Superiores en 1974 como una solución al problema del mercado de la vivienda, demostrando que produce asignaciones únicas Pareto-eficientes. El algoritmo ganó importancia práctica a través del trabajo de Alvin Roth sobre el intercambio de riñones, donde se volvió central para emparejar donantes y receptores. El Premio Nobel de 2012 a Roth validó la importancia del TTC para el diseño de mercados del mundo real, particularmente en el trasplante de órganos.

Cuándo usarlo

Aplique TTC al asignar bienes indivisibles (casas, órganos, plazas escolares) entre agentes con preferencias estrictas sobre los paquetes. Úselo cuando la eficiencia de Pareto sea esencial y no haya transferencias monetarias disponibles o deseables. El TTC es ideal para mercados descentralizados donde los agentes pueden identificar intercambios beneficiosos localmente. Funciona mejor cuando los agentes tienen información de preferencias completa y acíclica.

Limitaciones y consideraciones

  • Requiere órdenes de preferencia estrictas sin indiferencia; las extensiones a preferencias débiles son complejas.
  • No a prueba de coaliciones: las coaliciones de agentes pueden tergiversar las preferencias para mejorar el resultado colectivo.
  • Sensibilidad a los ciclos de preferencia: la inexistencia de ciclos puede dejar a algunos agentes sin intercambiar.
  • Limitado a la asignación sin transferencias monetarias; ineficiente para valoraciones heterogéneas.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Pareto eficiente: no existen mejoras sin intercambio; todos los intercambios mutuamente beneficiosos se ejecutan.
  • Individualmente racional: cada agente prefiere débilmente la asignación final a su dotación inicial.
  • A prueba de estrategias para ciertos entornos: los agentes no pueden mejorar al informar erróneamente sus preferencias.
  • Computacionalmente eficiente: tiempo polinomial con implementación sencilla.
  • Transparente: los agentes entienden cómo su elección señalada conduce a la asignación.

Aplicaciones

  • Intercambio de riñones: emparejar donantes y receptores de órganos para aumentar la compatibilidad de trasplantes mediante intercambios multipartitos.
  • Asignación de viviendas: asignar habitaciones de dormitorios universitarios o unidades de vivienda pública de manera eficiente.
  • Elección de escuela: asignar estudiantes a escuelas con restricciones de capacidad y diversidad de preferencias.
  • Intercambio de lóbulos hepáticos: facilitar los intercambios de donación pareada para el trasplante de hígado de donante vivo.
  • Intercambios de muebles y bienes: organizar intercambios de trueque eficientes en plataformas de intercambio comunitario.

Cómo funciona

Cómo funciona

1

Cree un grafo dirigido donde cada agente apunte a su agente preferido entre los que aún están en el mercado.

2

Encuentre todos los ciclos en el digrafo (secuencias donde A apunta a B, B apunta a C, ..., de vuelta a A).

3

Para cada ciclo identificado, ejecute los intercambios: cada agente recibe la dotación del agente al que apuntó.

4

Elimine a los agentes intercambiados y sus dotaciones del mercado. Reconstruya el digrafo de preferencias entre los agentes restantes y repita hasta que no existan más ciclos.

Errores comunes

  • Confundir la eficiencia de Pareto con la equidad o la igualdad; el TTC maximiza la eficiencia pero no la igualdad de resultados.
  • Asumir la prueba de estrategias en todos los entornos; el TTC es veraz solo en ciertos contextos (por ejemplo, mercados de vivienda, no intercambio de riñones con priorización).
  • Pasar por alto que el algoritmo termina cuando no existen más ciclos rentables, lo que podría dejar a los agentes sin emparejar.
  • Olvidar que el TTC requiere preferencias estrictas sin indiferencia; aplicarlo con preferencias débiles requiere una extensión.

Preguntas frecuentes

¿Por qué es importante la eficiencia de Pareto en la asignación de recursos?

La eficiencia de Pareto asegura que ningún agente pueda mejorar sin que otro empeore. Es un requisito mínimo para una asignación 'buena'; violarla significa que los recursos se están desperdiciando y podrían reasignarse para beneficiar a alguien.

¿Puede el TTC producir múltiples asignaciones diferentes?

No. El algoritmo TTC, con su digrafo de preferencias único, produce una asignación Pareto-eficiente única. La ruta hacia esa asignación (orden de identificación de ciclos y ejecución de intercambios) puede variar, pero el resultado final es siempre el mismo.

¿Cómo se modifica el TTC para el intercambio de riñones cuando no todos los pares donante-receptor son compatibles?

En el intercambio de riñones, el digrafo de preferencias se construye solo sobre pares compatibles. El algoritmo luego identifica ciclos y cadenas de intercambios entre agentes compatibles, extendiendo el TTC original para tener en cuenta las restricciones biológicas.

Métodos relacionados

Fuentes

  1. Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.

    Abrir referencia DOI
    Copiado.
  2. 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.

    Abrir referencia DOI
    Copiado.