En matemáticas , economía y ciencias de la computación , particularmente en los campos de la combinatoria , la teoría de juegos y los algoritmos , el problema del compañero de habitación estable ( SRP ) es el problema de encontrar un emparejamiento estable para un conjunto de tamaño par. Un emparejamiento es una separación del conjunto en pares disjuntos ("compañeros de habitación"). El emparejamiento es estable si no hay dos elementos que no sean compañeros de habitación y que se prefieran mutuamente a su compañero de habitación bajo el emparejamiento. Esto se distingue del problema del matrimonio estable en que el problema de los compañeros de habitación estables permite emparejamientos entre dos elementos cualesquiera, no solo entre clases de "hombres" y "mujeres".
Comúnmente se expresa así:
A diferencia del problema del matrimonio estable , puede que no exista una correspondencia estable para ciertos grupos de participantes y sus preferencias. Para un ejemplo mínimo de una correspondencia estable que no existe, considere 4 personas A , B , C y D , cuyas clasificaciones son:
En esta clasificación, cada uno de A, B y C es la persona más preferible para alguien. En cualquier solución, uno de A, B o C debe emparejarse con D y los otros dos entre sí (por ejemplo, AD y BC), pero para cualquiera que esté emparejado con D, otro miembro lo habrá calificado como el más alto, y el compañero de D, a su vez, preferirá a este otro miembro sobre D. En este ejemplo, AC es una pareja más favorable que AD, pero el emparejamiento restante necesario de BD plantea el mismo problema, lo que ilustra la ausencia de una correspondencia estable para estos participantes y sus preferencias.
Un algoritmo eficiente (Irving 1985) es el siguiente. El algoritmo determinará, para cualquier instancia del problema, si existe una correspondencia estable y, de ser así, la encontrará. El algoritmo de Irving tiene una complejidad O( n 2 ) , siempre que se utilicen estructuras de datos adecuadas para implementar la manipulación necesaria de las listas de preferencias y la identificación de rotaciones.
El algoritmo consta de dos fases. En la fase 1, los participantes se proponen entre sí, de una manera similar a la del algoritmo de Gale-Shapley para el problema del matrimonio estable . Cada participante ordena a los demás miembros por preferencia, lo que da como resultado una lista de preferencias, un conjunto ordenado de los demás participantes. Luego, los participantes proponen a cada persona de su lista, en orden, y continúan con la siguiente persona si su propuesta actual es rechazada. Un participante rechazará una propuesta si ya tiene una propuesta de alguien a quien prefiere. Un participante también rechazará una propuesta previamente aceptada si luego recibe una propuesta que prefiere. En este caso, el participante rechazado le propondrá matrimonio a la siguiente persona en su lista, y así sucesivamente hasta que se acepte nuevamente una propuesta. Si algún participante finalmente es rechazado por todos los demás participantes, esto indica que no es posible una coincidencia estable. De lo contrario, la fase 1 finalizará con cada persona que tenga una propuesta de uno de los otros.
Consideremos dos participantes, q y p . Si q tiene una propuesta de p , entonces eliminamos de la lista de q todos los participantes x después de p , y simétricamente, por cada participante eliminado x , eliminamos q de la lista de x , de modo que q es el primero en la lista de p ; y p , el último en la de q , ya que q y cualquier x no pueden ser socios en ninguna coincidencia estable. El conjunto reducido resultante de listas de preferencias juntas se llama tabla de Fase 1. En esta tabla, si alguna lista reducida está vacía, entonces no hay coincidencia estable. De lo contrario, la tabla de Fase 1 es una tabla estable . Una tabla estable, por definición, es el conjunto de listas de preferencias de la tabla original después de que los miembros han sido eliminados de una o más de las listas, y se satisfacen las siguientes tres condiciones (donde lista reducida significa una lista en la tabla estable):
(i) p es el primero en la lista reducida de q si y solo si q es el último en la de p
(ii) p no está en la lista reducida de q si y solo si q no está en la de p si y solo si q prefiere a la última persona en su lista a p ; o p , la última persona en su lista a q
(iii) ninguna lista reducida está vacía
Las tablas estables tienen varias propiedades importantes, que se utilizan para justificar el resto del procedimiento:
Estas eliminaciones de rotación comprenden la Fase 2 del algoritmo de Irving.
Por 2, si cada lista reducida de la tabla de la Fase 1 contiene exactamente un individuo, entonces esto da una coincidencia.
De lo contrario, el algoritmo entra en la Fase 2. Una rotación en una tabla estable T se define como una secuencia ( x 0 , y 0 ), ( x 1 , y 1 ), ..., ( x k-1 , y k-1 ) tal que los x i son distintos, y i es el primero en la lista reducida de x i (o x i es el último en la lista reducida de y i ) e y i+1 es el segundo en la lista reducida de x i , para i = 0, ..., k-1 donde los índices se toman módulo k. De ello se deduce que en cualquier tabla estable con una lista reducida que contenga al menos dos individuos, dicha rotación siempre existe. Para encontrarlo, comience en un p 0 que contenga al menos dos individuos en su lista reducida, y defina recursivamente q i+1 como el segundo en la lista de p i y p i+1 como el último en la lista de q i+1 , hasta que esta secuencia repita algún p j , en cuyo punto se encuentra una rotación: es la secuencia de pares que comienza en la primera ocurrencia de ( p j , q j ) y termina en el par anterior a la última ocurrencia. La secuencia de p i hasta p j se llama cola de la rotación. El hecho de que sea una tabla estable en la que ocurre esta búsqueda garantiza que cada p i tenga al menos dos individuos en su lista.
Para eliminar la rotación, y i rechaza x i de modo que x i propone y i+1 , para cada i . Para restaurar las propiedades de tabla estable (i) y (ii), para cada i , todos los sucesores de x i-1 se eliminan de la lista de y i , y y i se elimina de sus listas. Si una lista reducida se vacía durante estas eliminaciones, entonces no hay coincidencia estable. De lo contrario, la nueva tabla es nuevamente una tabla estable, y ya especifica una coincidencia ya que cada lista contiene exactamente un individuo o queda otra rotación para encontrar y eliminar, por lo que se repite el paso.
La fase 2 del algoritmo ahora se puede resumir de la siguiente manera:
T = Tabla de fase 1 ; mientras ( verdadero ) { identifica una rotación r en T ; elimina r de T ; si alguna lista en T se vuelve vacía , devuelve nulo ; ( no puede existir una coincidencia estable ) de lo contrario , si ( cada lista reducida en T tiene tamaño 1 ) devuelve la coincidencia M = {{ x , y } | x e y están en las listas de cada uno en T }; ( esta es una coincidencia estable ) } Para lograr un tiempo de ejecución O( n2 ), se crea una matriz de clasificación cuya entrada en la fila i y la columna j es la posición del individuo j en la lista del i ; esto lleva un tiempo O( n2 ). Con la matriz de clasificación, se puede verificar si un individuo prefiere a uno sobre otro en tiempo constante comparando sus rangos en la matriz. Además, en lugar de eliminar explícitamente elementos de las listas de preferencias, se mantienen los índices del primero, segundo y último en la lista reducida de cada individuo. También se mantiene el primer individuo que no coincide , es decir, que tiene al menos dos en sus listas reducidas. Luego, en la Fase 2, la secuencia de p i "recorrida" para encontrar una rotación se almacena en una lista, y se utiliza una matriz para marcar a los individuos como visitados, como en un recorrido de gráfico de búsqueda en profundidad estándar . Después de eliminar una rotación, continuamos almacenando solo su cola, si la hay, en la lista y como se visitó en la matriz, y comenzamos la búsqueda de la próxima rotación en el último individuo en la cola, y de lo contrario en el siguiente individuo no coincidente si no hay cola. Esto reduce el recorrido repetido de la cola, ya que en gran medida no se ve afectado por la eliminación de la rotación.
Las siguientes son las listas de preferencias para una instancia de Stable Roommates que involucra a 6 participantes: 1, 2, 3, 4, 5, 6.
1: 3 4 2 6 5
2: 6 5 4 1 3
3:
2 4 5 1 6 4 : 5 2 3 6 1
5: 3 1 2 4 6
6: 5 1 3 4 2
Una posible ejecución de la Fase 1 consiste en la siguiente secuencia de propuestas y rechazos, donde → representa propone y × representa rechaza .
1 → 3
2 → 6
3 → 2
4 → 5
5 → 3; 3 × 1
1 → 4
6 → 5; 5 × 6
6 → 1
Así, la Fase 1 termina con las siguientes listas de preferencias reducidas: (por ejemplo, tachamos 5 por 1: porque 1: obtiene al menos 6)
1 : 3 4 2 6 5
2 : 654133
: 245
1 6
4 : 523615
: 3
1 2 4 6
6 : 5 1 3 4 2
En la fase 2, primero se identifica la rotación r 1 = (1,4), (3,2). Esto se debe a que 2 es el segundo favorito de 1 y 4 es el segundo favorito de 3. Al eliminar r 1 se obtiene:
1 : 3 4 2 6 5
2
: 6541 3
3 : 2 4 5 1 6
4
: 523 6 1
5: 3 1 2 4 6
6 : 5 1 3 4 2
A continuación, se identifica la rotación r 2 = (1,2), (2,6), (4,5) y su eliminación da como resultado:
1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5: 3 1 2 4 6
6 : 5 1 3 4 2
Por lo tanto, 1 y 6 coinciden. Finalmente, se identifica la rotación r 3 = (2,5), (3,4) y su eliminación da:
1 : 3 4 2 6 5
2 : 6 5 4 1 3
3 : 2 4 5 1 6
4 : 5 2 3 6 1
5: 3 1 2 4 6
6 : 5 1 3 4 2
Por lo tanto, la coincidencia {1, 6}, {2,4}, {3, 5} es estable.
matchingbiblioteca. [1]matchingMarketspaquete R. [4] [5]assignStableRoommatesfunción que forma parte de la biblioteca de componentes Tracker gratuita del Laboratorio de Investigación Naval de los Estados Unidos . [8]