Politopo de coincidencia estable

En matemáticas , economía e informática , el politopo de emparejamiento estable o politopo de matrimonio estable es un politopo convexo derivado de las soluciones a una instancia del problema de emparejamiento estable . ^{[ 1 ] [ 2 ]}

El politopo de emparejamiento estable es la envoltura convexa de los vectores indicadores de los emparejamientos estables del problema dado. Tiene una dimensión para cada par de elementos que pueden emparejarse y un vértice para cada emparejamiento estable. Para cada vértice, las coordenadas cartesianas son uno para los pares que se emparejan en el emparejamiento correspondiente y cero para los pares que no se emparejan. ^{[ 1 ]}

El politopo de emparejamiento estable tiene un número polinomial de facetas . Estas incluyen las desigualdades convencionales que describen los emparejamientos sin el requisito de estabilidad (cada coordenada debe estar entre 0 y 1, y para cada elemento que se empareja, la suma de las coordenadas de los pares que involucran a ese elemento debe ser exactamente uno), junto con desigualdades que restringen el emparejamiento resultante a ser estable (para cada par potencial de elementos emparejados, la suma de las coordenadas de los emparejamientos que son al menos igual de buenos para uno de los dos elementos debe ser al menos uno). Los puntos que satisfacen todas estas restricciones pueden considerarse como las soluciones fraccionarias de una relajación de programación lineal del problema de emparejamiento estable.

Es un teorema de Vande Vate (1989) que el politopo descrito por las restricciones de facetas enumeradas anteriormente tiene solo los vértices descritos anteriormente. En particular, es un politopo integral . Esto puede considerarse un análogo del teorema de Garrett Birkhoff que establece que un politopo análogo, el politopo de Birkhoff que describe el conjunto de todos los emparejamientos fraccionarios entre dos conjuntos, es integral. ^{[ 3 ]}

Una forma equivalente de enunciar el mismo teorema es que todo emparejamiento fraccional puede expresarse como una combinación convexa de emparejamientos enteros. Teo y Sethuraman (1998) lo demuestran construyendo una distribución de probabilidad sobre emparejamientos enteros cuyo valor esperado puede igualarse a cualquier emparejamiento fraccional dado. Para ello, realizan los siguientes pasos:

• Consideremos, para cada elemento de un lado del problema de emparejamiento estable (los médicos, por ejemplo, en un problema de emparejamiento de médicos con hospitales), los valores fraccionarios asignados a los emparejamientos con los elementos del otro lado (los hospitales), y ordenemos estos valores en orden descendente según las preferencias de ese médico.
• Divida el intervalo unitario en subintervalos, de longitudes iguales a estos valores fraccionarios, en el orden ordenado. Al elegir un número aleatorio dentro del intervalo unitario, se obtendrá una coincidencia aleatoria para el médico seleccionado, con una probabilidad igual al peso fraccionario de dicha coincidencia.
• De forma simétrica, considere para cada elemento del otro lado del emparejamiento estable (los hospitales), ordene los valores fraccionarios de los emparejamientos que involucran a ese elemento en orden creciente de preferencia, y construya una partición del intervalo unitario cuyos subintervalos tengan estos valores fraccionarios en el orden ordenado.
• Se puede demostrar que, para cada par emparejado, los subintervalos asociados a dicho par son idénticos tanto en la partición correspondiente al médico como en la partición correspondiente al hospital. Por lo tanto, al elegir un único número aleatorio en el intervalo unitario y utilizarlo para seleccionar simultáneamente un hospital para cada médico y un médico para cada hospital, se obtiene un emparejamiento. Además, se puede demostrar que este emparejamiento es estable.

El emparejamiento estable resultante, elegido aleatoriamente, selecciona cualquier par emparejado en particular con una probabilidad igual al valor de la coordenada fraccionaria de dicho par. Por lo tanto, la distribución de probabilidad sobre los emparejamientos estables construidos de esta manera proporciona una representación del emparejamiento fraccionario dado como una combinación convexa de emparejamientos estables enteros. ^{[ 4 ]}

La familia de todos los emparejamientos estables forma un retículo distributivo , el retículo de emparejamientos estables , en el que la unión de dos emparejamientos da a todos los médicos su preferencia entre los hospitales que les fueron asignados en los dos emparejamientos, y el encuentro da a todos los hospitales su preferencia. ^{[ 5 ]} Lo mismo ocurre con la familia de todos los emparejamientos estables fraccionarios, los puntos del politopo de emparejamientos estables. ^{[ 3 ]}

En el politopo de emparejamiento estable, se puede definir un emparejamiento como dominante sobre otro si, para cada médico y hospital, el valor fraccional total asignado a los emparejamientos para ese médico que son al menos tan buenos (para el médico) como ese hospital es al menos igual de grande en el primer emparejamiento que en el segundo. Esto define un orden parcial en los emparejamientos fraccionales. Este orden parcial tiene un único elemento máximo, el emparejamiento estable entero encontrado por una versión del algoritmo de Gale-Shapley en la que los médicos proponen emparejamientos y los hospitales responden a las propuestas. También tiene un único elemento mínimo, el emparejamiento estable entero encontrado por una versión del algoritmo de Gale-Shapley en la que los hospitales hacen las propuestas. ^{[ 3 ]}

De acuerdo con este orden parcial, se puede definir la coincidencia de dos emparejamientos fraccionarios como un emparejamiento fraccionario que sea lo más bajo posible en el orden parcial, dominando a los otros dos emparejamientos. Para cada médico y hospital, se asigna a ese par potencial un peso que hace que el peso total de ese par y de todos los pares mejores para el mismo médico sea igual al mayor de los totales correspondientes de los dos emparejamientos dados. La unión se define simétricamente. ^{[ 3 ]}

Al aplicar programación lineal al politopo de emparejamiento estable, se puede encontrar el emparejamiento estable de peso mínimo o máximo. ^{[ 1 ]} Los métodos alternativos para el mismo problema incluyen aplicar el problema de cierre a un conjunto parcialmente ordenado derivado de la red de emparejamientos estables , ^{[ 6 ]} o aplicar programación lineal al politopo de orden de este orden parcial.

La propiedad del politopo de emparejamiento estable, de definir una red distributiva continua, es análoga a la propiedad definitoria de un politopo distributivo , un politopo en el que la maximización y minimización por coordenadas forman las operaciones de intersección y unión de una red. ^{[ 7 ]} Sin embargo, las operaciones de intersección y unión para el politopo de emparejamiento estable se definen de manera diferente a la maximización y minimización por coordenadas. En cambio, el politopo de orden del orden parcial subyacente de la red de emparejamientos estables proporciona un politopo distributivo asociado con el conjunto de emparejamientos estables, pero uno para el cual es más difícil leer el valor fraccional asociado con cada par emparejado. De hecho, el politopo de emparejamiento estable y el politopo de orden del orden parcial subyacente están muy relacionados entre sí: cada uno es una transformación afín del otro. ^{[ 8 ]}