En matemáticas , economía e informática , el entramado de emparejamientos estables es un entramado distributivo cuyos elementos son emparejamientos estables . Para un caso dado del problema de emparejamiento estable, este enrejado proporciona una descripción algebraica de la familia de todas las soluciones al problema. Fue descrito originalmente en la década de 1970 por John Horton Conway y Donald Knuth . [1] [2]
Según el teorema de representación de Birkhoff , este enrejado puede representarse como los conjuntos inferiores de un conjunto subyacente parcialmente ordenado , y los elementos de este conjunto pueden recibir una estructura concreta como rotaciones, gráficos de ciclo que describen los cambios entre coincidencias estables adyacentes en el enrejado. La familia de todas las rotaciones y su orden parcial se puede construir en tiempo polinomial , lo que lleva al tiempo polinomial para otros problemas de correspondencia estable, incluida la correspondencia estable de peso mínimo o máximo. El algoritmo Gale-Shapley se puede utilizar para construir dos elementos de celosía especiales, su elemento superior e inferior.
Cada red distributiva finita se puede representar como una red de emparejamientos estables. El número de elementos en la celosía puede variar de un caso promedio deal peor de los casos exponencial. Calcular el número de elementos es # P-completo .
Fondo
En su forma más simple, una instancia del problema de emparejamiento estable consta de dos conjuntos del mismo número de elementos que deben emparejarse entre sí, por ejemplo, médicos y puestos en hospitales. Cada elemento tiene un orden de preferencia sobre los elementos del otro tipo: los médicos tienen preferencias diferentes para el hospital en el que les gustaría trabajar (por ejemplo, en función de las ciudades en las que preferirían vivir), y los hospitales tienen preferencias. para qué médicos les gustaría trabajar para ellos (por ejemplo, según la especialización o las recomendaciones). El objetivo es encontrar una coincidencia estable : ninguna pareja de médico y hospital se prefieren entre sí a la coincidencia asignada. Las versiones de este problema son utilizadas, por ejemplo, por el Programa Nacional de Emparejamiento de Residentes para emparejar a los estudiantes de medicina estadounidenses con los hospitales. [3]
En general, puede haber muchas coincidencias estables diferentes. Por ejemplo, suponga que hay tres médicos (A, B, C) y tres hospitales (X, Y, Z) que tienen preferencias de:
- A: YXZ B: ZYX C: XZY
- X: BAC Y: CBA Z: ACB
Hay tres soluciones estables para este arreglo de emparejamiento:
- Los médicos obtienen su primera opción y los hospitales la tercera: AY, BZ, CX.
- Todos los participantes obtienen su segunda opción: AX, BY, CZ.
- Los hospitales obtienen su primera opción y los médicos la tercera: AZ, BX, CY.
El enrejado de emparejamientos estables organiza esta colección de soluciones, para cualquier caso de emparejamiento estable, dándole la estructura de un enrejado distributivo . [1]
Estructura
Orden parcial de emparejamientos
La red de emparejamientos estables se basa en la siguiente estructura más débil, un conjunto parcialmente ordenado cuyos elementos son los emparejamientos estables. Definir una operación de comparación en los emparejamientos estables, donde si y solo si todos los médicos prefieren la coincidencia hacer coincidir : o tienen el mismo hospital asignado en ambos emparejamientos, o se les asigna un mejor hospital en de lo que están en . Si los médicos no están de acuerdo sobre qué combinación prefieren, entonces y son incomparables: ninguno es el otro. La misma operación de comparación se puede definir de la misma manera para dos conjuntos de elementos, no solo médicos y hospitales. La elección de cuál de los dos conjuntos de elementos utilizar en el papel de los médicos es arbitraria. Intercambiar los roles de los médicos y los hospitales invierte el orden de cada par de elementos, pero no cambia de otro modo la estructura del orden parcial. [1]
Entonces, este ordenamiento da a los emparejamientos la estructura de un conjunto parcialmente ordenado. Para ello, debe obedecer las siguientes tres propiedades:
- Para cada coincidencia ,
- Por cada dos emparejamientos diferentes y , no puede ser el caso que ambos y son verdaderas.
- Por cada tres emparejamientos diferentes , , y , Si y , luego .
Para emparejamientos estables, las tres propiedades se derivan directamente de la definición de la operación de comparación.
Elementos superiores e inferiores
Definir la mejor coincidencia de un elemento de una instancia de coincidencia estable para ser el elemento que la mayoría prefiere, entre todos los elementos que pueden combinarse con en una coincidencia estable y defina la peor coincidencia de forma análoga. Entonces no hay dos elementos que puedan tener la misma mejor combinación. Supongamos por el contrario que los médicos y Ambos tienen como su mejor partido, y que prefiere a . Luego, en la coincidencia estable que coincide a (que debe existir por la definición de la mejor coincidencia de ), y sería un par inestable, porque prefiere a y prefiere a cualquier otro socio en cualquier emparejamiento estable. Esta contradicción muestra que asignar a todos los médicos a sus mejores coincidencias da una coincidencia. Es una coincidencia estable, porque cualquier par inestable también sería inestable para una de las coincidencias utilizadas para definir las mejores coincidencias. Además de asignar a todos los médicos a sus mejores coincidencias, asigna todos los hospitales a sus peores coincidencias. En el orden parcial de los emparejamientos, es mayor que todos los demás emparejamientos estables. [1]
Simétricamente, la asignación de todos los médicos a sus peores coincidencias y la asignación de todos los hospitales a sus mejores coincidencias da otra coincidencia estable. En el orden parcial de las coincidencias, es menor que todas las demás coincidencias estables. [1]
El algoritmo Gale-Shapley proporciona un proceso para construir emparejamientos estables, que se puede describir de la siguiente manera: hasta que se alcanza un emparejamiento, el algoritmo elige un hospital arbitrario con un puesto vacante y ese hospital hace una oferta de trabajo al médico que más prefiere entre los que aún no ha hecho ofertas. Si el médico está desempleado o tiene una asignación menos preferida, el médico acepta la oferta (y renuncia a su otra asignación, si existe). El proceso siempre termina, porque cada médico y hospital interactúan solo una vez. Cuando termina, el resultado es una coincidencia estable, la que asigna a cada hospital a su mejor coincidencia y que asigna a todos los médicos a sus peores coincidencias. Un algoritmo que intercambia las funciones de los médicos y los hospitales (en el que los médicos desempleados envían solicitudes de empleo a su siguiente preferencia entre los hospitales, y los hospitales aceptan solicitudes cuando tienen un puesto vacante o prefieren al nuevo solicitante, despidiendo al médico que prefieren. había aceptado previamente) en su lugar, produce el emparejamiento estable que asigna a todos los médicos a sus mejores emparejamientos y a cada hospital a su peor emparejamiento. [1]
Operaciones de celosía
Dadas dos coincidencias estables y para la misma entrada, se pueden formar dos emparejamientos más y de la siguiente manera:
- En , cada médico obtiene su mejor opción entre los dos hospitales con los que se asignan en y (si estos difieren) y cada hospital tiene su peor opción.
- En , cada médico obtiene su peor opción entre los dos hospitales con los que están asignados en y (si estos difieren) y cada hospital obtiene su mejor opción.
(Las mismas operaciones se pueden definir de la misma manera para dos conjuntos de elementos, no solo médicos y hospitales). [1]
Entonces ambos y son emparejamientos. No es posible, por ejemplo, que dos médicos tengan la misma mejor opción y sean emparejados con el mismo hospital en, ya que independientemente de cuál de los dos médicos sea el preferido por el hospital, ese médico y el hospital formarían una pareja inestable en cualquiera de y todavía no están emparejados. Porque los médicos están emparejados en , los hospitales también deben coincidir. El mismo razonamiento se aplica simétricamente a. [1]
Además, ambos y son estables. No puede haber una pareja de un médico y un hospital que se prefieran mutuamente a su pareja, porque la misma pareja necesariamente sería también una pareja inestable para al menos uno de los y . [1]
Propiedades de celosía
Las dos operaciones y forman las operaciones de unión y encuentro de una red distributiva finita . En este contexto, una celosía finita se define como un conjunto finito parcialmente ordenado en el que hay un elemento mínimo único y un elemento máximo único, en el que cada dos elementos tienen un elemento mínimo único mayor o igual a ambos (su unión ) y cada dos elementos tienen un elemento mayor único menor o igual a ambos (su encuentro). [1]
En el caso de las operaciones y definido anteriormente, la unión es mayor o igual a ambos y porque se definió para dar a cada médico su opción preferida, y porque estas preferencias de los médicos son la forma en que se define el orden en las coincidencias. Está por debajo de cualquier otra coincidencia que también esté por encima de ambos y , porque cualquier coincidencia de este tipo tendría que dar a cada médico una coincidencia asignada que sea al menos igual de buena. Por lo tanto, se ajusta a los requisitos para la operación de unión de una celosía. Simétricamente, la operaciónse ajusta a los requisitos para la operación de cumplir. [1]
Debido a que se definen utilizando un mínimo o un máximo de elementos en el orden de preferencia, estas dos operaciones obedecen las mismas leyes distributivas obedecidas por las operaciones de mínimo y máximo en ordenamientos lineales: por cada tres emparejamientos diferentes, , y ,
y
Por lo tanto, la red de emparejamientos estables es una red distributiva . [1]
Representación por rotaciones
El teorema de representación de Birkhoff establece que cualquier retícula distributiva finita puede ser representada por una familia de conjuntos finitos , con intersección y unión como operaciones de encuentro y unión, y con la relación de ser un subconjunto como operación de comparación para el orden parcial asociado. Más específicamente, estos conjuntos pueden tomarse como los conjuntos inferiores de un orden parcial asociado. En la forma general del teorema de Birkhoff, este orden parcial puede tomarse como el orden inducido en un subconjunto de los elementos de la celosía, los elementos irreducibles de unión (elementos que no pueden formarse como combinaciones de otros dos elementos). [4] Para la red de emparejamientos estables, los elementos del orden parcial pueden describirse en cambio en términos de estructuras llamadas rotaciones , descritas por Irving & Leather (1986) . [5]
Suponga que dos emparejamientos estables diferentes y son comparables y no tienen una tercera coincidencia estable entre ellos en el orden parcial. (Es decir, y forman un par de la relación de cobertura del orden parcial de emparejamientos estables) .Entonces, el conjunto de pares de elementos que se emparejan en uno pero no en ambos y (la diferencia simétrica de sus conjuntos de pares emparejados) se llama rotación. Forma un gráfico de ciclo cuyos bordes se alternan entre las dos coincidencias. De manera equivalente, la rotación se puede describir como el conjunto de cambios que deberían realizarse para cambiar el menor de los dos emparejamientos en el mayor (con menor y mayor determinados utilizando el orden parcial). Si dos emparejamientos estables diferentes son por separado el emparejamiento más alto para la misma rotación, entonces también lo es su encuentro. De ello se deduce que para cualquier rotación, el conjunto de emparejamientos estables que puede ser el más alto de un par conectado por la rotación tiene un elemento más bajo único. Este emparejamiento más bajo es unir irreductible, y esto da una correspondencia uno a uno entre rotaciones y emparejamientos estables irreductibles de unión. [5]
Si a las rotaciones se les da el mismo orden parcial que sus correspondientes emparejamientos estables irreductibles de unión, entonces el teorema de representación de Birkhoff da una correspondencia uno a uno entre los conjuntos inferiores de rotaciones y todos los emparejamientos estables. El conjunto de rotaciones asociado con cualquier emparejamiento estable dado se puede obtener cambiando el emparejamiento dado por rotaciones hacia abajo en el orden parcial, eligiendo arbitrariamente qué rotación realizar en cada paso, hasta llegar al elemento inferior, y enumerando las rotaciones utilizadas en esta secuencia. de cambios. El emparejamiento estable asociado con cualquier conjunto inferior de rotaciones se puede obtener aplicando las rotaciones al elemento inferior de la red de emparejamientos estables, eligiendo arbitrariamente qué rotación aplicar cuando se puede aplicar más de uno. [5]
Cada par de elementos de una instancia de coincidencia estable dada pertenece a un máximo de dos rotaciones: una rotación que, cuando se aplica a la menor de dos coincidencias, elimina otras asignaciones a y y en su lugar los asigna entre sí, y una segunda rotación que, cuando se aplica al menor de dos emparejamientos, elimina el par de la coincidencia y busca otras asignaciones para esos dos elementos. Porque hay pares de elementos, hay rotaciones. [5]
Propiedades matematicas
Universalidad
Más allá de ser una red distributiva finita, no existen otras restricciones en la estructura de la red de emparejamientos estables. Esto se debe a que, para cada red distributiva finita, existe una instancia de coincidencia estable cuyo entramado de coincidencias estables es isomorfo a . [6] Más fuertemente, si una red distributiva finita tiene elementos, entonces se puede realizar utilizando una instancia de coincidencia estable con como máximo médicos y hospitales. [7]
Número de elementos de celosía
El enrejado de emparejamientos estables se puede utilizar para estudiar la complejidad computacional de contar el número de emparejamientos estables de una instancia determinada. De la equivalencia entre las celosías de emparejamientos estables y las celosías distributivas finitas arbitrarias, se deduce que este problema tiene una complejidad computacional equivalente a contar el número de elementos en una celosía distributiva finita arbitraria, o contar las antichains en un conjunto arbitrario parcialmente ordenado. Calcular el número de coincidencias estables es # P-completo . [5]
En un caso uniformemente aleatorio del problema del matrimonio estable con doctores y hospitales, el número medio de emparejamientos estables es asintóticamente . [8] En un caso de matrimonio estable elegido para maximizar el número de emparejamientos estables diferentes, este número puede ser al menos, [5] y nosotros también limitados por una función exponencial de n (significativamente más pequeño que el límite factorial ingenuo en el número de coincidencias). [9]
Consecuencias algorítmicas
La familia de rotaciones y su ordenamiento parcial se pueden construir en tiempo polinomial a partir de una instancia determinada de correspondencia estable y proporciona una representación concisa de la familia de todas las correspondencias estables, que en algunos casos puede ser exponencialmente mayor cuando se enumeran explícitamente. Esto permite que se realicen de manera eficiente varios otros cálculos en instancias de coincidencia estables. [10]
Emparejamiento y cierre estable ponderado
Si a cada par de elementos en una instancia de coincidencia estable se le asigna un peso de valor real, es posible encontrar la coincidencia estable de peso mínimo o máximo en el tiempo polinomial . Un método posible para esto es aplicar programación lineal al politopo de orden del orden parcial de rotaciones, o al politopo de coincidencia estable . [11] Es posible un algoritmo combinatorio alternativo, basado en el mismo orden parcial. [12]
A partir de los pesos en pares de elementos, se pueden asignar pesos a cada rotación, donde a una rotación que cambia una coincidencia estable dada a otra superior en el orden parcial de las coincidencias estables se le asigna el cambio de peso que causa: el peso total de la concordancia más alta menos el peso total de la concordancia más baja. Por la correspondencia entre emparejamientos estables y conjuntos inferiores de rotaciones, el peso total de cualquier emparejamiento es entonces igual al peso total de su correspondiente conjunto inferior, más el peso del elemento inferior del enrejado de emparejamientos. El problema de encontrar la correspondencia estable de peso mínimo o máximo se vuelve de esta manera equivalente al problema de encontrar el conjunto inferior de peso mínimo o máximo en un conjunto parcialmente ordenado de tamaño polinomial, el conjunto parcialmente ordenado de rotaciones. [12]
Este problema de conjunto inferior óptimo es equivalente a una instancia del problema de cierre , un problema en gráficos dirigidos ponderados por vértices en los que el objetivo es encontrar un subconjunto de vértices de peso óptimo sin bordes salientes. El conjunto inferior óptimo es un cierre óptimo de un grafo acíclico dirigido que tiene los elementos del orden parcial como sus vértices, con una arista de a cuando sea en el orden parcial. El problema de cierre puede, a su vez, resolverse en tiempo polinomial transformándolo en una instancia del problema de flujo máximo . [12]
Arrepentimiento mínimo
Gusfield (1987) define el arrepentimiento de un participante en un emparejamiento estable como la distancia de su emparejamiento asignado desde la parte superior de su lista de preferencias. Él define el arrepentimiento de un emparejamiento estable como el máximo arrepentimiento de cualquier participante. Luego, uno puede encontrar la coincidencia estable de mínimo arrepentimiento mediante un algoritmo codicioso simple que comienza en el elemento inferior del enrejado de coincidencia y luego aplica repetidamente cualquier rotación que reduzca el arrepentimiento de un participante con el máximo arrepentimiento, hasta que esto causaría que otro participante tener un mayor arrepentimiento. [10]
Coincidencia estable mediana
Los elementos de cualquier retícula distributiva forman un gráfico mediano , una estructura en la que cualesquiera tres elementos, , y (aquí, coincidencias estables) tienen un elemento mediano único que se encuentra en un camino más corto entre dos de ellos. Puede definirse como: [13]
Para el entramado de coincidencias estables, esta mediana se puede tomar en su lugar por elementos, asignando a cada médico la mediana en las preferencias del médico de los tres hospitales que coinciden con ese médico en , , y y de manera similar, asignando a cada hospital la mediana de los tres médicos que le corresponden. De manera más general, cualquier conjunto de un número impar de elementos de cualquier retícula distributiva (o gráfico de mediana) tiene una mediana, un elemento único que minimiza su suma de distancias al conjunto dado. [14] Para la mediana de un número impar de emparejamientos estables, cada participante se empareja con el elemento mediano del multiset de sus emparejamientos de los emparejamientos dados. Para un conjunto uniforme de emparejamientos estables, esto se puede eliminar eligiendo la asignación que empareja a cada médico con el más alto de los dos elementos de la mediana y cada hospital con el más bajo de los dos elementos de la mediana. En particular, esto conduce a una definición de la coincidencia mediana en el conjunto de todas las coincidencias estables. [15] Sin embargo, para algunos casos del problema de emparejamiento estable, encontrar esta mediana de todos los emparejamientos estables es NP-difícil . [dieciséis]
Referencias
- ^ a b c d e f g h i j k l 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 ' Universidad de Montreal, ISBN 0-8405-0342-3, MR 0488980. Véase en particular el problema 6, págs. 87-94.
- ^ Hwang, JS (1982), "El entramado de matrimonios estables y permutaciones", Journal of the Australian Mathematical Society, Serie A , 33 (3): 401–410, doi : 10.1017 / S1446788700018838 , MR 0678518
- ^ Peranson, E .; Randlett, RR (junio de 1995), "The NRMP matching algorítmico", Academic Medicine , 70 (6): 477–84, doi : 10.1097 / 00001888-199506000-00008 , PMID 7786367
- ^ Birkhoff, Garrett (1937), "Rings of sets", Duke Mathematical Journal , 3 (3): 443–454, doi : 10.1215 / S0012-7094-37-00334-X
- ^ a b c d e f Irving, Robert W .; Leather, Paul (1986), "La complejidad de contar los matrimonios estables", SIAM Journal on Computing , 15 (3): 655–667, doi : 10.1137 / 0215048 , MR 0850415
- ^ Blair, Charles (1984), "Cada red distributiva finita es un conjunto de emparejamientos estables", Journal of Combinatorial Theory , Serie A, 37 (3): 353–356, doi : 10.1016 / 0097-3165 (84) 90056-6 , MR 0769224
- ^ Gusfield, Dan ; Irving, Robert; Cuero, Paul; Saks, Michael (1987), "Cada red distributiva finita es un conjunto de emparejamientos estables para una instancia de matrimonio estable pequeña", Journal of Combinatorial Theory , Serie A, 44 (2): 304-309, doi : 10.1016 / 0097-3165 (87) 90037-9 , MR 0879688
- ^ Pittel, Boris (1989), "El número medio de coincidencias estables", SIAM Journal on Discrete Mathematics , 2 (4): 530–549, doi : 10.1137 / 0402048 , MR 1018538
- ^ Karlin, Anna R .; Gharan, Shayan Oveis; Weber, Robbie (2018), "Un límite superior simplemente exponencial en el número máximo de emparejamientos estables", en Diakonikolas, Ilias; Kempe, David; Henzinger, Monika (eds.), Actas del 50º Simposio sobre Teoría de la Computación (STOC 2018) , Association for Computing Machinery, págs. 920–925, arXiv : 1711.01032 , doi : 10.1145 / 3188745.3188848 , MR 3826305
- ^ a b Gusfield, Dan (1987), "Tres algoritmos rápidos para cuatro problemas en el matrimonio estable", SIAM Journal on Computing , 16 (1): 111-128, doi : 10.1137 / 0216010 , MR 0873255
- ^ Vande Vate, John H. (1989), "La programación lineal trae felicidad marital", Operations Research Letters , 8 (3): 147-153, doi : 10.1016 / 0167-6377 (89) 90041-2 , MR 1007271
- ^ a b c 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
- ^ Birkhoff, Garrett ; Kiss, SA (1947), "Una operación ternaria en celosías distributivas" , Boletín de la American Mathematical Society , 53 (1): 749–752, doi : 10.1090 / S0002-9904-1947-08864-9 , MR 0021540
- ^ Bandelt, Hans-Jürgen; Barthélémy, Jean-Pierre (1984), "Medianas en gráficas de medianas", Matemáticas aplicadas discretas , 8 (2): 131–142, doi : 10.1016 / 0166-218X (84) 90096-9 , MR 0743019
- ^ 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
- ^ Cheng, Christine T. (2010), "Comprensión de las correspondencias estables de la mediana generalizada", Algorithmica , 58 (1): 34–51, doi : 10.1007 / s00453-009-9307-2 , MR 2658099