Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach

Resumen Técnico: Formación de Coaliciones Estable y Presupuestariamente Viable para el Aprendizaje Federado Agrupado

Planteamiento del Proble Problema
Los sistemas de aprendizaje federado (FL, por sus siglas en inglés) a menudo sufren de heterogeneidad estadística, donde una única "gran coalición" de todos los participantes produce modelos subóptimos. Si bien el aprendizaje federado agrupado aborda el aspecto estadístico mediante la agrupación de participantes compatibles, el aspecto económico permanece poco explorado. Específicamente, existe una falta de marcos que aseguren simultáneamente:

1. Estabilidad: Los participantes no tienen incentivos para abandonar unilateralmente su coalición asignada para unirse a otra (estabilidad de Nash) o para ser rechazados por una coalición de destino (estabilidad individual).
2. Viabilidad Presupuestaria: La entidad coordinadora puede financiar las transferencias necesarias para compensar a los participantes sin incurrir en un déficit.
3. Eficiencia: La partición estable resultante se aproxima al óptimo de bienestar social global.

Los enfoques existentes suelen tratar la estabilidad y las restricciones presupuestarias por separado o asumen la superaditividad del excedente, lo cual no se cumple en entornos de FL heterogéneos y no convexos.

Metodología
El artículo modela el problema como un juego hedónico de formación de coaliciones con excedente transferible.

• Modelo del Sistema: Los participantes $N$ se dividen en coaliciones. Cada coalición $S$ entrena un modelo específico de la coalición $\theta_S$ utilizando objetivos locales ponderados. El modelo gestiona los fallos de comunicación (actualizaciones perdidas) mediante una regla de agregación segura que deja el modelo sin cambios si no llegan actualizaciones.
• Modelo Económico:
  • Excedente: El excedente transferible total $W(S)$ se define como el beneficio de aprendizaje esperado $B(S)$ menos los costes del coordinador $C_0(S)$ y los costes de los participantes $d_i(S)$.
  • Transferencias: Un coordinador paga transferencias $t_i(S)$ a los participantes. La utilidad del participante es $U_i(S) = t_i(S) - d_i(S)$.
  • Viabilidad Presupuestaria: La regla de asignación es débilmente viable presupuestariamente si el coordinador retiene un excedente no negativo ($R_0(S) \ge 0$) en cada coalición formada.
• Preferencias Hedónicas: Las preferencias son inducidas por una regla de asignación que convierte el excedente en utilidades. El artículo se centra en las asignaciones de excedente por pares simétricas, donde la utilidad de un participante en una coalición es la suma de los valores por pares $v_{ij}$ con todos los demás miembros $j \in S$.
• Análisis de Teoría de Juegos:
  • Los autores demuestran que las asignaciones por pares simétricas inducen un juego de potencial exacto. La función de potencial es la suma de los valores por pares dentro de las coaliciones.
  • Esta estructura garantiza la existencia de una partición estable de Nash y asegura que cualquier secuencia de movimientos de mejor respuesta estricta termine en pasos finitos.
  • La Estabilidad Individual (donde los miembros del destino deben consentir la entrada de un entrante) también se analiza, mostrando que si los valores por pares son no negativos, la estabilidad de Nash implica la estabilidad individual.
• Bienestar y Eficiencia:
  • El bienestar social se descompone en la utilidad del participante (vinculada a la función de potencial) y el excedio retenido por el coordinador.
  • El artículo establece que el equilibrio presupuestario exacto (cero excedente retenido) produce una partición de Nash óptima en términos de bienestar solo si el excedente es exactamente representable por pares.
  • Sin representabilidad exacta, la pérdida de bienestar puede ser ilimitada bajo la viabilidad presupuestaria. Sin embargo, si el excedente retenido es acotado en relación con el óptimo, se deriva una garantía de eficiencia multiplicativa (Precio de la Estabilidad).
  • Se demuestra que la maximización del potencial global es equivalente al agrupamiento de correlación de máximo acuerdo ponderado. El artículo propone un flujo de trabajo: aproximar el agrupamiento y luego aplicar la estabilización de mejor respuesta estricta para alcanzar una partición estable preservando las garantías de aproximación.
• Verificación: El artículo proporciona una verificación de oráculo de tiempo polinomial para la viabilidad presupuestaria cuando la función de excedente retenido es submodular.

Contribuciones Clave

1. Modelado: Introduce un modelo de FL específico de la coalición que gestiona rondas de comunicación no exitosas sin una agregación indefinida y no asume superaditividad.
2. Separación Económica: Separa explícitamente los beneficios de aprendizaje, los costes, las transferencias y el excedente retenido del coordinador, derivando condiciones para la viabilidad presupuestaria y la racionalidad individual.
3. Garantías de Estabilidad: Demuestra que las asignaciones por pares simétricas crean un juego de potencial exacto, garantizando la existencia de particiones estables de Nash e individualmente estables con convergencia finita.
4. Límites de Eficiencia: Caracteriza la relación entre el excedente retenido por el coordinador y la eficiencia del bienestar. Demuestra que el equilibrio exacto produce la estabilidad óptima solo en una clase específica de excedentes, mientras que un excedente relativo acotado proporciona un límite de eficiencia multiplicativa ajustado.
5. Complejidad Computacional: Vincula la maximización del potencial global con el agrupamiento de correlación (NP-duro) y deriva garantías de bienestar de extremo a extremo para los flujos de trabajo de aproximación más estabilización.
6. Verificación: Muestra que una cantidad exponencial de restricciones presupuestarias pueden verificarse en tiempo de oráculo polinomial si el excedente retenido es submodular.
7. Validación Empírica: Realiza un estudio preregistrado sobre datos de CIFAR-10 con $n=4$ participantes.

Resultados Experimentales
El estudio evalúa el mecanismo en cinco semillas de datos de CIFAR-10 con distribuciones heterogéneas:

• Optimalidad del Bienestar: En una calibración "benigna", el mecanismo descentralizado alcanzó el óptimo de bienestar de la tabla estimada certificada para las cinco semillas. El Precio de la Estabilidad empírico fue exactamente 1.
• Estabilidad frente a Baselines: En contraste, un baseline de "reparto de excedente igualitario" no logró producir un resultado estable de Nash en tres de las cinco semillas (el conjunto estable de Nash estaba vacío y la dinámica cicló de forma indefinida).
• Convergencia: El proceso de mejor respuesta descentralizado convergió rápidamente (media de 1.53 movimientos) desde diversas inicializaciones.
• Sensibilidad: En una calibración "ajustada" (sensible al coste), los costes de estabilidad aumentaron (Precio de la Estabilidad hasta 1.29), y la partición óptima se volvió sensible a los errores de estimación, resaltando el compromiso entre la rigidez presupuestaria y la estabilidad.
• Estimación: Los estimadores de ganancia de validación por pares (PVG) proporcionaron signos de pares significativamente más fiables que la alineación de gradientes, la cual era propensa a falsos positivos.

Significancia y Reivindicaciones
El artículo afirma conectar el valor de aprendizaje, las transferencias monetarias, la estabilidad y la eficiencia económica sin confundir el equilibrio local, la optimalidad global y la tratabilidad computacional.

• Teórica: Corrige las limitaciones de trabajos preliminares al interpretar correctamente el equilibrio de Nash como un óptimo de potencial local y al no asumir superaditividad. Establece que la estabilidad y la eficiencia son conceptos distintos vinculados por el excedente retenido del coordinador.
• Práctica: El mecanismo propuesto ofrece una forma demostrablemente estable y presupuestariamente viable de organizar participantes de FL heterogéneos. Los resultados empíricos demuestran que, mientras que las reglas simples de división de excedentes pueden fallar en la estabilización, el enfoque de potencial por pares propuesto garantiza la convergencia hacia un estado estable que puede coincidir con el óptimo de bienestar.
• Limitaciones: Los autores señalan que el modelo actual asume que el coordinador conoce o estima los costes y beneficios (asignación de incentivos en lugar de diseño de mecanismos veraces). La validación empírica está limitada a $n=4$ participantes para permitir la enumeración exacta y la certificación, y los resultados son específicos de las tablas de valores estimadas del experimento.

El trabajo concluye que, si bien el equilibrio presupuestario exacto no garantiza la optimalidad del bienestar en general, el marco propuesto proporciona una base teórica robusta y un mecanismo práctico para la formación de coaliciones estable y presupuestariamente viable en el aprendizaje federado agrupado.