Ciclo comercial superior
El ciclo de negociación superior (TTC) es un algoritmo para intercambiar artículos indivisibles sin usar dinero. Fue desarrollado por David Gale y publicado por Herbert Scarf y Lloyd Shapley . [1] : 30–31
El algoritmo TTC básico se ilustra con el siguiente problema de asignación de viviendas . Hay estudiantes viviendo en los dormitorios de estudiantes. Cada estudiante vive en una sola casa. Cada estudiante tiene una relación de preferencia sobre las casas, y algunos estudiantes prefieren las casas asignadas a otros estudiantes. Esto puede conducir a intercambios mutuamente beneficiosos. Por ejemplo, si el alumno 1 prefiere la casa asignada al alumno 2 y viceversa, ambos se beneficiarán intercambiando sus casas. El objetivo es encontrar una asignación estable central : una reasignación de casas a los estudiantes, de modo que se hayan realizado todos los intercambios de beneficio mutuo (es decir, ningún grupo de estudiantes puede mejorar juntos su situación intercambiando sus casas).
El algoritmo debe terminar, ya que en cada iteración eliminamos al menos un agente. Se puede probar que este algoritmo conduce a una asignación estable en el núcleo.
Por ejemplo, [2] : 223–224 suponga que el orden de preferencia de los agentes es el siguiente (donde solo son relevantes las 4 opciones principales como máximo):
En la primera iteración, el único ciclo comercial superior es {3} (es un ciclo de longitud 1), por lo que el agente 3 conserva su casa actual y abandona el mercado.
En la segunda iteración, la casa superior del agente 1 es 2 (ya que la casa 3 no está disponible). De manera similar, la casa superior del agente 2 es 5 y la casa superior del agente 5 es 1. Por lo tanto, {1,2,5} es un ciclo comercial superior. Se implementa: el agente 1 obtiene la casa 2, el agente 2 obtiene la casa 5 y el agente 5 obtiene la casa 1. Estos tres agentes abandonan el mercado.