Juego de árbol de expansión de costo mínimo

Un juego de árbol de expansión de costo mínimo ( juego MCST ) es una especie de juego cooperativo . En un juego MCST, cada jugador es un nodo en un gráfico completo . El gráfico contiene un nodo adicional, el nodo de suministro , denotado por s . El objetivo de los jugadores es que todos estén conectados por un camino hacia s . Para ello, necesitan construir un árbol de expansión . Cada borde del gráfico tiene un coste y los jugadores construyen el árbol de expansión de coste mínimo . Surge entonces la pregunta: ¿cómo repartir el coste de este MCST entre los actores?

La solución que ofrece la teoría de juegos cooperativos es considerar el coste de cada coalición potencial: cada subconjunto de jugadores. El costo de cada coalición S es el costo mínimo de un árbol de expansión que conecta solo los nodos en S con los nodos de suministro s . El valor de S es menos el costo de S. Utilizando estas definiciones, se pueden aplicar varios conceptos de solución de la teoría de juegos cooperativos. Bird introdujo los juegos MCST en 1976. ^[1]

Propiedades

• El núcleo de cada juego MCST no está vacío. ^{[1] [2]}
• El nucléolo es el único punto en la intersección del núcleo y el núcleo . ^[3]
• Si la red subyacente es un árbol, entonces el nucléolo coincide con el núcleo. ^[4]

Cálculo

• Una solución en el núcleo se puede leer directamente desde cualquier gráfico de árbol de costo mínimo asociado con el problema. ^[2]
• Existe un algoritmo que requiere O(n ² ) operaciones elementales para calcular cada punto adicional en el núcleo. ^[3]
• En los juegos MCST generales, calcular el nucleolo es NP-difícil; la prueba es por reducción del problema de cobertura del conjunto mínimo . ^[5] Existe un algoritmo que calcula el nucleolo en el tiempo O( n ³ | B |), donde B es el conjunto de coaliciones relevantes (en general, |B|=2 ⁿ , pero en algunos casos especiales, solo un subconjunto de las coaliciones son relevantes). ^[6]
• Si la red subyacente es un árbol , entonces el nucleolo se puede calcular en tiempo O( n ³ ) y el valor de Shapley se puede calcular en tiempo O( n ). ^[7] El tiempo de ejecución del cálculo del nucleolo se puede reducir a O ( n log n ) utilizando montones fusionables de manera eficiente . ^[8] En casos particulares, el nucleolo se puede calcular en tiempo O( n ). ^[4]

Juegos que abarcan el bosque

Un juego de bosque de costo mínimo (juego MCSF) es una generalización de un juego MCST, en el que se permiten múltiples nodos de suministro. En general, el núcleo de un juego MCSF puede estar vacío. ^[1] Sin embargo, si la red subyacente es un árbol, el núcleo siempre no está vacío y los puntos centrales se pueden calcular en un tiempo fuertemente polinomial . ^[9]

Referencias

1. pájaro, CG (1976). "Sobre la asignación de costos para un árbol generador: un enfoque de teoría de juegos" . Redes . 6 (4): 335–350. doi :10.1002/net.3230060404.
2. , Daniel; Huberman, Gur (1 de diciembre de 1981). "Juegos de árbol de expansión de costo mínimo" . Programación Matemática . 21 (1): 1–18. doi :10.1007/BF01584227. ISSN  1436-4646. S2CID  26198019.
3. , Daniel; Huberman, Gur (1 de julio de 1984). "Sobre el núcleo y el nucleolo de los juegos de árboles de costo mínimo". Programación Matemática . 29 (3): 323–347. doi :10.1007/BF02592000. ISSN  1436-4646. S2CID  12124235.
4. Granot, D.; Maschler, M.; Owen, G.; Zhu, WR (1 de junio de 1996). "El núcleo/nucleolo de un juego de árbol estándar". Revista Internacional de Teoría de Juegos . 25 (2): 219–244. doi :10.1007/BF01247104. ISSN  1432-1270. S2CID  120669939.
5. Faigle, Ulrich; Kern, Walter; Kuipers, Jeroen (1 de diciembre de 1998). "Calcular el nucleolo de los juegos de árboles de expansión de costo mínimo es NP-difícil". Revista Internacional de Teoría de Juegos . 27 (3): 443–450. doi :10.1007/s001820050083. ISSN  0020-7276. S2CID  46730554.
6. Kuipers, Jeroen; Solymosi, Tamás; Aarts, Harry (1 de septiembre de 2000). "Calcular el nucleolo de algunos juegos de estructura combinatoria". Programación Matemática . 88 (3): 541–563. doi :10.1007/PL00011385. ISSN  1436-4646. S2CID  13149058.
7. Meguido, Nimrod (agosto de 1978). "Complejidad computacional del enfoque de la teoría de juegos para la asignación de costos de un árbol". Matemáticas de la Investigación de Operaciones . 3 (3): 189–196. doi :10.1287/moor.3.3.189. ISSN  0364-765X.
8. Galil, Zvi (1 de enero de 1980). "Aplicaciones de montones fusionables eficientes para problemas de optimización en árboles". Acta Informática . 13 (1): 53–58. doi :10.1007/BF00288535. ISSN  0001-5903. S2CID  39221796.
9. Granot, Daniel; Granot, Frieda (1992). "Complejidad computacional de un enfoque de asignación de costos para un problema forestal que abarca costos fijos". Matemáticas de la Investigación de Operaciones . 17 (4): 765–780. doi :10.1287/moor.17.4.765. ISSN  0364-765X. JSTOR  3690069.