Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions

1. Introducción y Definición del Problema

El artículo aborda el problema de la formación de coaliciones en entornos donde los agentes son egoístas y sus preferencias no son conocidas a priori. A diferencia de los modelos tradicionales de juegos hedónicos que asumen coaliciones disjuntas y preferencias completas, este trabajo propone un nuevo marco bajo información parcial con las siguientes características:

• Coaliciones Superpuestas (POCF): Los agentes pueden unirse a múltiples coaliciones simultáneamente (estrategias mixtas o puras).
• Información Offline: No se permite la interacción activa con el entorno (exploración en tiempo real) debido a costos o riesgos. En su lugar, el algoritmo debe inferir las preferencias de los agentes a partir de un conjunto de datos fijo y pre-recopilado que contiene interacciones pasadas y retroalimentación de utilidad.
• Objetivo: Inferir las preferencias ocultas y construir una estructura de coalición que sea Nash Estable (NS) o aproximadamente Nash Estable ($\epsilon$-NS). Una estructura es NS si ningún agente puede mejorar su utilidad unilateralmente desviándose a otra coalición.
• Modelo de Preferencias: Se asumen preferencias aditivamente separables y simétricas (la utilidad que un agente obtiene de otro es la misma que el otro obtiene de él, pero puede variar según la coalición específica).

2. Metodología

El enfoque se basa en el aprendizaje offline y la minimización de un "gap de dualidad" (dual gap) que mide la estabilidad de Nash.

A. Modelos de Retroalimentación

El estudio analiza dos tipos de granularidad de datos disponibles en el conjunto de datos:

1. Retroalimentación Semi-Bandido (Semi-bandit): Se observa la utilidad individual de cada agente por cada interacción con otros miembros de sus coaliciones seleccionadas.
2. Retroalimentación Bandido (Bandit): Solo se observa la utilidad total (agregada) de un agente por su partición de coaliciones, sin desglose por pares.

B. Algoritmo Propuesto: Minimización de Surrogados

Se presenta un marco algorítmico general (Algoritmo 1) que utiliza estimadores de utilidad y "bonos de exploración" (exploration bonuses) para manejar la incertidumbre.

• Estimadores: Se construyen estimadores de la utilidad esperada ($\hat{v}_i$) basados en los datos.
• Bonos de Exploración: Se añaden términos de bonificación ($b^\delta_i$) para crear límites de confianza superiores (UCB) e inferiores (LCB), asegurando que el algoritmo sea conservador ante la falta de datos.
• Objetivo: Encontrar una estrategia conjunta $\phi$ que minimice el gap de dualidad estimado:
  $$\min_{\phi} \max_{i} [V^{\star, \delta}_i(\phi_{-i}) - V^\delta_i(\phi)]$$
  Donde $V^{\star, \delta}$ es la mejor respuesta optimista y $V^\delta$ es la utilidad pesimista actual.

C. Suposiciones de Cobertura del Dataset

La viabilidad del aprendizaje depende de qué tan bien el dataset cubre las posibles desviaciones unilaterales:

• Para Semi-Bandido (Suposición 1 - Cobertura de Tamaño de Coalición): El dataset debe contener al menos una instancia de cada tamaño de coalición que podría resultar de una desviación unilateral desde una estrategia Nash estable.
• Para Bandido (Suposición 2 - Cobertura de Acción): Dado que la información es más escasa, se requiere una suposición más estricta: el dataset debe ser al menos tan informativo como un dataset generado por una cantidad suficiente de muestras de cualquier desviación unilateral posible. Esto se formaliza mediante una condición de matriz de covarianza (usando regresión ridge).

3. Contribuciones Clave

1. Nuevo Marco Teórico: Introduce el primer modelo de aprendizaje offline para formación de coaliciones con superposición y preferencias desconocidas.
2. Condiciones Necesarias y Suficientes:
   • Identifica que la Suposición 1 es necesaria y suficiente para el aprendizaje eficiente bajo retroalimentación semi-bandido.
   • Demuestra que la Suposición 1 es insuficiente bajo retroalimentación bandido, requiriendo la Suposición 2 (más estricta) para garantizar el aprendizaje.
3. Algoritmos de Complejidad Muestral Óptima:
   • Desarrolla algoritmos que logran un estado $\epsilon$-NS con una complejidad muestral que depende óptimamente de $\epsilon$ (hasta factores logarítmicos).
   • La complejidad escala polinomialmente con el número de agentes ($n$) y coaliciones candidatas ($k$), eliminando la dependencia exponencial típica en juegos de suma cero o general.
4. Extensiones a Estrategias Puras: Aunque el análisis se centra en estrategias mixtas, se demuestra cómo adaptar el algoritmo para encontrar estrategias puras Nash estables en juegos simétricos.

4. Resultados Principales

Teóricos

• Teorema 3 (Semi-Bandido): Bajo la Suposición 1, el algoritmo logra un gap de dualidad acotado por $O(1/\sqrt{M})$, donde $M$ es el tamaño del dataset. La complejidad muestral para alcanzar $\epsilon$-NS es $O(1/\epsilon^2)$.
• Teorema 5 (Bandido): Bajo la Suposición 2, el algoritmo también logra una convergencia $O(1/\sqrt{M})$, pero con constantes que dependen de la dimensión del espacio de parámetros ($n^2k$).
• Imposibilidad: Se prueba que sin cumplir las suposiciones de cobertura, ningún algoritmo puede distinguir entre juegos con diferentes estructuras Nash estables, resultando en un gap de dualidad alto independientemente del tamaño del dataset.

Experimentales

• Se realizaron experimentos extensos en conjuntos de datos sintéticos.
• Validación de Suposiciones: Los resultados muestran que el algoritmo converge a un nivel bajo de aproximación a la estabilidad Nash cuando el dataset cumple con las suposiciones (política de exploración aleatoria uniforme).
• Fallo sin Cobertura: Cuando el dataset viola las suposiciones (política de exploración sesgada), el algoritmo falla en encontrar una solución estable, confirmando la necesidad teórica de las condiciones de cobertura.
• Escalabilidad: El rendimiento escala consistentemente con el tamaño del dataset ($M$), el número de agentes ($n$) y coaliciones ($k$), alineándose con las cotas teóricas.

5. Significado e Impacto

Este trabajo es significativo por varias razones:

• Realismo: Aborda la realidad de que en muchos escenarios (como asignación de consultores, gestión de proyectos o redes sociales), no se puede "probar" nuevas coaliciones activamente debido a costos, y las preferencias son dinámicas o desconocidas.
• Superposición: Generaliza los juegos hedónicos clásicos permitiendo superposición, lo cual es crucial para modelar interacciones modernas donde los individuos participan en múltiples grupos simultáneamente.
• Eficiencia de Muestras: Proporciona garantías teóricas de que se pueden encontrar soluciones estables con un número relativamente pequeño de datos históricos, lo cual es vital para aplicaciones donde la recolección de datos es costosa.
• Conexión con RL Offline: Conecta la teoría de juegos cooperativos con el aprendizaje por refuerzo offline (Offline RL), adaptando conceptos de cobertura de datos y bonos de exploración a un contexto de formación de coaliciones.

En resumen, el artículo establece las bases teóricas y prácticas para diseñar sistemas de asignación de recursos y formación de equipos que sean estables y eficientes, basándose únicamente en datos históricos limitados y ruidosos.