Juego del árbol de expansión de coste mínimo

Un juego de árbol de expansión de costo mínimo ( juego MCST ) es un tipo de juego cooperativo . En un juego MCST, cada jugador es un nodo en un grafo completo . El grafo 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 a s . Para ello, necesitan construir un árbol de expansión . Cada arista del grafo tiene un costo, y los jugadores construyen el árbol de expansión de costo mínimo . Surge entonces la pregunta: ¿cómo asignar el costo de este MCST entre los jugadores?

La solución que ofrece la teoría de juegos cooperativos consiste en considerar el coste de cada coalición potencial, es decir, de cada subconjunto de jugadores. El coste de cada coalición S es el coste mínimo de un árbol de expansión que conecta únicamente los nodos de S con el nodo de suministro s . El valor de S es igual al coste de S. Utilizando estas definiciones, se pueden aplicar diversos conceptos de solución de la teoría de juegos cooperativos. Los juegos MCST fueron introducidos por Bird en 1976. ^{[ 1 ]}

• El núcleo de cada juego de MCST no está vacío. ^{[ 1 ] [ 2 ]}
• El nucléolo es el único punto de 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 ]}

• Una solución en el núcleo se puede leer directamente de cualquier grafo de árbol de expansión 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 general, en los juegos MCST, calcular el nucleolo es NP-difícil; la prueba se realiza mediante reducción a partir del problema de cobertura de conjunto mínimo . ^{[ 5 ]} Existe un algoritmo que calcula el nucleolo en 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 para calcular el nucleolo se puede reducir a O( n log n ) usando montones fusionables eficientes . ^{[ 8 ]} En casos particulares, el nucleolo se puede calcular en tiempo O( n ). ^{[ 4 ]}

Un juego de bosque de expansión 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 del núcleo se pueden calcular en tiempo fuertemente polinomial . ^{[ 9 ]}