Problema de emparejamiento estable

En matemáticas , economía e informática , el problema del emparejamiento estable ^{[ 1 ] [ 2 ] [ 3 ]} consiste en encontrar un emparejamiento estable entre dos conjuntos de elementos de igual tamaño, dada una ordenación de preferencias para cada elemento. Un emparejamiento es una biyección de los elementos de un conjunto a los elementos del otro. Un emparejamiento no es estable si:

En otras palabras, un emparejamiento es estable cuando no existe ningún par ( A , B ) en el que ambos se prefieran mutuamente a su pareja actual en dicho emparejamiento.

El problema de la estabilidad matrimonial se ha planteado de la siguiente manera:

Dados n hombres y n mujeres, donde cada persona ha clasificado a todos los miembros del sexo opuesto por orden de preferencia, se propone que los matrimonios se celebren de manera que no existan dos personas de sexo opuesto que prefieran casarse entre sí antes que con sus parejas actuales. Cuando no existan tales parejas, el conjunto de matrimonios se considera estable.

La existencia de dos clases que necesitan emparejarse entre sí ( hombres y mujeres heterosexuales en este ejemplo) distingue este problema del problema de los compañeros de piso estables .

Los algoritmos para encontrar soluciones al problema del matrimonio estable tienen aplicaciones en diversas situaciones del mundo real, siendo quizás la más conocida la asignación de estudiantes de medicina recién graduados a sus primeros puestos hospitalarios. ^{[ 4 ]} En 2012, el Premio Nobel de Economía fue otorgado a Lloyd S. Shapley y Alvin E. Roth "por la teoría de las asignaciones estables y la práctica del diseño de mercados". ^{[ 5 ]}

Se ha utilizado una extensión del algoritmo de Gale-Shapley en redes de distribución de contenido . Optimizar el rendimiento desde la perspectiva del usuario y equilibrar la carga del servidor requiere una buena correspondencia entre grupos de usuarios que acceden a un tipo de contenido determinado (por ejemplo, páginas web o vídeo) y grupos de servidores bien posicionados para servirles el contenido deseado. Esto puede modelarse como grupos de usuarios y grupos de servidores con preferencias (parciales) entre sí, basadas en variables como la topología de la red o los acuerdos contractuales con los proveedores de servicios de internet . Esto puede resolverse como un problema de correspondencia estable. Es necesaria una generalización del enfoque clásico de Gale-Shapley debido a que existen números desiguales de grupos en cada lado, a que la demanda y la capacidad pueden variar entre grupos y a que las preferencias son parciales en lugar de totales. ^{[ 6 ]}

El algoritmo de Gale-Shapley para emparejamiento estable se utiliza para asignar rabinos que se gradúan del Hebrew Union College a congregaciones judías. ^{[ 7 ]}

En general, puede haber muchas parejas estables diferentes. Por ejemplo, supongamos que hay tres hombres (A, B, C) y tres mujeres (X, Y, Z) que tienen las siguientes preferencias:

A: YXZ  B: ZYX  C: XZY 

X: BAC  Y: CBA  Z: ACB

Existen tres soluciones estables para esta disposición de emparejamiento:

• Los hombres obtienen su primera opción y las mujeres su tercera (AY, BZ, CX);
• Todos los participantes obtienen su segunda opción (AX, BY, CZ);
• Las mujeres obtienen su primera opción y los hombres su tercera (AZ, BX, CY).

Las tres opciones son estables, ya que la inestabilidad requiere que ambos participantes estén más satisfechos con una pareja alternativa. Otorgar a un grupo sus primeras opciones garantiza la estabilidad de las parejas, puesto que estarían descontentos con cualquier otra propuesta. Otorgar a todos su segunda opción garantiza que cualquier otra pareja sería del agrado de una de las partes. En general, la familia de soluciones para cualquier instancia del problema del matrimonio estable puede estructurarse como un retículo distributivo finito , y esta estructura da lugar a algoritmos eficientes para diversos problemas de matrimonios estables. ^{[ 8 ]}

En una instancia uniformemente aleatoria del problema del matrimonio estable con n hombres y n mujeres, el número promedio de emparejamientos estables es asintóticamente${\displaystyle e^{-1}n\ln n}$. ^{[ 9 ]} En una instancia de matrimonio estable elegida para maximizar el número de emparejamientos estables diferentes, este número es una función exponencial de n . ^{[ 10 ]} Contar el número de emparejamientos estables en una instancia dada es #P-completo . ^{[ 11 ]}

En 1962, David Gale y Lloyd Shapley demostraron que, para cualquier número igual de individuos en diferentes grupos, en el contexto de la admisión universitaria y de las personas que desean contraer matrimonio, siempre es posible resolver el problema como parejas emparejadas para que todos los emparejamientos/factores emparejados resultantes sean estables. Presentaron un algoritmo para lograrlo. ^{[ 12 ] [ 13 ]}

El algoritmo de Gale-Shapley (también conocido como algoritmo de aceptación diferida) implica una serie de "rondas" (o " iteraciones "):

• En la primera ronda, primero a ) cada hombre soltero le propone matrimonio a la mujer que más prefiere, y luego b ) cada mujer responde "tal vez" a su pretendiente preferido y "no" a todos los demás. Entonces queda provisionalmente "comprometida" con el pretendiente que más prefiere hasta el momento, y ese pretendiente también queda provisionalmente comprometido con ella.
• En cada ronda subsiguiente, primero a ) cada hombre soltero le propone matrimonio a la mujer de su preferencia a la que aún no le ha propuesto matrimonio (independientemente de si la mujer ya está comprometida), y luego b ) cada mujer responde "tal vez" si actualmente no está comprometida o si prefiere a este hombre antes que a su pareja provisional actual (en este caso, rechaza a su pareja provisional actual, quien queda libre). La naturaleza provisional de los compromisos preserva el derecho de una mujer ya comprometida a "mejorar" su relación (y, en el proceso, a "dejar" a su pareja hasta entonces).
• Este proceso se repite hasta que todos estén involucrados.

Este algoritmo garantiza la formación de un matrimonio estable para todos los participantes a tiempo.${\displaystyle O(n^{2})}$dónde${\displaystyle n}$es el número de hombres o mujeres. ^{[ 14 ]}

Entre todas las posibles parejas estables diferentes, siempre produce la que es mejor para todos los hombres entre todas las parejas estables, y la peor para todas las mujeres. ^{[ 15 ]}

Es un mecanismo veraz desde el punto de vista de los hombres (la parte proponente), es decir, ningún hombre puede obtener una mejor pareja para sí mismo tergiversando sus preferencias. Además, el algoritmo GS es incluso a prueba de estrategias grupales para los hombres, es decir, ninguna coalición de hombres puede coordinar una tergiversación de sus preferencias de tal manera que todos los hombres de la coalición estén estrictamente mejor. ^{[ 16 ]} Sin embargo, es posible que alguna coalición tergiverse sus preferencias de tal manera que algunos hombres estén mejor y los demás hombres conserven a la misma pareja. ^{[ 17 ]} El algoritmo GS no es veraz para las mujeres (la parte revisora): cada mujer puede tergiversar sus preferencias y obtener una mejor pareja.

El algoritmo de Gale-Shapley también aprovecha el paralelismo para acelerar instancias SMP a gran escala, ya que los hombres no comprometidos pueden hacer propuestas de forma independiente en cada ronda. Las implementaciones paralelas pueden asignar hombres a diferentes hilos, resolver propuestas simultáneas con primitivas de sincronización y utilizar optimizaciones como la evitación de colas, diseños de datos que tienen en cuenta la localidad y la ejecución híbrida CPU-GPU para reducir la sobrecarga. ^{[ 18 ]}

El teorema de los hospitales rurales se refiere a una variante más general del problema de emparejamiento estable, como la que se aplica al problema de emparejar médicos con puestos en hospitales, que difiere de la forma básica n a n del problema de matrimonio estable de las siguientes maneras:

• Es posible que cada participante solo esté dispuesto a ser emparejado con un subconjunto de los participantes del otro lado del proceso de emparejamiento.
• Los participantes de un lado del proceso de emparejamiento (los hospitales) pueden tener una capacidad numérica, especificando el número de médicos que están dispuestos a contratar.
• Es posible que el número total de participantes de un lado no coincida con la capacidad total a la que deben equipararse en el otro lado.
• Es posible que el resultado no coincida con todos los participantes.

En este caso, la condición de estabilidad es que ninguna pareja no emparejada se prefiera mutuamente a su situación en el emparejamiento (ya sea otra pareja o no estar emparejada). Con esta condición, seguirá existiendo un emparejamiento estable, que podrá ser encontrado mediante el algoritmo de Gale-Shapley.

Para este tipo de problema de emparejamiento estable, el teorema de los hospitales rurales establece que:

• El conjunto de médicos asignados y el número de puestos cubiertos en cada hospital son los mismos en todos los emparejamientos estables.
• Cualquier hospital que tenga puestos vacantes en alguna asignación estable, recibe exactamente el mismo conjunto de médicos en todas las asignaciones estables.

En un emparejamiento estable con indiferencia , algunos hombres podrían ser indiferentes entre dos o más mujeres y viceversa.

El problema de los compañeros de piso estables es similar al problema del matrimonio estable, pero se diferencia en que todos los participantes pertenecen a un mismo grupo (en lugar de estar divididos en un número igual de "hombres" y "mujeres").

El problema de hospitales/residentes —también conocido como el problema de admisión universitaria— difiere del problema del matrimonio estable en que un hospital puede admitir a varios residentes, o una universidad puede admitir una clase entrante de más de un estudiante. Los algoritmos para resolver el problema de hospitales/residentes pueden estar orientados a los hospitales (como lo estaba el NRMP antes de 1995) ^{[ 19 ]} o a los residentes . Este problema se resolvió, mediante un algoritmo, en el mismo artículo original de Gale y Shapley en el que se resolvió el problema del matrimonio estable. ^{[ 12 ]}

El problema de hospitales/residentes con parejas permite que el conjunto de residentes incluya parejas que deben ser asignadas juntas, ya sea al mismo hospital o a un par específico de hospitales elegidos por la pareja (por ejemplo, una pareja casada quiere asegurarse de permanecer junta y no quedar atrapada en programas muy alejados entre sí). La adición de parejas al problema de hospitales/residentes hace que el problema sea NP-completo . ^{[ 20 ]}

El problema de asignación busca encontrar un emparejamiento en un grafo bipartito ponderado que tenga el máximo peso. Los emparejamientos con peso máximo no tienen por qué ser estables, pero en algunas aplicaciones un emparejamiento con peso máximo es mejor que uno estable.

El problema de emparejamiento con contratos es una generalización del problema de emparejamiento, en el que los participantes pueden emparejarse con diferentes términos contractuales. ^{[ 21 ]} Un caso especial importante de contratos es el emparejamiento con salarios flexibles. ^{[ 22 ]}

El popular problema de emparejamiento busca un emparejamiento${\displaystyle M^{*}}$de tal manera que ningún otro emparejamiento${\displaystyle M}$existe con más personas más felices con${\displaystyle M}$que con${\displaystyle M^{*}}$Para entradas no bipartitas, determinar si existe un emparejamiento popular es un problema NP-completo . ^{[ 23 ]}

• Emparejamiento (teoría de grafos) : emparejamiento entre diferentes vértices del grafo; generalmente no está relacionado con el orden de preferencia.
• Emparejamiento sin envidia : una relajación del emparejamiento estable para problemas de emparejamiento de muchos a uno.
• Combinación de colores arcoíris para gráficos con bordes coloreados
• Politopo de coincidencia estable
• Problema de la secretaria (también llamado problema del matrimonio ): decidir cuándo detenerse para obtener la mejor recompensa en una secuencia de opciones.

• Kleinberg, J., y Tardos, E. (2005) Diseño de algoritmos , Capítulo 1, págs. 1-12. Véase el sitio web complementario para el texto.Archivado el 14 de mayo de 2011 en Wayback Machine .
• Knuth, DE (1996). El matrimonio estable y su relación con otros problemas combinatorios: una introducción al análisis matemático de algoritmos . Actas y apuntes de clase del CRM. Traducción al inglés. Sociedad Matemática Americana.
• Pittel, B. (1992). "Sobre posibles soluciones a un problema de matrimonio estable" . The Annals of Applied Probability . 2 (2): 358– 401. doi : 10.1214/aoap/1177005708 . JSTOR 2959755 . 
• Roth, AE (1984). "La evolución del mercado laboral para médicos internos y residentes: un estudio de caso en teoría de juegos" (PDF) . Journal of Political Economy . 92 (6): 991– 1016. doi : 10.1086/261272 . S2CID 1360205 . 
• Roth, AE; Sotomayor, MAO (1990). Emparejamiento bilateral: Un estudio en modelado y análisis de teoría de juegos . Cambridge University Press .
• Shoham, Yoav; Leyton-Brown, Kevin (2009). Sistemas multiagente: Fundamentos algorítmicos, de teoría de juegos y lógicos . Nueva York: Cambridge University Press . ISBN 978-0-521-89943-7.Consulte la Sección 10.6.4; disponible para descargar gratuitamente en línea .
• Schummer, J.; Vohra, RV (2007). «Diseño de mecanismos sin dinero» (PDF) . En Nisán, Noam; Jardín áspero, Tim; Tardós, Eva; Vazirani, Vijay (eds.). Teoría algorítmica de juegos . págs. 255-262 . ISBN  978-0521872829.
• Gusfield, D.; Irving, RW (1989). El problema del matrimonio estable: estructura y algoritmos . MIT Press . ISBN 0-262-07118-5.

• Demostración interactiva en Flash del problema del matrimonio estable.
• https://web.archive.org/web/20080512150525/http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
• http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
• Apuntes de clase sobre el problema de la estabilidad matrimonial