En matemáticas , economía e informática , el problema del matrimonio estable (también problema de emparejamiento estable o SMP ) es el problema de encontrar un emparejamiento estable entre dos conjuntos de elementos de igual tamaño dado un orden de preferencias para cada elemento. Una coincidencia es una biyección de los elementos de un conjunto a los elementos del otro conjunto. Una coincidencia no es estable si:
- Hay un elemento A del primer conjunto emparejado que prefiere algún elemento B dado del segundo conjunto emparejado sobre el elemento con el que A ya está emparejado, y
- B también prefiere A sobre el elemento con el que B ya está emparejado.
En otras palabras, un emparejamiento es estable cuando no existe ningún emparejamiento ( A , B ) en el que ambos se prefieran entre sí a su pareja actual bajo el emparejamiento.
El problema del matrimonio estable se ha expresado de la siguiente manera:
Dado n hombres y n mujeres, donde cada persona ha clasificado a todos los miembros del sexo opuesto en orden de preferencia, casar a los hombres y mujeres juntos de manera que no haya dos personas del sexo opuesto que prefieran tener el uno al otro antes que sus parejas actuales. . Cuando no existen tales pares de personas, el conjunto de matrimonios se considera estable.
La existencia de dos clases que deben emparejarse (hombres y mujeres heterosexuales en este ejemplo) distingue este problema del problema de los compañeros de habitación estables .
Aplicaciones
Los algoritmos para encontrar soluciones al problema del matrimonio estable tienen aplicaciones en una variedad de situaciones del mundo real, quizás la más conocida de ellas es la asignación de estudiantes de medicina graduados a sus primeras citas en el hospital. [1] En 2012, el Premio Nobel de Ciencias Económicas fue otorgado a Lloyd S. Shapley y Alvin E. Roth "por la teoría de asignaciones estables y la práctica del diseño de mercado". [2]
Una aplicación importante y a gran escala del matrimonio estable consiste en asignar usuarios a servidores en un gran servicio de Internet distribuido. [3] Miles de millones de usuarios acceden a páginas web, videos y otros servicios en Internet, lo que requiere que cada usuario sea emparejado con uno de (potencialmente) cientos de miles de servidores en todo el mundo que ofrecen ese servicio. Un usuario prefiere servidores que estén lo suficientemente próximos para proporcionar un tiempo de respuesta más rápido para el servicio solicitado, lo que resulta en un orden preferencial (parcial) de los servidores para cada usuario. Cada servidor prefiere servir a los usuarios que puede con un costo menor, lo que resulta en un orden preferencial (parcial) de usuarios para cada servidor. Las redes de entrega de contenido que distribuyen gran parte del contenido y los servicios del mundo resuelven este gran y complejo problema de matrimonio estable entre usuarios y servidores cada decenas de segundos para permitir que miles de millones de usuarios se emparejen con sus respectivos servidores que pueden proporcionar las páginas web y videos solicitados. u otros servicios. [3]
Diferentes emparejamientos estables
En general, puede haber muchas coincidencias estables diferentes. Por ejemplo, suponga que hay tres hombres (A, B, C) y tres mujeres (X, Y, Z) que tienen preferencias de:
- A: YXZ B: ZYX C: XZY
- X: BAC Y: CBA Z: ACB
Hay tres soluciones estables para este arreglo de emparejamiento:
- los hombres tienen su primera opción y las mujeres la tercera - (AY, BZ, CX);
- todos los participantes obtienen su segunda opción: (AX, BY, CZ);
- las mujeres tienen su primera opción y los hombres la tercera - (AZ, BX, CY).
Los tres son estables, porque la inestabilidad requiere que ambos participantes estén más felices con un partido alternativo. Darle a un grupo sus primeras opciones asegura que las coincidencias sean estables porque no estarían contentos con cualquier otra coincidencia propuesta. Darles a todos su segunda opción asegura que cualquier otro partido no sea del agrado de una de las partes. En general, a la familia de soluciones a cualquier caso del problema del matrimonio estable se le puede dar la estructura de una red distributiva finita , y esta estructura conduce a algoritmos eficientes para varios problemas de matrimonios estables. [4]
En un caso uniformemente aleatorio del problema del matrimonio estable con n hombres yn mujeres, el número promedio de emparejamientos estables es asintóticamente. [5] En un caso de matrimonio estable elegido para maximizar el número de emparejamientos estables diferentes, este número es una función exponencial de n . [6] Contar el número de coincidencias estables en una instancia determinada es # P-completo . [7]
Solución algorítmica
En 1962, David Gale y Lloyd Shapley demostraron que, para cualquier número igual de hombres y mujeres, siempre es posible resolver el SMP y estabilizar todos los matrimonios. Presentaron un algoritmo para hacerlo. [8] [9]
El algoritmo 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 no comprometido propone a la mujer que más prefiere, y luego b ) cada mujer responde "tal vez" a su pretendiente que más prefiere y "no" a todos los demás pretendientes. A continuación, se "compromete" provisionalmente con el pretendiente que más prefiere hasta ahora, y ese pretendiente también se compromete provisionalmente con ella.
- En cada ronda subsiguiente, primero a ) cada hombre no comprometido propone a la mujer más preferida 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 ella está actualmente no comprometida o si prefiere a este hombre sobre su actual pareja provisional (en este caso, rechaza a su actual pareja provisional que deja de estar comprometida). La naturaleza provisional de los compromisos preserva el derecho de una mujer ya comprometida a "cambiar" (y, en el proceso, "dejar plantada" a su hasta entonces pareja).
- Este proceso se repite hasta que todos se comprometen.
Este algoritmo está garantizado para producir un matrimonio estable para todos los participantes en el tiempo. dónde es el número de hombres o mujeres. [10]
Entre todos los posibles emparejamientos estables diferentes, siempre se obtiene el mejor para todos los hombres entre todos los emparejamientos estables y el peor para todas las mujeres. Es un mecanismo veraz desde el punto de vista de los hombres (el lado proponente). Es decir, ningún hombre puede obtener una mejor correspondencia para sí mismo si tergiversa 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 manera que todos los hombres de la coalición estén estrictamente en mejores condiciones. [11] Sin embargo, es posible que algunas coaliciones tergiversen sus preferencias de modo que algunos hombres estén en mejor situación y los otros mantengan la misma pareja. [12] El algoritmo GS no es veraz para las mujeres (el lado de la revisión): cada mujer puede tergiversar sus preferencias y obtener una mejor coincidencia.
Teorema de hospitales rurales
El teorema de los hospitales rurales se refiere a una variante más general del problema de emparejamiento estable, como el que se aplica en el problema de emparejar médicos con puestos en hospitales, que difiere en las siguientes formas de la forma básica n- a- n del problema del matrimonio estable:
- Cada participante solo puede estar dispuesto a ser emparejado con un subconjunto de los participantes del otro lado del emparejamiento.
- Los participantes de un lado del 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 sea igual a la capacidad total con la que se emparejarán en el otro lado.
- Es posible que la coincidencia resultante no coincida con todos los participantes.
En este caso, la condición de estabilidad es que ninguna pareja no emparejada se prefiera entre sí a su situación en el emparejamiento (ya sea que esa situación sea otra pareja o no emparejada). Con esta condición, seguirá existiendo una coincidencia estable y aún se puede encontrar mediante el algoritmo 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 ocupados en cada hospital son los mismos en todos los emparejamientos estables.
- Cualquier hospital que tenga algunos puestos vacíos en algún emparejamiento estable, recibe exactamente el mismo grupo de médicos en todos los emparejamientos estables.
Problemas relacionados
En el emparejamiento estable con la indiferencia , algunos hombres pueden ser indiferentes entre dos o más mujeres y viceversa.
El problema de los compañeros de habitación estables es similar al problema del matrimonio estable, pero se diferencia en que todos los participantes pertenecen a un solo grupo (en lugar de estar divididos en números iguales de "hombres" y "mujeres").
El problema de los hospitales / residentes , también conocido como el problema de admisión a la universidad , se diferencia del problema del matrimonio estable en que un hospital puede aceptar a varios residentes o una universidad puede aceptar una clase entrante de más de un estudiante. Los algoritmos para resolver el problema de los hospitales / residentes pueden estar orientados al hospital (como lo era el NRMP antes de 1995) [13] o al residente . Este problema se resolvió, con un algoritmo, en el mismo artículo original de Gale y Shapley, en el que se solucionó el problema del matrimonio estable. [8]
El problema de los hospitales / residentes con las parejas permite que el conjunto de residentes incluya parejas que deben ser asignadas juntas, ya sea al mismo hospital oa un par específico de hospitales elegidos por la pareja (por ejemplo, una pareja casada quiere asegurarse de que se quedarán juntos y no quedar atrapados en programas que están muy lejos unos de otros). La adición de parejas al problema de los hospitales / residentes hace que el problema sea NP-completo . [14]
El problema de asignación busca encontrar una coincidencia en un gráfico bipartito ponderado que tenga el peso máximo. Las coincidencias ponderadas máximas no tienen que ser estables, pero en algunas aplicaciones una coincidencia ponderada máxima es mejor que una 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 de contratos. [15] Un caso especial importante de contratos es el de los salarios flexibles. [dieciséis]
Ver también
- Emparejamiento (teoría de grafos) : emparejamiento entre diferentes vértices del gráfico; generalmente no está relacionado con el orden de preferencias.
- Emparejamiento sin envidia : una relajación de emparejamiento estable para problemas de emparejamiento de muchos a uno
- Coincidencia de arco iris para gráficos de color de borde
- Politopo a juego estable
Referencias
- ^ Algoritmos de correspondencia estables
- ^ "El premio de Ciencias Económicas 2012" . Nobelprize.org . Consultado el 9 de septiembre de 2013 .
- ^ a b Bruce Maggs y Ramesh Sitaraman (2015). "Pepitas algorítmicas en la entrega de contenido" (PDF) . Revisión de comunicación informática ACM SIGCOMM . 45 (3).
- ^ Gusfield, Dan (1987). "Tres algoritmos rápidos para cuatro problemas en el matrimonio estable". Revista SIAM de Computación . 16 (1): 111-128. doi : 10.1137 / 0216010 . Señor 0873255 .
- ^ Pittel, Boris (1989). "El número medio de emparejamientos estables". Revista SIAM de Matemática Discreta . 2 (4): 530–549. doi : 10.1137 / 0402048 . Señor 1018538 .
- ^ Karlin, Anna R .; Gharan, Shayan Oveis; Weber, Robbie (2018). "Un límite superior simplemente exponencial en el número máximo de emparejamientos estables". En Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.). Actas del 50 ° Simposio de Teoría de la Computación (STOC 2018) . Asociación para Maquinaria de Computación. págs. 920–925. arXiv : 1711.01032 . doi : 10.1145 / 3188745.3188848 . Señor 3826305 .
- ^ Irving, Robert W .; Cuero, Paul (1986). "La complejidad de contar matrimonios estables". Revista SIAM de Computación . 15 (3): 655–667. doi : 10.1137 / 0215048 . Señor 0850415 .
- ^ a b Gale, D .; Shapley, LS (1962). "Admisiones universitarias y estabilidad del matrimonio" . American Mathematical Monthly . 69 (1): 9-14. doi : 10.2307 / 2312726 . JSTOR 2312726 .
- ^ Harry Mairson : "El problema del matrimonio estable", The Brandeis Review 12, 1992 (en línea ).
- ^ Iwama, Kazuo ; Miyazaki, Shuichi (2008). "Una encuesta sobre el problema del matrimonio estable y sus variantes". Conferencia Internacional sobre Educación e Investigación en Informática para la Sociedad que Circula el Conocimiento (ICKS 2008) . IEEE. págs. 131-136. doi : 10.1109 / ICKS.2008.7 . hdl : 2433/226940 . ISBN 978-0-7695-3128-1.
- ^ Dubins, LE ; Freedman, DA (1981). "Maquiavelo y el algoritmo Gale-Shapley". American Mathematical Monthly . 88 (7): 485–494. doi : 10.2307 / 2321753 . JSTOR 2321753 . Señor 0628016 .
- ^ Huang, Chien-Chung (2006). "Engaños por hombres en el algoritmo de emparejamiento estable de Gale-Shapley". En Azar, Yossi; Erlebach, Thomas (eds.). Algoritmos - ESA 2006, 14º Simposio Europeo Anual, Zurich, Suiza, 11-13 de septiembre de 2006, Actas . Apuntes de conferencias en Ciencias de la Computación. 4168 . Saltador. págs. 418–431. doi : 10.1007 / 11841036_39 . Señor 2347162 .
- ^ Robinson, Sara (abril de 2003). "¿Están los estudiantes de medicina encontrando su (mejor) pareja posible?" (PDF) . Noticias SIAM (3): 36 . Consultado el 2 de enero de 2018 .
- ^ Gusfield, D .; Irving, RW (1989). El problema del matrimonio estable: estructura y algoritmos . Prensa del MIT. pag. 54. ISBN 0-262-07118-5.
- ^ Hatfield, John William; Milgrom, Paul (2005). "Coincidencia con contratos". American Economic Review . 95 (4): 913–935. doi : 10.1257 / 0002828054825466 . JSTOR 4132699 .
- ^ Crawford, Vincent; Knoer, Elsie Marie (1981). "Coincidencia de trabajo con empresas y trabajadores heterogéneos". Econometrica . 49 (2): 437–450. doi : 10.2307 / 1913320 . JSTOR 1913320 .
Otras lecturas
- Kleinberg, J. y Tardos, E. (2005) Algorithm Design , Capítulo 1, págs. 1-12. Consulte el sitio web complementario para el texto [1] .
- Knuth, DE (1996). Matrimonio estable y su relación con otros problemas combinatorios: una introducción al análisis matemático de algoritmos . Actas de CRM y notas de conferencias. Traducción en inglés. Sociedad Matemática Estadounidense.
- Pittel, B. (1992). "Sobre las posibles soluciones de un problema matrimonial estable" . Los anales de la probabilidad aplicada . 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) . Revista de Economía Política . 92 (6): 991–1016. doi : 10.1086 / 261272 .
- Roth, AE; Sotomayor, MAO (1990). Emparejamiento bilateral: un estudio sobre modelado y análisis de la teoría de juegos . Prensa de la Universidad de Cambridge .
- Shoham, Yoav; Leyton-Brown, Kevin (2009). Sistemas multiagente: fundamentos algorítmicos, teóricos de juegos y lógicos . Nueva York: Cambridge University Press . ISBN 978-0-521-89943-7.Consulte la Sección 10.6.4; descargable gratis en línea .
- Schummer, J .; Vohra, RV (2007). "Diseño de mecanismos sin dinero" (PDF) . En Nisan, Noam; Roughgarden, Tim; Tardos, Eva; Vazirani, Vijay (eds.). Teoría algorítmica de juegos . págs. 255-262. ISBN 978-0521872829.
enlaces externos
- Demostración interactiva en Flash de SMP
- 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
- Notas de la conferencia SMP