Hispanopedia Wiki
Articulo de referencia

Ciclo de negociación superior

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

Hispanopedia WikiContenido en espanolLectura gratuita

El ciclo de negociación superior (TTC) es un algoritmo para negociar artículos indivisibles sin usar 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 TTC se ilustra con el siguiente problema de asignación de viviendas . Haynorte{\displaystyle n}Estudiantes que viven en residencias estudiantiles. Cada estudiante vive en una casa individual. Cada estudiante tiene una preferencia por las casas, y algunos estudiantes prefieren las casas asignadas a otros estudiantes. Esto puede dar lugar 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 central —una reasignación de casas a los estudiantes— de tal manera que se hayan realizado todos los intercambios mutuamente beneficiosos (es decir, que ningún grupo de estudiantes pueda mejorar su situación en conjunto intercambiando sus casas).

El algoritmo funciona de la siguiente manera.

  1. Pida a cada agente que indique su casa "principal" (la que prefiere).
  2. Dibuja una flecha desde cada agente.i{\displaystyle i}al agente, denotadoArriba⁡(i){\displaystyle \operatorname {Top} (i)}, quien ocupa el cargo más alto en la Cámara de Representantesi{\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 agentei{\displaystyle i}(actualmente posee su propia casa principal). Implemente el intercambio indicado por este ciclo (es decir, reasigne cada casa al agente que la señala) y elimine a todos los agentes involucrados del gráfico.
  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 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 de negociación 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 de mayor valor del agente 1 es la 2 (ya que la casa 3 no está disponible). De manera similar, la casa de mayor valor del agente 2 es la 5 y la del agente 5 es la 1. Por lo tanto, {1,2,5} es un ciclo de intercambio de propiedades de alto valor. Se implementa de la siguiente manera: 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 superior {4,6} es, 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 puede utilizarse en otras situaciones, por ejemplo: [ 2 ] supongamos que hay 7 médicos asignados a turnos nocturnos; a cada médico se le asigna un turno nocturno un día de la semana. Algunos médicos prefieren los turnos asignados a otros médicos. El algoritmo TTC puede utilizarse aquí para lograr un intercambio mutuamente beneficioso máximo.

Propiedades

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 Pareto-eficiente . Además, siempre encuentra una asignación estable central . Asimismo, con preferencias estrictas, existe una única asignación estable central, que es la que encuentra TTC.

En el dominio de preferencias estrictas, TTC es el único mecanismo que satisface la racionalidad individual, la eficiencia de Pareto y la resistencia a la manipulación estratégica. [ 4 ] [ 5 ]

Preferencias con indiferencias

El algoritmo TTC original asumía que las preferencias eran estrictas, de modo que cada agente siempre tenía una única casa de primera categoría. En entornos realistas, los agentes pueden ser indiferentes entre casas, y un agente puede tener dos o más casas de primera categoría. Se han sugerido varios algoritmos diferentes para este entorno. [ 6 ] [ 7 ] Posteriormente se generalizaron de varias maneras. [ 8 ] [ 9 ] [ 10 ] El esquema general es el siguiente.

  1. Pida a cada agente que le indique todas las casas que considera mejores.
  2. Construye el grafo TTC G : un grafo 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 sin aristas salientes (hay al menos una).
    • Identifique los sumideros terminales : aquellos sumideros en los que cada agente posee una de sus opciones preferidas.
      • Si no hay sumideros terminales, interrumpa el proceso y vaya al paso 4.
      • De lo contrario, para cada sumidero terminal S : asigne permanentemente a cada agente en S a su casa actual, retírelos del mercado, actualice el gráfico TTC y vuelva 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 ]

  • Singularidad: la regla selecciona, para cada agente, una casa única de entre sus mejores casas.
  • Terminación: se garantiza que el algoritmo que utiliza la regla terminará.
  • Persistencia: en el grafo reducido obtenido por la regla, cada camino dirigido que termina en un agente insatisfecho i (un agente que no posee una casa de alto valor) es persistente ; el camino permanece en el grafo hasta que el agente i abandona el mercado o intercambia su casa.
  • Independencia de los agentes insatisfechos: si el agente i no está satisfecho y dos grafos TTC solo difieren en las aristas que salen de i , entonces los grafos TTC reducidos solo difieren en la arista que sale de i .

Si la regla de selección satisface Unicidad y Terminación, el mecanismo resultante produce una asignación Pareto-eficiente y en el núcleo débil (ningún subconjunto de agentes puede obtener una casa estrictamente mejor para todos ellos mediante el intercambio entre sí). 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 otras condiciones técnicas, el mecanismo resultante es a prueba de manipulación estratégica .

Una regla de selección particular que satisface estas condiciones es la regla del Objeto de Máxima Prioridad (HPO). Esta regla presupone 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 principal propiedad de un agente etiquetado. Entre ellos, elija al agente i que posee la casa de mayor prioridad. Haga que i apunte a una casa de mayor prioridad propiedad de un agente etiquetado. Etiquete al agente i .
  • (c) Si hay agentes sin etiquetar, vuelva al apartado (b).

Cuando la regla finaliza, todos los agentes están etiquetados y cada agente etiquetado tiene una arista saliente única. 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. En consecuencia, el algoritmo finaliza después de como máximo n iteraciones. El tiempo de ejecución de cada iteración esO(norteregistro⁡norte+norteγ){\displaystyle O(n\log {n}+n\gamma )}, dóndeγ{\displaystyle \gamma }es el tamaño máximo de una clase de indiferencia. Por lo tanto, el tiempo total de ejecución esO(norte2registro⁡norte+norte2γ){\displaystyle O(n^{2}\log {n}+n^{2}\gamma )}.

Otras extensiones

El algoritmo TTC se ha ampliado de diversas maneras.

1. Un entorno en el que, además de los estudiantes que ya viven en casas, también hay 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 de 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 está implementado 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". Journal of Mathematical Economics . 1 : 23–37 . doi : 10.1016/0304-4068(74)90033-0 . S2CID 154744803 . 
  2. 1 2 Hervé Moulin (2004). División justa y bienestar colectivo . Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
  3. ↑ Roth, Alvin E. (1982-01-01). "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). "Integridad estratégica y el núcleo estricto en un mercado con indivisibilidades" . International Journal of Game Theory . 23 (1): 75– 83. doi : 10.1007/BF01242849 . ISSN 1432-1270 . S2CID 36253188 .  
  5. ↑ Anno, Hidekazu (2015-01-01). "Una breve demostración para 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" . Games and Economic Behavior . 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 supone 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. 1 2 3 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 . 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
  11. ↑ Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999). "Asignación de viviendas con inquilinos existentes" . Journal of Economic Theory . 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). "Primera prueba de la matrícula centralizada en el Distrito Escolar de Recuperación" . 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" . Quarterly Journal of Economics . 119 (2): 457– 488. doi : 10.1162/0033553041382157 .
  15. ↑ Klein, T. (2015). "Análisis de emparejamientos estables en R: paquete matchingMarkets" (PDF) . Viñeta del paquete MatchingMarkets de R.
  16. ↑ "matchingMarkets: Análisis de emparejamientos estables" . Proyecto R. 12 de enero de 2020.
  17. ↑ "API de MatchingTools" .
Lecturas relacionadas
6 articulos
David GaleDavid GaleDavid Gale (December 13, 1921 – March 7, 2008) was an American mathematician and economist. He was a professor emeritus at the University of Califo...Bufanda HerbertBufanda HerbertHerbert Eli "Herb" Scarf (25 de julio de 1930 - 15 de noviembre de 2015) fue un economista matemático estadounidense y profesor Sterling de Economí...Lloyd ShapleyLloyd ShapleyLloyd Stowell Shapley ( 2 de junio de 1923 - 12 de marzo de 2016) fue un matemático estadounidense y economista ganador del Premio Nobel . Contribu...{\displaystyle n^{\gamma }}Problema de asignación de viviendasEn economía e informática , el problema de asignación de viviendas consiste en asignar objetos a personas con preferencias diferentes , de manera q...Preferencia (economía)Preferencia (economía)Un ejemplo sencillo de un orden de preferencia sobre tres bienes, en el que se prefiere una naranja a un plátano, pero se prefiere una manzana a un...{\displaystyle (N,v)}Núcleo (teoría de juegos)En la teoría de juegos cooperativos , el núcleo es el conjunto de asignaciones o imputaciones factibles en las que ninguna coalición de agentes pue...