Problema de matrimonio estable
En matemáticas , economía e informática , el problema del matrimonio estable (también problema de coincidencia estable o SMP ) es el problema de encontrar una coincidencia 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. Un emparejamiento no es estable si:
En otras palabras, un emparejamiento es estable cuando no existe ningún emparejamiento ( A , B ) en el que ambos se prefieran a su pareja actual bajo el emparejamiento.
Dados 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 tal manera que no haya dos personas del sexo opuesto que prefieran tenerse el uno al otro que a sus parejas actuales. . Cuando no existen tales parejas de personas, el conjunto de matrimonios se considera estable.
La existencia de dos clases que deben emparejarse entre sí (hombres y mujeres heterosexuales en este ejemplo) distingue este problema del problema de los compañeros de habitación estables .
Los algoritmos para encontrar soluciones al problema del matrimonio estable tienen aplicaciones en una variedad de situaciones del mundo real, siendo quizás la más conocida 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 las asignaciones estables y la práctica del diseño de mercado". [2]
Una aplicación importante ya gran escala del matrimonio estable es la asignación de 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 coincida con uno de (potencialmente) cientos de miles de servidores en todo el mundo que ofrecen ese servicio. Un usuario prefiere servidores que sean 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 atender a los usuarios que puede con un menor costo, lo que resulta en un orden preferencial (parcial) de usuarios para cada servidor. Redes de entrega de contenidoque 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 coincidan con sus respectivos servidores que pueden proporcionar las páginas web, videos u otros servicios. [3]
