base de conocimiento
CTRL+F para buscar su palabra clave

Problema matrimonial estable

En matemática, economía y ciencias de la computación, 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 dada una ordenación de preferencias para cada elemento. Una coincidencia es una asignación de los elementos de un conjunto a los elementos del otro conjunto. Una coincidencia no es estable si:

  1. Hay un elemento A del primer conjunto emparejado que prefiere algún elemento B dado del segundo conjunto emparejado sobre el elemento al que A ya está emparejado, y
  2. 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 ) que ambos prefieran entre sí a su compañero actual bajo el emparejamiento.

El problema del matrimonio estable se ha declarado 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, cásese juntos con los hombres y las mujeres para que no haya dos personas del sexo opuesto que prefieran tener el uno al otro en lugar de sus parejas actuales. . Cuando no hay tales pares de personas, el conjunto de matrimonios se considera estable.

Tenga en cuenta que la existencia de dos clases que deben combinarse entre sí (hombres y mujeres en este ejemplo) distingue este problema del problema de los compañeros de cuarto 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. En 2012, el Premio Sveriges Riksbank en Ciencias Económicas en Memoria de Alfred Nobel 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 mercado".

Una aplicación importante y a gran escala del matrimonio estable es la asignación de usuarios a servidores en un gran servicio de Internet distribuido. 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 (potencialmente) de cientos de miles de servidores en todo el mundo que ofrecen ese servicio. Un usuario prefiere servidores que sean lo suficientemente próximos como para proporcionar un tiempo de respuesta más rápido para el servicio solicitado, lo que resulta en un pedido preferencial (parcial) de los servidores para cada usuario. Cada servidor prefiere servir a los usuarios con un costo menor, lo que resulta en un pedido preferencial (parcial) de usuarios para cada servidor. Las redes de distribución 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.

Solución

En 1962, David Gale y Lloyd Shapley demostraron que, para un número igual de hombres y mujeres, siempre es posible resolver el SMP y hacer que todos los matrimonios sean estables. Presentaron un algoritmo para hacerlo.

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 le propone matrimonio a la mujer que más prefiere, y luego b ) cada mujer responde "tal vez" a su pretendiente que ella prefiere y "no" a todos los demás pretendientes. Luego está provisionalmente "comprometida" con el pretendiente que más prefiere hasta ahora, y ese pretendiente también está provisionalmente comprometido con ella.
  • En cada ronda subsiguiente, primero a ) cada hombre no comprometido le propone matrimonio a la mujer más preferida a la que aún no se ha propuesto (independientemente de si la mujer ya está comprometida), y luego b ) cada mujer responde "tal vez" si está actualmente no está comprometida o si prefiere a este hombre sobre su actual pareja provisional (en este caso, rechaza a su actual pareja provisional que no está comprometida). La naturaleza provisional de los compromisos conserva el derecho de una mujer ya comprometida a "intercambiar" (y, en el proceso, a "sacudirla" hasta entonces pareja).
  • Este proceso se repite hasta que todos estén comprometidos.

La complejidad del tiempo de ejecución de este algoritmo es O (n2) {\ displaystyle O (n ^ {2})} donde n {\ displaystyle n} es el número de hombres o mujeres.

Este algoritmo garantiza que:

Todos se casan Al final, no puede haber un hombre y una mujer sin compromiso, ya que él debe haberle propuesto en algún momento (ya que un hombre eventualmente se lo propondrá a todos, si es necesario) y, si se lo propusiera, ella necesariamente lo haría estar comprometido (con alguien) a partir de entonces. Los matrimonios son estables Deje que Alice y Bob se comprometan, pero no el uno con el otro. Al completar el algoritmo, no es posible que tanto Alice como Bob se prefieran el uno al otro sobre sus socios actuales. Si Bob prefiere a Alice a su pareja actual, debe haberle propuesto a Alice antes de proponerle matrimonio a su pareja actual. Si Alice aceptó su propuesta, pero no está casada con él al final, debe haberlo dejado por alguien que le gusta más y, por lo tanto, no le gusta Bob más que su pareja actual. Si Alice rechazó su propuesta, ya estaba con alguien que le gustaba más que Bob.

Algoritmo

function stableMatching {Inicialice todos m ∈ M y w ∈ W para liberar mientras ∃ hombre libre m que todavía tiene una mujer w para proponer a {w = primera mujer en la lista de m a quien m aún no ha propuesto si w es libre (m, w) se compromete; de ​​lo contrario , ya existe algún par (m ', w) si w prefiere m a m' m 'se libera (m, w) se compromete; de ​​lo contrario (m', w) permanece comprometido }}

Diferentes combinaciones estables

En general, puede haber muchas coincidencias estables diferentes. Por ejemplo, supongamos 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 acuerdo de correspondencia:

  • los hombres obtienen 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 obtienen su primera opción y los hombres la tercera (AZ, BX, CY).

Los tres son estables, porque la inestabilidad requiere que uno de los participantes esté más feliz con una coincidencia alternativa. Darle a un grupo sus primeras opciones asegura que las coincidencias sean estables porque no estarían contentas con cualquier otra coincidencia propuesta. Dar a todos su segunda opción asegura que cualquier otra partida no le guste a ningún otro partido.

Optimidad de la solución.

La existencia de diferentes emparejamientos estables plantea la pregunta: ¿qué emparejamiento devuelve el algoritmo Gale-Shapley? ¿Es la combinación mejor para hombres, para mujeres o la intermedia? 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, selecciona esa propuesta como su mejor opción, asegurando que cada hombre tenga una oferta aceptada y finalice la coincidencia.

Este es un hecho general: el algoritmo 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.

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 sea 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 coincidencia en A. Esto significa que en A, m 0 ha visitado w 1, pero ella lo rechazó (esto se denota con la flecha verde de m 0 a w 1). w 1 lo rechazó a favor de un hombre que ella prefiere, digamos m 2. Entonces, en B, w 1 se corresponde con m 0 pero "anhela" (quiere pero no coincide) con m 2 (esto se denota con la flecha roja de w 1 a m 2).

Como B es una combinación estable, m 2 debe coincidir en B con alguna mujer que 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 en el ciclo, quien lo rechazó a favor del siguiente hombre en el ciclo. Pero esto es imposible ya que ese "ciclo de rechazos" no puede comenzar en ningún lado: supongamos por contradicción que comienza, por ejemplo, en m 0 - el primer hombre rechazado por su mujer adyacente ( w 1). Por supuesto, este rechazo ocurre solo después de que m 2 llega a w 1. Pero esto puede ocurrir solo después de que w 3 rechaza m 2, contradicción de que m 0 es el primero.

Consideraciones estratégicas

El algoritmo GS es un mecanismo verdadero desde el punto de vista de los hombres (el lado proponente). Es decir, ningún hombre puede obtener una mejor correspondencia para sí mismo al tergiversar sus preferencias. Además, el algoritmo GS es incluso una prueba de estrategia de grupo 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 mejor. Sin embargo, es posible que alguna coalición distorsione sus preferencias de modo que algunos hombres estén mejor y los otros retengan el mismo compañero.

El algoritmo GS no es verdadero para las mujeres (el lado de la revisión): cada mujer puede tergiversar sus preferencias y obtener una mejor coincidencia.

Contando los emparejamientos estables

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 e − 1nln⁡n {\ displaystyle e ^ {- 1} n \ ln n}.

El máximo crece al menos exponencialmente con n , y contar el número de coincidencias estables en una instancia dada es ♯P-completo.

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 de MatchMarkets y MatchR.
  • API: La API MatchingTools proporciona una interfaz de programación de aplicaciones gratuita para el algoritmo Gale – Shapley.
  • Python: el algoritmo Gale – Shapley se incluye junto con varios otros para problemas de coincidencia generalizados en el paquete QuantEcon / MatchingMarkets.py
  • Matlab: el algoritmo Gale-Shapley se implementa en la función asignar2DStable que forma parte de la Biblioteca de componentes de seguimiento gratuita del Laboratorio de Investigación Naval de los Estados Unidos.

Problemas similares

En una correspondencia 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 difiere en que todos los participantes pertenecen a un grupo único (en lugar de dividirse en un número igual de "hombres" y "mujeres").

El problema de los hospitales / residentes , también conocido como el problema de admisión a la universidad , difiere del problema del matrimonio estable en que un hospital puede acoger a varios residentes, o una universidad puede recibir una clase entrante de más de un estudiante. Los algoritmos para resolver el problema de los hospitales / residentes pueden estar orientados a los hospitales (como el NRMP era anterior a 1995) u orientados a los residentes . Este problema se resolvió, con un algoritmo, en el mismo documento original de Gale y Shapley, en el que se resolvió el problema del matrimonio estable.

El problema de los 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 que se quedarán juntos y no estar atrapados en programas que están lejos el uno del otro). La incorporación de parejas al problema de los hospitales / residentes hace que el problema sea NP completo.

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. Un caso especial importante de contratos es igualar con salarios flexibles.