Solucionador del Problema del Matrimonio Estable

Solucionador del Problema del Matrimonio Estable

El Solucionador del Problema del Matrimonio Estable es una implementación interactiva del algoritmo de aceptación diferida de Gale-Shapley, el algoritmo de emparejamiento de 1962 que David Gale y Lloyd Shapley demostraron que siempre produce una pareja estable entre dos grupos de igual tamaño, dada la clasificación completa de cada miembro sobre el otro lado. Esta herramienta toma sus listas de preferencias, ejecuta el algoritmo paso a paso y muestra el resultado como un emparejamiento estable, una visualización bipartita animada, mapas de calor de preferencias y una prueba verificada de que no existen pares bloqueantes.

¿Qué es el problema del matrimonio estable?

Dados dos conjuntos disjuntos de igual tamaño — por ejemplo, n hombres y n mujeres, o n solicitantes y n puestos — y una lista completa de preferencias de cada miembro clasificando a cada miembro del otro lado, un emparejamiento es una asociación uno a uno entre los dos conjuntos. El emparejamiento se denomina estable si no existe ningún par (a, b) fuera del emparejamiento que prefiera estar juntos antes que quedarse con sus parejas asignadas.

Formalmente, un emparejamiento M es estable si no hay un par bloqueante — un par (a, b) con a emparejado con b' y b emparejado con a' tal que:

Si se cumplen ambas condiciones, tanto a como b abandonarían a sus parejas actuales, lo que desestabiliza el emparejamiento. Un emparejamiento estable es aquel en el que no existe tal par.

El algoritmo de Gale-Shapley

Gale y Shapley demostraron — de manera constructiva — que siempre existe un emparejamiento estable para cualquier conjunto de preferencias, y proporcionaron un algoritmo eficiente para encontrarlo. El algoritmo se ejecuta en rondas:

1. Cada proponente no comprometido propone al receptor de mayor rango en su lista que aún no lo haya rechazado.
2. Cada receptor que recibe una o más propuestas elige la que más prefiere (comparándola con cualquier prometido tentativo actual) y acepta tentativamente; todos los demás son rechazados.
3. Los proponentes rechazados quedan libres de nuevo y pasan a su siguiente opción en la siguiente ronda.
4. El algoritmo termina cuando cada proponente está comprometido, lo cual se garantiza que ocurra en un máximo de n² propuestas.

Propiedades teóricas clave

Existencia y unicidad

Siempre existe un emparejamiento estable (Gale y Shapley, 1962), pero no es necesariamente único. Para un conjunto de preferencias dado, puede haber múltiples emparejamientos estables, y estos forman un retículo ordenado por preferencia conjunta.

Optimalidad del proponente

Cuando un lado propone, Gale-Shapley produce el emparejamiento estable óptimo para el proponente: cada proponente recibe la mejor pareja que podría tener en cualquier emparejamiento estable. Por un argumento simétrico, este es también el emparejamiento pésimo para el receptor — el lado receptor obtiene su peor pareja estable. Cambiar el lado proponente en esta calculadora a menudo cambia el resultado.

A prueba de estrategias para proponentes

Bajo Gale-Shapley, los proponentes no tienen incentivos para falsear sus preferencias: decir la verdad es una estrategia dominante para ellos. Los receptores, sin embargo, a veces pueden beneficiarse de falsear sus preferencias estratégicamente — una de las razones por las que el mercado de hospitales y residentes en EE. UU. está diseñado con los estudiantes como el lado proponente.

Teorema de los hospitales rurales

El conjunto de agentes no emparejados es idéntico en todos los emparejamientos estables. Por lo tanto, si su instancia tiene tamaños desequilibrados (fuera del alcance de esta herramienta clásica), las mismas personas quedarán sin pareja en cada solución estable.

Formato de entrada

Esta calculadora espera una línea por miembro, con el nombre seguido de dos puntos y una lista completa de preferencias clasificadas separadas por comas:

Requisitos:

• Ambos grupos deben tener exactamente el mismo número de miembros.
• Cada miembro debe clasificar a cada miembro del otro grupo — no se admiten listas parciales.
• Los nombres pueden usar letras, dígitos, guiones bajos, guiones, espacios y letras Unicode comunes.
• Se admiten hasta 15 miembros por lado para una animación interactiva rápida.

Cómo usar esta calculadora

1. Ingrese las preferencias para el Grupo A en el área de texto de la izquierda — una línea por miembro, lista completa clasificada.
2. Ingrese las preferencias para el Grupo B en el área de texto de la derecha — una línea por miembro, mismo formato.
3. Elija el lado proponente. Elija el Grupo A o el Grupo B. Pruebe ambos para comparar los resultados óptimos para A vs. óptimos para B.
4. Haga clic en "Resolver Emparejamiento Estable". La calculadora ejecuta Gale-Shapley y produce las parejas estables, estadísticas, animación y prueba de estabilidad.
5. Desplace la animación con los controles de reproducción / paso / reinicio para ver cada propuesta, aceptación, intercambio y rechazo en orden.
6. Inspeccione el mapa de calor. Cada celda muestra la clasificación; las celdas con contorno amarillo forman el emparejamiento final — observe qué tan arriba o abajo están esas celdas para ver qué tan "feliz" es cada lado.

Ejemplo resuelto — El clásico 3×3

Hombres: Alex, Bryan, Chris. Mujeres: Bea, Claire, Diana. Preferencias:

Ejecutar Gale-Shapley con los hombres proponiendo produce Alex–Bea, Bryan–Claire, Chris–Diana en una sola ronda (la primera opción de cada hombre coincide con una mujer cuya primera opción es otra persona — sin conflicto). El emparejamiento es estable: ninguna pareja hombre-mujer estaría mejor intercambiando parejas, por lo que no hay par bloqueante.

Aplicaciones en el mundo real

Por qué Lloyd Shapley ganó un Premio Nobel

En 2012, la Real Academia de las Ciencias de Suecia otorgó el Premio Nobel de Economía a Lloyd Shapley (por la teoría, junto a David Gale que había fallecido) y Alvin Roth (por aplicar la teoría a mercados reales, incluido el rediseño del emparejamiento de residencias médicas en EE. UU. y las redes de intercambio de riñones). El premio citó "la teoría de las asignaciones estables y la práctica del diseño de mercados".

Preguntas frecuentes

¿Qué es el problema del matrimonio estable?

El problema del matrimonio estable pregunta: dados dos grupos del mismo tamaño donde cada miembro clasifica a todos los miembros del otro grupo del más al menos preferido, ¿podemos emparejar a todos de modo que no existan dos personas que prefieran dejar a sus parejas actuales para estar entre sí? Tal emparejamiento se llama emparejamiento estable. El algoritmo de Gale-Shapley resuelve este problema en un tiempo O(n²) y siempre encuentra un emparejamiento estable.

¿Cómo funciona el algoritmo de Gale-Shapley?

El algoritmo de aceptación diferida de Gale-Shapley procede por rondas. En cada ronda, cada proponente actualmente no comprometido propone al receptor de mayor rango en su lista que aún no lo haya rechazado. Cada receptor acepta tentativamente la mejor propuesta recibida hasta el momento y rechaza el resto; cualquier proponente desplazado queda libre de nuevo. El algoritmo termina cuando ningún proponente está libre, lo cual ocurre en un máximo de n² propuestas.

¿Es único el emparejamiento estable?

No. Una instancia de emparejamiento estable puede tener muchos emparejamientos estables. Sin embargo, cuando un lado propone, Gale-Shapley siempre produce el emparejamiento estable óptimo para el proponente: cada proponente obtiene la mejor pareja que podría obtener en cualquier emparejamiento estable. Por simetría, este es también el emparejamiento pésimo para el receptor del otro lado. Cambiar el lado proponente a menudo produce un emparejamiento estable diferente.

¿Qué es un par bloqueante?

Un par bloqueante es un par (a, b) que no está emparejado actualmente donde 'a' prefiere a 'b' sobre su pareja actual Y 'b' también prefiere a 'a' sobre su pareja actual. Si existe algún par bloqueante, el emparejamiento es inestable porque esos dos preferirían emparejarse entre sí. Un emparejamiento estable no tiene pares bloqueantes, lo cual esta calculadora verifica automáticamente después de cada resolución.

¿Cuáles son las aplicaciones reales del emparejamiento estable?

El algoritmo de Gale-Shapley impulsa el Programa Nacional de Emparejamiento de Residentes que asigna estudiantes de medicina a residencias en los Estados Unidos, sistemas de elección de escuelas en Boston y Nueva York, admisiones universitarias en varios países, cadenas de intercambio de riñones de donantes de órganos y sistemas de asignación de compañeros de cuarto. Lloyd Shapley y Alvin Roth ganaron el Premio Nobel de Economía en 2012 en parte por este trabajo.

¿Ambos grupos deben tener el mismo tamaño?

En la formulación clásica del matrimonio estable, sí. Ambos lados deben tener el mismo número de miembros y cada uno debe proporcionar una clasificación completa del otro lado. Existen variantes desequilibradas (como el emparejamiento estable con listas incompletas o el problema de hospitales y residentes) pero requieren algoritmos modificados. Esta calculadora impone tamaños iguales y listas de preferencias completas.

Lecturas adicionales

• Problema del matrimonio estable — Wikipedia
• Algoritmo de Gale-Shapley — Wikipedia
• National Resident Matching Program — Wikipedia (Inglés)
• Premio Nobel de Ciencias Económicas 2012 — Shapley y Roth