Ciclo comercial superior

Top Trading Cycle (TTC) es un algoritmo para intercambiar artículos indivisibles sin usar dinero. Fue desarrollado por David Gale y publicado por Herbert Bufanda y Lloyd Shapley . ^{[1] : 30–31}

Mercado de la vivienda

El algoritmo básico de TTC se ilustra con el siguiente problema de asignación de viviendas . Hay estudiantes que viven en las residencias 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 estudiante 1 prefiere la casa asignada al estudiante 2 y viceversa, ambos se beneficiarán al intercambiar sus casas. El objetivo es encontrar una asignación central estable : una reasignación de casas a los estudiantes, de modo que se hayan realizado todos los intercambios mutuamente beneficiosos (es decir, ningún grupo de estudiantes pueda mejorar su situación juntos intercambiando sus casas). ${\displaystyle n}$

El algoritmo funciona de la siguiente manera.

1. Pida a cada agente que indique su casa "mejor" (la más preferida).
2. Dibuja una flecha desde cada agente hasta el agente, denominado , que posee la casa superior de . ${\displaystyle i}$ ${\displaystyle \operatorname {Top} (i)}$ ${\displaystyle i}$
3. Tenga en cuenta que debe haber al menos un ciclo en el gráfico (este podría ser un ciclo de longitud 1, si algún agente actualmente tiene su propia casa superior). Implemente el comercio indicado por este ciclo (es decir, reasigne cada casa al agente que la señala) y elimine todos los agentes involucrados del gráfico. ${\displaystyle i}$
4. Si quedan agentes, regrese al paso 1.

El algoritmo debe terminar, ya que en cada iteración eliminamos al menos un agente. Se puede demostrar que este algoritmo conduce a una asignación estable del núcleo.

Por ejemplo, ^{[2] : 223–224} supongamos que el orden de preferencia de los agentes es el siguiente (donde solo son relevantes como máximo las 4 opciones principales):

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 la 2 (ya que la casa 3 no está disponible). De manera similar, la casa principal del agente 2 es 5 y la casa principal del agente 5 es 1. Por lo tanto, {1,2,5} es un ciclo de negociación 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.

En la tercera iteración, el ciclo comercial superior es {4,6}, por lo que los agentes 4 y 6 intercambian sus casas. No quedan más agentes, así que el juego termina. La asignación final es:

Esta asignación es centralmente estable, ya que ninguna coalición puede mejorar su situación mediante el intercambio mutuo.

El mismo algoritmo se puede utilizar en otras situaciones, por ejemplo: ^[2] supongamos que hay 7 médicos asignados a turnos de noche; a cada médico se le asigna un turno de noche en un día de la semana. Algunos médicos prefieren los turnos que se les dan a otros médicos. El algoritmo TTC se puede utilizar aquí para lograr un intercambio máximo de beneficio mutuo.

Propiedades

TTC es un mecanismo veraz . Así lo demostró Alvin Roth . ^[3]

Cuando las preferencias son estrictas (no hay indiferencias), TTC siempre encuentra una asignación estrictamente Pareto-eficiente . Además, siempre encuentra una asignación central estable . Además, con preferencias estrictas, existe una asignación central estable única, y es la que encuentra TTC.

En el dominio de las preferencias estrictas, TTC es el único mecanismo que satisface la racionalidad individual, la eficiencia de Pareto y la resistencia a la estrategia. ^{[4] [5]}

Preferencias con indiferencias

El algoritmo TTC original suponía que las preferencias son estrictas, de modo que cada agente siempre tiene una única casa superior. En entornos realistas, los agentes pueden ser indiferentes entre las casas y un agente puede tener dos o más casas principales. Se han sugerido varios algoritmos diferentes para esta configuración. ^{[6] [7]} Posteriormente se generalizaron de varias maneras. ^{[8] [9] [10]} El esquema general es el siguiente.

1. Pídale a cada agente que indique todas sus casas principales.
2. Construya el gráfico TTC G : un gráfico dirigido en el que cada agente señala a todos los agentes que poseen sus casas principales.
3. Repetir:
   • Analice los componentes fuertemente conectados de G .
   • Identifique los sumideros : los componentes que no tienen bordes salientes (hay al menos uno).
   • Identifique los sumideros terminales : los sumideros en los que cada agente posee una de sus principales opciones.
     • Si no hay terminales disipadores, rompa y vaya al paso 4.
     • De lo contrario, para cada terminal receptor S : asigne permanentemente a cada agente en S a su casa actual, elimínelos del mercado, actualice el gráfico TTC y regrese al paso 3.
4. Seleccione un conjunto de ciclos comerciales separados, utilizando una regla de selección predeterminada. Implemente el comercio indicado por estos ciclos y retírelos del mercado.
5. Si quedan agentes, regrese al paso 1.

Los mecanismos difieren en la regla de selección utilizada en el Paso 4. La regla de selección debe satisfacer varias condiciones: ^[9]

• Unicidad: la regla selecciona, para cada agente, una casa única entre sus mejores casas.
• Terminación: se garantiza que el algoritmo que utiliza la regla terminará.
• Persistencia: en el gráfico reducido obtenido por la regla, cada camino dirigido que termina en un agente i insatisfecho (un agente que no posee una casa superior) es persistente : el camino permanece en el gráfico hasta que el agente i abandona el mercado o cambia su casa. .
• Independencia de los agentes insatisfechos: si el agente i está insatisfecho y dos gráficos TTC solo difieren en los bordes que salen de i , entonces los gráficos TTC reducidos solo difieren en el borde que sale de i .

Si la regla de selección satisface Unicidad y Terminación, el mecanismo resultante produce una asignación que es Pareto-eficiente y en el núcleo débil (ningún subconjunto de agentes puede obtener una casa estrictamente mejor para todos ellos negociando entre ellos). Un núcleo débil también implica que es individualmente racional. Si, además, la regla de selección satisface la persistencia, la independencia de los agentes insatisfechos y algunas otras condiciones técnicas, el mecanismo resultante es a prueba de estrategias .

Una regla de selección particular que satisface estas condiciones es la regla de Objeto de máxima prioridad (HPO). Asume un orden de prioridad predeterminado en las casas. Funciona de la siguiente manera. ^[9]

• (a) Todo agente insatisfecho señala al propietario de la casa de mayor prioridad entre sus casas superiores. Todos los agentes insatisfechos son etiquetados.
• (b) De los agentes no etiquetados, considere aquellos que tienen una casa superior propiedad de un agente etiquetado. Entre ellos, elija al agente i propietario de la casa de mayor prioridad. Haz que señale una casa de máxima prioridad propiedad de un agente etiquetado. Agente de etiquetas i .
• (c) Si hay agentes sin etiquetar, regrese al (b).

Cuando finaliza la regla, cada agente está etiquetado y cada agente etiquetado tiene un borde de salida único. La regla garantiza que, en cada iteración, todos los ciclos contengan al menos un agente insatisfecho. Por lo tanto, en cada iteración, al menos un nuevo agente queda satisfecho. Por lo tanto, el algoritmo finaliza después de como máximo n iteraciones. El tiempo de ejecución de cada iteración es , donde es el tamaño máximo de una clase de indiferencia. Por lo tanto, el tiempo total de ejecución es . ${\displaystyle O(n\log {n}+n\gamma )}$ ${\displaystyle \gamma }$ ${\displaystyle O(n^{2}\log {n}+n^{2}\gamma )}$

Otras extensiones

El algoritmo TTC se ha ampliado de varias formas.

1. Un entorno en el que, además de los estudiantes que ya viven en casas, también hay nuevos estudiantes sin casa y casas vacías sin estudiantes. ^[11]

2. El entorno de elección de escuela . ^[12] El Distrito Escolar de Recuperación de Nueva Orleans adoptó la versión de elección escolar de TTC en 2012. ^[13]

3. La configuración del intercambio de riñones : principales ciclos y cadenas comerciales (TTCC). ^[14]

Implementación en paquetes de software.

• R : El algoritmo Top-Trading-Cycles para el problema del mercado inmobiliario se implementa como parte del matchingMarketspaquete. ^{[15] [16]}
• API : La API MatchingTools proporciona una interfaz de programación de aplicaciones gratuita para el algoritmo Top-Trading-Cycles. ^[17]

Ver también

• Economía de intercambio
• Mercado de la vivienda

Referencias

1. Shapley, Lloyd; Bufanda, Herbert (1974). "Sobre núcleos e indivisibilidad". Revista de Economía Matemática . 1 : 23–37. doi :10.1016/0304-4068(74)90033-0. S2CID  154744803.
2. Hervé Moulin (2004). División Justa y Bienestar Colectivo . Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
3. Roth, Alvin E. (1 de enero de 1982). "Compatibilidad de incentivos en un mercado con bienes indivisibles". Cartas de Economía . 9 (2): 127-132. doi :10.1016/0165-1765(82)90003-9. ISSN  0165-1765.
4. Mamá, Jinpeng (1 de marzo de 1994). "Prueba de la estrategia y núcleo estricto en un mercado con indivisibilidades". Revista Internacional de Teoría de Juegos . 23 (1): 75–83. doi :10.1007/BF01242849. ISSN  1432-1270. S2CID  36253188.
5. Anno, Hidekazu (1 de enero de 2015). "Una breve prueba para la caracterización del núcleo del mercado inmobiliario". Cartas de Economía . 126 : 66–67. doi :10.1016/j.econlet.2014.11.019. ISSN  0165-1765.
6. Alcalde-Unzu, Jorge; Molís, Elena (1 de septiembre de 2011). "Intercambio de bienes indivisibles e indiferencias: los principales mecanismos de conjuntos absorbentes de comercio". Juegos y comportamiento económico . 73 (1): 1–16. doi :10.1016/j.geb.2010.12.005. hdl : 2454/18593 . ISSN  0899-8256.
7. Jaramillo, Paula; Manjunath, Vikram (1 de septiembre de 2012). "La diferencia que hace la indiferencia en la asignación de objetos a prueba de estrategias". Revista de teoría económica . 147 (5): 1913-1946. doi :10.1016/j.jet.2012.05.017. ISSN  0022-0531.
8. Aziz, Haris; Keijzer, Bart de (2012). "Mercados inmobiliarios con indiferencias: una historia de dos mecanismos". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 26 (1): 1249-1255. doi : 10.1609/aaai.v26i1.8239 . ISSN  2374-3468. S2CID  15395473.
9. Saban, Daniela; Sethuraman, Jay (16 de junio de 2013). "Asignación de viviendas con indiferencias". Actas de la decimocuarta conferencia ACM sobre comercio electrónico . CE '13. Nueva York, NY, EE.UU.: Asociación de Maquinaria de Computación. págs. 803–820. doi :10.1145/2492002.2482574. ISBN 978-1-4503-1962-1.
10. Desconocido ^{[ enlace muerto permanente ]}
11. Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999). "Asignación de viviendas con inquilinos existentes". Revista de teoría económica . 88 (2): 233–260. doi : 10.1006/jeth.1999.2553 .. Véase también Presentación de Katharina Schaar.
12. Abdulkadiroğlu, Atila; Sönmez, Tayfun (2003). "Elección de escuela: un enfoque de diseño de mecanismos" (PDF) . Revista económica estadounidense . 93 (3): 729–747. doi :10.1257/000282803322157061. hdl : 10161/2090 . S2CID  15609227.
13. Vanacore, Andrés (16 de abril de 2012). "La inscripción centralizada en el Distrito Escolar de Recuperación se prueba por primera vez". The Times-Picayune . Nueva Orleans . Consultado el 4 de abril de 2016 .
14. Roth, Alvin; Sönmez, Tayfun; Unver, M. Utku (2004). "Intercambio de riñones". Revista Trimestral de Economía . 119 (2): 457–488. doi :10.1162/0033553041382157.
15. Klein, T. (2015). "Análisis de coincidencias estables en R: mercados de coincidencia de paquetes" (PDF) . "Vignette to R Paquete MatchingMarkets" .
16. "matchingMarkets: Análisis de emparejamientos estables". Proyecto R. 12 de enero de 2020.
17. "API de herramientas coincidentes".