Estabilidad de Desviación Única en Juegos Hedónicos Aditivamente Separables con Tamaños de Coalición Restringidos

Información Básica

• ID del Artículo: 2510.12641
• Título: Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
• Autores: Martin Bullinger (University of Bristol), Adam Dunajski (University of Edinburgh), Edith Elkind (Northwestern University), Matan Gilboa (University of Oxford)
• Clasificación: cs.GT (Teoría de Juegos), cs.DS (Estructuras de Datos y Algoritmos)
• Fecha de Publicación: 14 de octubre de 2025 (preimpresión en arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.12641

Resumen

Este artículo estudia problemas de estabilidad en juegos hedónicos aditivamente separables (ASHG, por sus siglas en inglés) bajo restricciones de límites fijos en los tamaños de coalición. Los autores consideran cuatro conceptos clásicos de estabilidad basados en desviaciones de agentes únicos: estabilidad de Nash, estabilidad individual, estabilidad contractual de Nash y estabilidad contractual individual. Para cada concepto de estabilidad, los autores examinan dos variantes: una que requiere que las coaliciones dejadas por los desviadores mantengan tamaños válidos, y otra sin esta restricción. El artículo proporciona un panorama completo sobre la existencia de resultados estables bajo parámetros de tamaño dados, y caracteriza completamente la complejidad computacional de los problemas de existencia relevantes cuando solo hay restricciones de límite superior.

Antecedentes de Investigación y Motivación

Importancia del Problema

La formación de coaliciones es un problema central en sistemas multiagente, con aplicaciones generalizadas en:

• Divisiones de grupos en proyectos de estudiantes
• Asignación de asientos en oficinas departamentales
• Organización de grupos en actividades al aire libre
• Asignación de asientos en cenas de conferencias

Estos escenarios prácticos comparten características comunes: los tamaños de coalición deben satisfacer restricciones de límites superior e inferior, y los esquemas de partición deben mantener estabilidad frente a comportamientos desviacionistas de los agentes.

Limitaciones de la Investigación Existente

1. Falta de consideración de límites inferiores: Trabajos previos se enfocaban principalmente en restricciones de límite superior, con investigación insuficiente sobre límites inferiores
2. Conceptos de estabilidad incompletos: Falta de análisis sistemático de diferentes conceptos de estabilidad bajo condiciones de restricción
3. Complejidad computacional no aclarada: La complejidad computacional de varios conceptos de estabilidad bajo restricciones aún no ha sido completamente caracterizada

Motivación de la Investigación

Este artículo tiene como objetivo llenar estos vacíos de investigación, proporcionando un marco teórico completo para la estabilidad en juegos hedónicos bajo restricciones de tamaño de coalición.

Contribuciones Principales

1. Caracterización completa de existencia: Proporciona un panorama completo de existencia para todos los conceptos de estabilidad considerados bajo parámetros de tamaño dados
2. Análisis completo de complejidad computacional: Caracteriza completamente la complejidad computacional de todos los conceptos de estabilidad cuando solo hay restricciones de límite superior (λ=1)
3. Algoritmos de tiempo polinomial:
   • Proporciona un algoritmo de tiempo polinomial para estabilidad contractual individual (CIS)
   • Proporciona un algoritmo de tiempo polinomial para estabilidad contractual de Nash (CNS) cuando el límite superior es 2
   • Proporciona un algoritmo de tiempo polinomial para CIS* cuando el límite inferior es al menos 2
4. Resultados de NP-completitud: Demuestra la NP-completitud de problemas de determinación de estabilidad en múltiples casos
5. Corrección de algoritmos: Corrige errores en el algoritmo de Aziz et al. (2013)

Explicación Detallada de Métodos

Definición de la Tarea

Entrada:

• Conjunto de agentes N
• Funciones de utilidad aditivamente separables v = (va)a∈N, donde va: N{a} → ℝ
• Restricciones de tamaño de coalición λ ≤ μ (λ es el límite inferior, μ es el límite superior)

Salida:

• (λ,μ)-partición: una partición de coalición que satisface restricciones de tamaño
• Determinación de estabilidad: si la partición satisface un concepto de estabilidad específico

Restricciones:

• Cada coalición C satisface λ ≤ |C| ≤ μ
• Las desviaciones deben ser (λ,μ)-permisibles o (λ,μ)-factibles

Marco de Conceptos de Estabilidad

Definiciones Fundamentales

Para la utilidad del agente a en la coalición C: $u_a(C) = \sum_{b \in C\setminus\{a\}} v_a(b)$

Cuatro Conceptos de Estabilidad Estándar

1. Estabilidad de Nash (NS): Ningún agente puede mejorar su utilidad desviándose
2. Estabilidad Individual (IS): Desviación de Nash + consentimiento de miembros de la coalición objetivo
3. Estabilidad Contractual de Nash (CNS): Desviación de Nash + consentimiento de miembros de la coalición original
4. Estabilidad Contractual Individual (CIS): Satisface simultáneamente condiciones de IS y CNS

Variantes de Factibilidad

Cada concepto estándar tiene una variante de factibilidad correspondiente (marcada con *), que requiere que la coalición original siga satisfaciendo restricciones de tamaño después de la desviación.

Algoritmos Clave

Algoritmo 1: Algoritmo CIS (Versión Corregida)

Entrada: ASHG (N,v), parámetro μ
Salida: (1,μ)-partición

1. Inicializar: i←0, A←N
2. mientras A ≠ ∅:
3.   Seleccionar agente a ∈ A
4.   Calcular utilidad de crear nueva coalición h
5.   para k ∈ [i]:  // Considerar unirse a coalición existente
6.     Calcular utilidad de unirse a coalición k, h'
7.     si h < h': Actualizar selección óptima
8.   Crear/unirse a coalición según selección óptima
9.   Actualizar conjunto de agentes disponibles A

Algoritmo 3: Algoritmo CIS* (Valuaciones No Nulas)

Para el caso de límite inferior λ≥2, mediante enfoque de dos fases:

1. Fase I: Formar coaliciones de tamaño mínimo óptimas para cada líder
2. Fase II: Llenar agentes restantes en orden inverso

Configuración Experimental

Marco de Análisis Teórico

Este artículo realiza principalmente análisis teórico, incluyendo:

1. Pruebas de existencia: Pruebas constructivas y contraejemplos
2. Análisis de complejidad: Pruebas de reducción y diseño de algoritmos
3. Corrección de algoritmos: Verificación formal

Métodos de Análisis de Complejidad

• Pruebas de NP-completitud: Reducciones desde problemas clásicos como 3-SAT y X3C
• Algoritmos polinomiales: Diseño constructivo de algoritmos
• Análisis de límites inferiores: Prueba de no existencia mediante contraejemplos

Resultados Experimentales

Resultados de Existencia

Hallazgos Clave:

• Las valuaciones simétricas garantizan la existencia del concepto de estabilidad factible más fuerte (NS*)
• Incluso para valuaciones simétricas simples, los conceptos de estabilidad estándar pueden no existir
• CIS* existe en cualquier caso (cuando existe una partición factible)

Resultados de Complejidad Computacional (λ=1)

Complejidad Específica de Algoritmos:

• CIS: Algoritmo polinomial con complejidad de tiempo O(n³)
• CNS (μ=2): Algoritmo polinomial con complejidad de tiempo O(n²)
• NS/IS: NP-completitud probada mediante reducción desde problema de emparejamiento minimax

Resultados para Límite Inferior λ≥2

Trabajo Relacionado

Fundamentos de Juegos Hedónicos

• Drèze & Greenberg (1980): Introducción del concepto de juegos hedónicos
• Bogomolnaia & Jackson (2002): Establecimiento de juegos hedónicos aditivamente separables

Desarrollo de Conceptos de Estabilidad

• Sung & Dimitrov (2010): Complejidad de estabilidad de desviación única
• Aziz et al. (2013): Algoritmo polinomial para CIS (este artículo identifica y corrige sus errores)

Investigación de Coaliciones Restringidas

• Levinger et al. (2024): Estabilidad grupal bajo restricciones de límite superior
• Fioravantes et al. (2025): Análisis de complejidad parametrizada

Conclusiones y Discusión

Conclusiones Principales

1. Dicotomía de existencia: Existe una diferencia fundamental entre conceptos de estabilidad factible y estándar en términos de existencia
2. Jerarquía de complejidad: Desde la resolubilidad polinomial de CIS hasta la NP-completitud de NS, presenta una jerarquía clara de complejidad
3. Impacto de restricciones: Las restricciones de límite inferior afectan significativamente la existencia y computabilidad de la estabilidad

Limitaciones

1. Problemas abiertos: La complejidad de NS cuando λ=2, μ=3 aún no está determinada
2. Aplicación práctica: Se requiere investigación adicional para conectar resultados teóricos con escenarios de aplicación práctica
3. Eficiencia de algoritmos: Algunos algoritmos polinomiales pueden tener factores constantes grandes

Direcciones Futuras

1. Otros tipos de juegos: Extensión a juegos hedónicos fraccionarios y otros modelos
2. Algoritmos de aproximación: Diseño de algoritmos de aproximación para casos NP-difíciles
3. Algoritmos en línea: Consideración de formación de coaliciones en entornos dinámicos

Evaluación Profunda

Fortalezas

1. Completitud teórica: Proporciona un marco teórico sistemático para la estabilidad en juegos hedónicos de coalición restringida
2. Innovación técnica:
   • Construcciones de reducción ingeniosas (como la reducción de X3C a CNS)
   • Diseño de algoritmos innovadores (algoritmo CIS* de dos fases)
   • Corrección de errores (corrección del algoritmo de Aziz et al.)
3. Profundidad de resultados: No solo proporciona existencia, sino también algoritmos constructivos
4. Claridad de escritura: Definiciones de conceptos claras, estructura de pruebas completa

Debilidades

1. Falta de validación experimental: Trabajo puramente teórico, sin verificación en datos reales
2. Orientación de aplicación limitada: La orientación para escenarios de aplicación práctica requiere investigación adicional
3. Algunas pruebas extensas: Ciertas pruebas de NP-completitud son complejas, con legibilidad mejorable

Impacto

1. Valor académico: Proporciona una base teórica importante para la teoría de juegos de coalición restringida
2. Valor práctico: Proporciona herramientas algorítmicas para problemas reales de formación de coaliciones
3. Reproducibilidad: Las descripciones de algoritmos son claras, fáciles de implementar y verificar

Escenarios Aplicables

1. Campo educativo: Agrupación de estudiantes, programación de cursos
2. Gestión organizacional: Formación de equipos, asignación de recursos
3. Elección social: Coaliciones de votación, formación de grupos de interés
4. Informática: Agrupamiento de nodos en sistemas distribuidos

Referencias

1. Bogomolnaia, A., & Jackson, M. O. (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38(2), 201-230.
2. Aziz, H., Brandt, F., & Seedig, H. G. (2013). Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195, 316-334.
3. Sung, S. C., & Dimitrov, D. (2010). Computational complexity in additive hedonic games. European Journal of Operational Research, 203(3), 635-639.
4. Levinger, C., Hazon, N., Simola, S., & Azaria, A. (2024). Coalition formation with bounded coalition size. In Proceedings of AAMAS 2024.

Evaluación General: Este es un artículo de alta calidad en informática teórica que realiza contribuciones importantes a la teoría de juegos de coalición restringida. La profundidad teórica e innovación técnica del artículo son destacadas, proporcionando una base sólida para investigaciones posteriores en este campo. Aunque carece de validación experimental, esta limitación es comprensible considerando su naturaleza teórica. Este trabajo tiene un valor académico importante para los campos de teoría de juegos, diseño de algoritmos y sistemas multiagente.