Problema de matrimonio estable
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:
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.
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 modo 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 .
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. 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 se emparejen con sus respectivos servidores que pueden proporcionar las páginas web, videos u otros servicios. [3]
