Hispanopedia Wiki
Articulo de referencia

Ciclo comercial superior

El ciclo de negociación superior (TTC) es un algoritmo para negociar artículos indivisibles sin utilizar dinero. Fue desarrollado por David Gale y publicado por Herbert Scarf y ...

Hispanopedia WikiContenido en espanolLectura gratuita

El ciclo de negociación superior (TTC) es un algoritmo para negociar artículos indivisibles sin utilizar dinero. Fue desarrollado por David Gale y publicado por Herbert Scarf 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 casas . Hay estudiantes que viven en dormitorios de estudiantes. Cada estudiante vive en una sola casa. Cada estudiante tiene una relación de preferencia en 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 estable en el núcleo : 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 puede mejorar su situación en conjunto intercambiando sus casas). norte {\estilo de visualización n}

El algoritmo funciona de la siguiente manera.

  1. Pídale a cada agente que indique su casa “top” (la más preferida).
  2. Dibuje una flecha desde cada agente hasta el agente, denotado , que posee la casa superior de . i {\estilo de visualización i} Arriba ⁡ ( i ) {\displaystyle \operatorname {Arriba} (i)} i {\estilo de visualización i}
  3. Tenga en cuenta que debe haber al menos un ciclo en el gráfico (puede ser un ciclo de longitud 1, si algún agente posee actualmente su propia casa superior). Implemente el intercambio indicado por este ciclo (es decir, reasigne cada casa al agente que la señala) y elimine todos los agentes involucrados del gráfico. i {\estilo de visualización i}
  4. Si quedan agentes, vuelva 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 preferencias de los agentes es el siguiente (donde solo las 4 opciones principales como máximo son relevantes):

En la primera iteración, el único ciclo de negociación superior es {3} (es un ciclo de duración 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 superior del agente 2 es la 5 y la casa superior del agente 5 es la 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 de intercambio principal es {4,6}, por lo que los agentes 4 y 6 intercambian sus casas. No quedan más agentes, por lo que el juego termina. La asignación final es:

Esta asignación es estable en su núcleo, 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 que están asignados a turnos de noche; cada médico está asignado a un turno de noche en un día de la semana. Algunos médicos prefieren los turnos asignados a otros médicos. El algoritmo TTC se puede utilizar aquí para lograr un intercambio mutuamente beneficioso máximo.

Propiedades

La TTC es un mecanismo veraz . Esto fue demostrado por Alvin Roth . [3]

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

En el dominio de preferencias estrictas, la 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 eran estrictas, de modo que cada agente siempre tenía una única casa superior. En situaciones realistas, los agentes pueden ser indiferentes entre casas, y un agente puede tener dos o más casas superiores. Se han sugerido varios algoritmos diferentes para esta situació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 apunta a todos los agentes que poseen sus casas principales.
  3. Repetir:
    • Analice los componentes fuertemente conectados de G .
    • Identifique los sumideros : los componentes sin 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 disipadores terminales, rómpalos y vaya al paso 4.
      • De lo contrario, para cada terminal receptor S : asignar permanentemente a cada agente en S a su casa actual, eliminarlos del mercado, actualizar el gráfico TTC y volver al paso 3.
  4. Seleccione un conjunto de ciclos de negociación disjuntos, utilizando una regla de selección predeterminada. Implemente la operación indicada por estos ciclos y retírelos del mercado.
  5. Si quedan agentes, vuelva 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 casas top.
  • Terminación: se garantiza que el algoritmo que utiliza la regla finalizará.
  • 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 intercambia su casa.
  • Independencia de agentes insatisfechos: si el agente i no está satisfecho 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 se encuentra en el núcleo débil (ningún subconjunto de agentes puede obtener una casa estrictamente mejor para todos ellos comerciando entre ellos). El núcleo débil también implica que es individualmente racional. Si, además, la regla de selección satisface Persistencia, 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 del objeto de mayor prioridad (HPO, por sus siglas en inglés). Supone un orden de prioridad predeterminado para las casas. Funciona de la siguiente manera: [9]

  • (a) Cada agente insatisfecho señala al propietario de la casa de mayor prioridad entre sus casas principales. Todos los agentes insatisfechos están 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 que posee la casa de mayor prioridad. Haga que i señale una casa de mayor prioridad propiedad de un agente etiquetado. Etiquete al agente i .
  • (c) Si hay agentes no etiquetados, regrese a (b).

Cuando la regla termina, todos los agentes quedan etiquetados y cada agente etiquetado tiene un único borde de salida. La regla garantiza que, en cada iteración, todos los ciclos contienen al menos un agente insatisfecho. Por lo tanto, en cada iteración, al menos un nuevo agente queda satisfecho. Por lo tanto, el algoritmo termina después de un máximo de 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 de ejecución total es . Oh ( norte registro ⁡ norte + norte gamma ) {\displaystyle O(n\log {n}+n\gamma )} gamma {\estilo de visualización \gamma} Oh ( norte 2 registro ⁡ norte + norte 2 gamma ) {\displaystyle O(n^{2}\log {n}+n^{2}\gamma)}

Otras extensiones

El algoritmo TTC se ha ampliado de diversas maneras.

1. Un contexto en el que, además de estudiantes que ya viven en casas, hay también estudiantes nuevos 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 de escuela del TTC en 2012. [13]

3. El entorno de intercambio de riñones : Ciclos y cadenas de negociación principales (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 de MatchingTools proporciona una interfaz de programación de aplicaciones gratuita para el algoritmo Top-Trading-Cycles. [17]

Véase también

Referencias

  1. ^ Shapley, Lloyd; Scarf, 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. ^ de Herve 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". Economics Letters . 9 (2): 127–132. doi :10.1016/0165-1765(82)90003-9. ISSN  0165-1765.
  4. ^ Ma, Jinpeng (1994-03-01). "Estrategia a prueba de errores 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 de la caracterización del núcleo en los mercados inmobiliarios". Economics Letters . 126 : 66–67. doi :10.1016/j.econlet.2014.11.019. ISSN  0165-1765.
  6. ^ Alcalde-Unzu, Jorge; Molis, Elena (2011-09-01). "Intercambio de bienes indivisibles e indiferencias: los mecanismos de los conjuntos absorbentes de comercio superior". 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 genera la indiferencia en la asignación de objetos a prueba de estrategias". Journal of Economic Theory . 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. ^ abc Saban, Daniela; Sethuraman, Jay (16 de junio de 2013). "Asignación de viviendas con indiferencias". Actas de la decimocuarta conferencia de la ACM sobre comercio electrónico . EC '13. Nueva York, NY, EE. UU.: Association for Computing Machinery. 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, Andres (16 de abril de 2012). "La inscripción centralizada en el Distrito Escolar de Recuperación obtiene su primera prueba". 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 emparejamientos estables en R: Paquete matchingMarkets" (PDF) . Viñeta de R Package MatchingMarkets .
  16. ^ "matchingMarkets: Análisis de emparejamientos estables". Proyecto R. 12 de enero de 2020.
  17. ^ "API de MatchTools".
Obtenido de "https://es.wikipedia.org/w/index.php?title=Ciclo_comercial_al_alto&oldid=1238398463"