Sequential Elimination and Union Shapley Value for Group Assessment in Coalitional Games

Resumen Técnico: Eliminación Secuencial y Valor de Shapley de Unión para la Evaluación de Grupos en Juegos Cooperativos

Planteamiento del Problema
En la teoría de juegos cooperativa y campos relacionados como la centralidad en redes y la valoración de datos en aprendizaje automático, un desafío fundamental es extender las evaluaciones de jugadores individuales a grupos. Los métodos existentes suelen depender de dos enfoques directos:

1. Suma: Agregar valores individuales (por ejemplo, la suma de los valores de Shapley). Esto ignora la estructura subyacente de la cooperación y las dependencias entre jugadores.
2. Fusión: Tratar al grupo como un único elemento fusionado y evaluarlo (por ejemplo, el valor de Shapley de Fusión). Esto altera la estructura del juego y no logra distinguir entre jugadores independientes y jugadores altamente dependientes.

Ambos enfoques a menudo fallan en capturar con precisión las dependencias dentro de los grupos. Por ejemplo, en un juego donde dos pares disjuntos de jugadores generan valor de forma independiente, sumar valores individuales o fusionar grupos puede asignar incorrectamente la misma importancia a un par de jugadores cooperantes y a un par de jugadores independientes, fallando en reflejar la asimetría en su impacto sistémico.

Metodología
Los autores proponen y analizan un tercer enfoque basado en la eliminación secuencial. En este marco, los elementos de un grupo se eliminan uno por uno, y sus evaluaciones en los juegos reducidos resultantes se agregan. La hipótesis central es que este método mide naturalmente la contribución neta de un grupo al descontar efectos superpuestos y centrarse en el daño causado por la ausencia del grupo.

El estudio se fundamenta en un análisis axiomático exhaustivo de los valores de grupo en juegos cooperativos. La metodología implica:

• Definición de Clases Axiomáticas: Los autores introducen una clase de semivalores de grupo (débilmente consistentes). Estos son valores de grupo que satisfacen Linealidad, Simetría, Monotonía Débil, Jugador Nulo Fuera y el axioma de Jugador Dummy. También definen una clase correspondiente de semivalores de sinergia, que reemplazan el axioma de Jugador Dummy con el axioma de Jugador Dummificador (introducido por Grabisch y Roubens).
• Extensión Secuencial: El artículo establece que un valor de jugador admite una extensión secuencial si y solo si satisface la propiedad de Contribuciones Equilibradas. Se demuestra que todo semivalue consistente (que satisface Jugador Nulo Fuera) admite una extensión secuencial única.
• Función Potencial: Los autores utilizan la función potencial introducida por Hart y Mas-Colell para caracterizar la extensión secuencial del valor de Shapley.

Contribuciones y Resultados Clave

1. El Valor de Shapley de Unión:
   Los autores introducen el Valor de Shapley de Unión como la extensión secuencial única del valor de Shapley. Se define como la diferencia entre el potencial del juego original y el potencial del juego después de que el grupo es eliminado:
   $$US_S(N, v) = P(N, v) - P(N \setminus S, v) = \sum_{T \subseteq N, S \cap T \neq \emptyset} \frac{\Delta v(T)}{|T|}$$
   donde $\Delta v(T)$ son los dividendos de Harsanyi.

   • Interpretación: Este valor mide el "daño" infligido al juego cuando un grupo se retira. Agrega contribuciones de tal manera que el dividendo de cada coalición se cuenta como máximo una vez, incluso si el grupo contiene múltiples miembros de dicha coalición.
   • Axiomatización: El valor de Shapley de Unión se caracteriza únicamente por los axiomas de Potencial (o Contribuciones Equilibradas) combinados con Eficiencia. También se caracteriza únicamente entre los semivalores de grupo mediante la Igualdad de Grupos (todos los grupos en un juego de unanimidad son igualmente importantes).

2. Clasificación Axiomática de los Valores de Grupo:
   El artículo distingue entre dos variantes de evaluación de grupos:

   • Valor Total: Valores que evalúan el valor total de un grupo (por ejemplo, Extensión de Suma, Shapley de Fusión, Shapley de Unión). Estos se capturan mediante semivalores de grupo.
   • Sinergia: Valores que miden la sinergia de un grupo (por ejemplo, Índice de Interacción). Estos se capturan mediante semivalores de sinergia.
     Los autores proporcionan una correspondencia funcional entre estas dos clases. Específicamente, muestran que el Valor de Shapley de Fusión corresponde al Índice de Interacción (una contraparte sinérgica), y el Valor de Shapley de Unión corresponde a un nuevo valor sinérgico llamado Valor de Shapley de Intersección.

3. El Valor de Shapley de Intersección:
   Definido como la suma de los dividendos de las coaliciones que contienen al grupo completo:
   $$IS_S(N, v) = \sum_{S \subseteq T \subseteq N} \frac{\Delta v(T)}{|T|}$$
   Este valor mide la intersección de contribuciones. Para un grupo de tamaño dos, la suma del Valor de Shapley de Unión y el Valor de Shapley de Intersección es igual a la suma de los valores de Shapley individuales:
   $$US_{\{i,j\}}(N, v) + IS_{\{i,j\}}(N, v) = SV_i(N, v) + SV_j(N, v)$$
   Esta descomposición permite separar el valor conjunto de un grupo en una parte de "unión" (contando contribuciones una sola vez) y una parte de "intersección" (sinergia).

4. Comparación con Trabajos Existentes:
   El análisis aclara la relación entre los valores propuestos y la literatura existente:

   • Se demuestra que el Valor de Shapley de Fusión (Marichal et al.) es el único semivalue de grupo que satisface el axioma de Coalición Dummy.
   • El Índice de Interacción (Grabisch y Roubens) se identifica como un semivalue de sinergia, distinto de los semivalores de grupo porque viola el axioma estándar de Jugador Dummy en favor del axioma de Jugador Dummificador.
   • El artículo demuestra que el enfoque de extensión secuencial es teóricamente robusto, ya que se aplica a todos los semivalores consistentes y produce valores con fuertes propiedades axiomáticas.

Significado
El artículo afirma que el enfoque de extensión secuencial, y específicamente el Valor de Shapley de Unión, constituye una de las extensiones más naturales y fundamentadas teóricamente de los valores de jugador a grupos en juegos cooperativos. Al distinguir entre evaluar el valor total y medir la sinergia, los autores proporcionan un marco unificado que aclara las diferencias entre las nociones existentes en la literatura. La introducción de los Valores de Shapley de Unión e Intersección ofrece nuevas herramientas para analizar interacciones, particularmente en escenarios donde la superposición de contribuciones debe descontarse (Unión) o donde la sinergia pura debe aislarse (Intersección). El trabajo establece que estos valores no son heurísticas arbitrarias, sino que están determinados únicamente por axiomas fundamentales como Contribuciones Equilibradas, Potencial e Igualdad de Grupos.