En matemáticas , economía e informática , particularmente en los campos de combinatoria , teoría de juegos y algoritmos , el problema del compañero de cuarto estable ( SRP ) es el problema de encontrar una coincidencia estable para un conjunto de tamaño par. Un emparejamiento es una separación del conjunto en pares disjuntos ("compañeros de cuarto"). El emparejamiento es estable si no hay dos elementos que no sean compañeros de cuarto y que ambos se prefieran a su compañero de cuarto bajo el emparejamiento. Esto es distinto del problema del matrimonio estable. en que el problema de los compañeros de cuarto estables permite coincidencias entre dos elementos cualesquiera, no solo entre clases de "hombres" y "mujeres".
A diferencia del problema del matrimonio estable , es posible que no exista un emparejamiento estable para ciertos conjuntos de participantes y sus preferencias. Para un ejemplo mínimo de un emparejamiento estable que no existe, considere 4 personas A , B , C y D , cuyas clasificaciones son:
En este ranking, 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), sin embargo, para cualquiera que esté asociado con D, otro miembro lo habrá calificado más alto, y El compañero de D, a su vez, preferirá a este otro miembro sobre D. En este ejemplo, AC es un emparejamiento más favorable que AD, pero el emparejamiento restante necesario de BD plantea el mismo problema, ilustrando la ausencia de un emparejamiento estable para estos participantes y su preferencias
Se proporcionó un algoritmo eficiente en ( Irving 1985 ). [1] El algoritmo determinará, para cualquier instancia del problema, si existe una coincidencia estable y, de ser así, encontrará dicha coincidencia. 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 las rotaciones.
El algoritmo consiste en dos fases. En la Fase 1, los participantes se proponen matrimonio , de manera similar al 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 en su lista, en orden, continuando con la siguiente persona si su propuesta actual es rechazada. Un participante rechazará una propuesta si ya tiene una propuesta de alguien que prefiere. Un participante también rechazará una propuesta aceptada previamente si luego recibe una propuesta que prefiere. En este caso, el participante rechazado luego propondrá a la siguiente persona en su lista, continuando 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 terminará con cada persona con una propuesta de los demás.
Considere 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, para cada participante x eliminado , eliminamos q de la lista de x , de modo que q sea el primero en la lista de p ; y p , último en q ' s, ya que q y cualquier xno pueden ser socios en ningún emparejamiento estable. El conjunto reducido de listas de preferencias resultante se denomina tabla de fase 1. En esta tabla, si alguna lista reducida está vacía, entonces no hay coincidencia estable. De lo contrario, la mesa de la Fase 1 es una mesa estable . Una tabla estable, por definición, es el conjunto de listas de preferencias de la tabla original después de que se hayan eliminado miembros de una o más de las listas y se cumplan las siguientes tres condiciones (donde lista reducida significa una lista en la tabla estable):