En matemáticas , economía e informática , el algoritmo Gale-Shapley (también conocido como algoritmo de aceptación diferida o algoritmo de propuesta y rechazo ) es un algoritmo para encontrar una solución al problema de emparejamiento estable , llamado así por David Gale y Lloyd Shapley quien lo había descrito como la solución tanto del problema de admisión a la universidad como del matrimonio estable . Se necesita tiempo polinomial y el tiempo es lineal en el tamaño de la entrada al algoritmo. Es unmecanismo veraz desde el punto de vista de los proponentes, para quienes la solución siempre será óptima.
Fondo
El problema de emparejamiento estable, en su forma más básica, toma como entrada un número igual de dos tipos de participantes ( n hombres y n mujeres, o n estudiantes de medicina y n pasantías, por ejemplo), y un orden para cada participante dando su preferencia por con quién ser emparejado entre los participantes del otro tipo. Siempre existe una coincidencia estable, y el problema algorítmico resuelto por el algoritmo Gale-Shapley es encontrar una. 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, una coincidencia es estable cuando no hay coincidencia ( A , B ) donde ambos participantes prefieren a otra persona a su pareja actual.
Solución
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. [1] [2] En 1984, Alvin E. Roth observó que esencialmente el mismo algoritmo ya había estado en uso práctico desde principios de la década de 1950, en el Programa Nacional de Emparejamiento de Residentes . [3]
El algoritmo Gale-Shapley 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.
La complejidad en tiempo de ejecución de este algoritmo es dónde es el número de hombres o mujeres. [4] Dado que las listas de preferencias de entrada también tienen un tamaño proporcional a, el tiempo de ejecución es lineal en el tamaño de entrada.
Este algoritmo garantiza que:
- Todo el mundo se casa
- Al final, no puede haber un hombre y una mujer ambos sin compromiso, ya que él debe haberle propuesto matrimonio en algún momento (ya que un hombre eventualmente se lo propondrá a todos, si es necesario) y, al ser propuesto, ella necesariamente estaría comprometida ( a alguien) a partir de entonces.
- Los matrimonios son estables
- Deje que Alice y Bob estén comprometidos, pero no entre ellos. Una vez completado el algoritmo, no es posible que tanto Alice como Bob se prefieran entre sí sobre sus socios actuales. Si Bob prefiere a Alice a su pareja actual, debe haberle propuesto matrimonio a Alice antes de proponerle matrimonio a su pareja actual. Si Alice aceptó su propuesta, pero al final no está casada con él, debe haberlo dejado por alguien que le gusta más y, por lo tanto, no le gusta más Bob que su actual pareja. Si Alice rechazó su propuesta, ya estaba con alguien que le gustaba más que Bob.
Algoritmo
algoritmo stable_matching es Inicializar m ∈ M y w ∈ W para liberar mientras ∃ hombre libre m que tiene una mujer w para proponer hacer w: = primera mujer en la lista de m a la que m aún no le ha propuesto matrimonio si ∃ algún par (m ', w) entonces si w prefiere m a m' entonces m 'queda libre (m, w) se engancha y si de lo contrario (m, w) se engancha fin si se repite
Optimidad de la solución
La existencia de diferentes emparejamientos estables plantea la pregunta: ¿qué emparejamiento devuelve el algoritmo Gale-Shapley? ¿Es el emparejamiento mejor para hombres, mujeres o intermedio? En el ejemplo anterior, el algoritmo converge en una sola ronda en la solución óptima para hombres porque cada mujer recibe exactamente una propuesta y, por lo tanto, elige esa propuesta, asegurando que cada hombre tenga una oferta aceptada, finalizando el emparejamiento.
Este es un hecho general: el algoritmo de Gale-Shapley en el que los hombres proponen a las mujeres siempre produce una coincidencia estable que es la mejor para todos los hombres entre todas las coincidencias estables. Del mismo modo, si las mujeres proponen, la combinación resultante es la mejor para todas las mujeres entre todas las combinaciones estables. Estos dos emparejamientos son los elementos superior e inferior del enrejado de emparejamientos estables .
Para ver esto, considere la ilustración de la derecha. Sea A el emparejamiento generado por el algoritmo de proposición de hombres y B un emparejamiento estable alternativo que es mejor para al menos un hombre, digamos m 0 . Suponga que m 0 coincide en B con una mujer w 1 , que él prefiere a su pareja en A. Esto significa que en A, m 0 ha visitado w 1 , pero ella lo rechazó (esto se indica con la flecha verde de m 0 a w 1 ). w 1 lo rechazaron en favor de un hombre que prefiere, digamos m 2 . Entonces, en B, w 1 se corresponde con m 0 pero "anhela" (quiere pero no se iguala ) m 2 (esto se indica con la flecha roja de w 1 a m 2 ).
Dado que B es una coincidencia estable, m 2 debe coincidir en B con alguna mujer que él prefiera w 1 , digamos w 3 . Esto significa que en A, m 2 ha visitado w 3 antes de llegar a w 1 , lo que significa que w 3 lo ha rechazado. Por consideraciones similares, y dado que el gráfico es finito, eventualmente debemos tener un ciclo dirigido en el que cada hombre fue rechazado en A por la siguiente mujer del ciclo, quien lo rechazó a favor del siguiente hombre del ciclo. Pero esto es imposible ya que tal "ciclo de rechazos" no puede comenzar en ninguna parte: supongamos por contradicción que comienza en, por ejemplo, m 0 - el primer hombre rechazado por su mujer adyacente ( w 1 ). Por supuesto, este rechazo ocurre solo después de que m 2 llegue a w 1 . Pero esto puede suceder solo después de que w 3 rechace m 2 , siendo la primera contradicción con m 0 .
Consideraciones estratégicas
El algoritmo GS 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 modo que todos los hombres de la coalición estén estrictamente en mejor situación. [5] 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. [6]
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.
Implementación en paquetes de software
- R : El algoritmo Gale-Shapley (también conocido como algoritmo de aceptación diferida) para el matrimonio estable y el problema de los hospitales / residentes está disponible como parte de los paquetes
matchingMarkets
[7] [8] ymatchingR
[9] . - API : la API MatchingTools proporciona una interfaz de programación de aplicaciones gratuita para el algoritmo Gale-Shapley. [10]
- Python : el algoritmo Gale-Shapley se incluye junto con varios otros algoritmos de juegos de emparejamiento bien conocidos en la
matching
biblioteca, [11] y elQuantEcon/MatchingMarkets.py
paquete [12] incluye varios otros para juegos de emparejamiento generalizados. - MATLAB : El algoritmo Gale-Shapley se implementa en la
assign2DStable
función que forma parte de la biblioteca gratuita de componentes de seguimiento del Laboratorio de Investigación Naval de los Estados Unidos . [13]
Reconocimiento
Shapley y Roth fueron galardonados con el Premio Nobel de Ciencias Económicas en 2012 "por la teoría de las asignaciones estables y la práctica del diseño de mercado "; Gale había muerto en 2008 [14].
Ver también
Referencias
- ↑ 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 ).
- ^ Bergstrom, Theodore C. (junio de 1992). "Revisión de emparejamiento de dos caras: un estudio en el modelado y análisis de teoría de juegos por AE Roth y MAO Sotomayor". Revista de Literatura Económica . 30 (2): 896–898. JSTOR 2727713 .
- ^ Iwama, Kazuo ; Miyazaki, Shuichi (2008). "Una encuesta sobre el problema del matrimonio estable y sus variantes" (PDF) . Conferencia Internacional sobre Educación e Investigación en Informática para la Sociedad que Circula el Conocimiento (icks 2008) : 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 . 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 .
- ^ Klein, T. (2015). "Análisis de coincidencias estables en R: Package matchingMarkets" (PDF) . Vignette to R Package MatchingMarkets .
- ^ "MatchingMarkets: análisis de coincidencias estables" . Proyecto R .
- ^ "matchingR: algoritmos coincidentes en R y C ++" . Proyecto R .
- ^ "API MatchingTools" .
- ^ Wilde, H .; Knight, V .; Gillard, J. (2020). "Coincidencia: una biblioteca de Python para resolver juegos de correspondencias" . Revista de software de código abierto . doi : 10.21105 / joss.02169 .
- ^ "matchingMarkets.py" . Paquete de Python .
- ^ "Biblioteca de componentes del rastreador" . Repositorio de Matlab . Consultado el 5 de enero de 2019 .
- ^ "Combinación perfecta de los premios Nobel de economía" . Science Mag . Consultado el 5 de diciembre de 2020 .
enlaces externos
- Demostración de JavaScript de Gale-Shapley