En matemáticas , economía e informática , el politopo de emparejamiento estable o el politopo de matrimonio estable es un politopo convexo derivado de las soluciones a una instancia del problema de emparejamiento estable . [1] [2]
Descripción
El politopo de emparejamiento estable es el casco convexo de los vectores indicadores de los emparejamientos estables del problema dado. Tiene una dimensión para cada par de elementos que se pueden emparejar y un vértice para cada emparejamiento estable. Para cada vértice, las coordenadas cartesianas son una para los pares que coinciden en la coincidencia correspondiente y cero para los pares que no coinciden. [1]
El politopo de coincidencia estable tiene un número polinómico de facetas . Estos incluyen las desigualdades convencionales que describen coincidencias sin el requisito de estabilidad (cada coordenada debe estar entre 0 y 1, y para que cada elemento coincida, la suma de coordenadas de los pares que involucran ese elemento debe ser exactamente uno), junto con las desigualdades que restringen el la coincidencia resultante sea estable (para cada par de elementos coincidentes potenciales, la suma de las coordenadas de las coincidencias que sean al menos tan buenas 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.
Integridad
Es un teorema de Vande Vate (1989) que el politopo descrito por las restricciones de facetas enumeradas anteriormente solo tiene los vértices descritos anteriormente. En particular, es un politopo integral . Esto puede verse como un análogo del teorema de Garrett Birkhoff de que un politopo análogo, el politopo de Birkhoff que describe el conjunto de todas las coincidencias fraccionarias entre dos conjuntos, es integral. [3]
Una forma equivalente de enunciar el mismo teorema es que cada emparejamiento fraccionario se puede expresar como una combinación convexa de emparejamientos integrales. Teo y Sethuraman (1998) prueban esto mediante la construcción de una distribución de probabilidad sobre emparejamientos integrales cuyo valor esperado se puede establecer igual a cualquier emparejamiento fraccional dado. Para ello, realizan los siguientes pasos:
- Considere para cada elemento de un lado del problema de correspondencia estable (los médicos, por ejemplo, en un problema de vinculación de médicos con hospitales) los valores fraccionarios asignados a los emparejamientos con los elementos del otro lado (los hospitales), y ordene estos valores en orden decreciente ordenar 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. La elección de un número aleatorio en el intervalo unitario dará una coincidencia aleatoria para el médico seleccionado, con una probabilidad igual al peso fraccionario de esa coincidencia.
- Simétricamente, considere para cada elemento en el otro lado de la coincidencia estable (los hospitales), ordene los valores fraccionarios para los emparejamientos que involucren ese elemento en orden creciente por preferencia, y construya una partición del intervalo unitario cuyos subintervalos tienen estos valores fraccionarios en el orden ordenado.
- Se puede probar que, para cada par emparejado, los subintervalos asociados con ese par son los mismos tanto en la partición del médico como en la partición del hospital de ese par. Por lo tanto, elegir un solo número aleatorio en el intervalo de la unidad y usar esa opción para seleccionar simultáneamente un hospital para cada médico y un médico para cada hospital, da una coincidencia. Además, se puede demostrar que esta coincidencia es estable.
El emparejamiento estable resultante elegido al azar elige cualquier par emparejado particular con probabilidad igual al valor de la coordenada fraccionaria de ese par. Por lo tanto, la distribución de probabilidad sobre emparejamientos estables construida de esta manera proporciona una representación del emparejamiento fraccional dado como una combinación convexa de emparejamientos integrales estables. [4]
Celosía de coincidencias fraccionarias
La familia de todos los emparejamientos estables forma un entramado distributivo , el entramado de emparejamientos estables , en el que la unión de dos emparejamientos da a todos los médicos su preferencia entre sus hospitales 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 fraccionales, los puntos del politopo de emparejamiento estable. [3]
En el politopo de emparejamiento estable, se puede definir un emparejamiento para dominar a otro si, para cada médico y hospital, el valor fraccionario 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 grande en la primera coincidencia como en la segunda. Esto define un orden parcial en las coincidencias fraccionarias. Este orden parcial tiene un elemento único más grande, el emparejamiento estable entero encontrado por una versión del algoritmo Gale-Shapley en el que los médicos proponen coincidencias y los hospitales responden a las propuestas. También tiene un elemento más pequeño único, la coincidencia estable de enteros encontrada por una versión del algoritmo Gale-Shapley en el que los hospitales hacen las propuestas. [3]
De forma coherente con este orden parcial, se puede definir el encuentro de dos emparejamientos fraccionarios como un emparejamiento fraccionario que sea lo más bajo posible en el orden parcial mientras se dominan los dos emparejamientos. Para cada médico y hospital, asigna a ese par emparejado potencial un peso que hace que el peso total de ese par y todos los pares mejores para el mismo médico sean iguales al mayor de los totales correspondientes de los dos emparejamientos dados. La unión se define simétricamente. [3]
Aplicaciones
Al aplicar la programación lineal al politopo de coincidencia estable, se puede encontrar la coincidencia 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.
Relación con el pedido de politopo
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 encuentro y unión de una red. [7] Sin embargo, las operaciones de encuentro y unión para el politopo de coincidencia estable se definen de una 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 que es más difícil leer el valor fraccionario asociado con cada par emparejado. De hecho, el politopo de coincidencia estable y el politopo de orden del orden parcial subyacente están estrechamente relacionados entre sí: cada uno es una transformación afín del otro. [8]
Referencias
- ^ a b c Vande Vate, John H. (1989), "La programación lineal trae felicidad conyugal", Cartas de investigación de operaciones , 8 (3): 147-153, doi : 10.1016 / 0167-6377 (89) 90041-2 , MR 1007271
- ^ Ratier, Guillaume (1996), "Sobre el politopo del matrimonio estable" (PDF) , Matemáticas discretas , 148 (1-3): 141-159, doi : 10.1016 / 0012-365X (94) 00237-D , MR 1368286
- ^ a b c d Roth, Alvin E .; Rothblum, Uriel G .; Vande Vate, John H. (1993), "Emparejamientos estables, asignaciones óptimas y programación lineal", Mathematics of Operations Research , 18 (4): 803–828, doi : 10.1287 / moor.18.4.803 , JSTOR 3690124 , MR 1251681
- ^ Teo, Chung-Piaw; Sethuraman, Jay (1998), "La geometría de las correspondencias estables fraccionarias y sus aplicaciones", Matemáticas de la investigación de operaciones , 23 (4): 874–891, doi : 10.1287 / moor.23.4.874 , MR 1662426
- ^ Knuth, Donald E. (1976), Mariages stables et leurs Relations avec d'autres problèmes combinatoires (PDF) (en francés), Montreal, Quebec: Les Presses de l'Université de Montréal, ISBN 0-8405-0342-3, MR 0488980. Véase en particular el problema 6, págs. 87-94.
- ^ Irving, Robert W .; Cuero, Paul; Gusfield, Dan (1987), "Un algoritmo eficiente para el matrimonio estable" óptimo ", Journal of the ACM , 34 (3): 532–543, doi : 10.1145 / 28869.28871 , MR 0904192
- ^ Felsner, Stefan; Knauer, Kolja (2011), "Rejillas distributivas, poliedros y flujos generalizados", European Journal of Combinatorics , 32 (1): 45–59, doi : 10.1016 / j.ejc.2010.07.011 , MR 2727459.
- ^ Aprile, Manuel; Cevallos, Alfonso; Faenza, Yuri (2018), "Sobre politopos de 2 niveles que surgen en entornos combinatorios", SIAM Journal on Discrete Mathematics , 32 (3): 1857–1886, arXiv : 1702.03187 , doi : 10.1137 / 17M1116684 , MR 3835234