Stabilité par Déviation Unique dans les Jeux Hédoniques Additifs Séparables avec Tailles de Coalitions Contraintes

Informations Fondamentales

• ID de l'article: 2510.12641
• Titre: Single-Deviation Stability in Additively Separable Hedonic Games with Constrained Coalition Sizes
• Auteurs: Martin Bullinger (Université de Bristol), Adam Dunajski (Université d'Édimbourg), Edith Elkind (Université Northwestern), Matan Gilboa (Université d'Oxford)
• Classification: cs.GT (Théorie des Jeux), cs.DS (Structures de Données et Algorithmes)
• Date de Publication: 14 octobre 2025 (prépublication arXiv)
• Lien de l'article: https://arxiv.org/abs/2510.12641

Résumé

Cet article étudie les problèmes de stabilité dans les jeux hédoniques additifs séparables (JHAS) lorsque les tailles de coalitions sont soumises à des contraintes de bornes fixes. Les auteurs considèrent quatre concepts classiques de stabilité basés sur la déviation d'un seul agent : la stabilité de Nash (SN), la stabilité individuelle (SI), la stabilité contractuelle de Nash (SCN) et la stabilité contractuelle individuelle (SCI). Pour chaque concept de stabilité, les auteurs examinent deux variantes : l'une exigeant que la coalition abandonnée par les agents qui dévient conserve une taille valide, l'autre sans cette contrainte. L'article fournit un tableau complet de l'existence de résultats stables pour des paramètres de taille donnés et caractérise complètement la complexité computationnelle des problèmes d'existence pertinents lorsque seules des bornes supérieures sont imposées.

Contexte et Motivation de la Recherche

Importance du Problème

La formation de coalitions est un problème central dans les systèmes multi-agents, largement appliqué à :

• La division en groupes pour les projets étudiants
• L'allocation de sièges dans les bureaux de départements
• L'organisation de groupes dans les activités de plein air
• L'arrangement des places aux dîners de conférence

Ces scénarios pratiques partagent une caractéristique commune : les tailles de coalitions doivent satisfaire des contraintes de bornes inférieure et supérieure, tandis que les schémas de partition doivent rester stables face aux comportements de déviation des agents.

Limitations de la Recherche Existante

1. Manque de considération des bornes inférieures : Les travaux antérieurs se concentrent principalement sur les bornes supérieures, avec une recherche insuffisante sur les bornes inférieures
2. Concepts de stabilité incomplets : Absence d'analyse systématique des différents concepts de stabilité sous contraintes
3. Complexité computationnelle non clarifiée : La complexité computationnelle de divers concepts de stabilité sous contraintes n'a pas été complètement caractérisée

Motivation de la Recherche

Cet article vise à combler ces lacunes de recherche en fournissant un cadre théorique complet pour la stabilité des jeux hédoniques sous contraintes de tailles de coalitions.

Contributions Principales

1. Caractérisation Complète de l'Existence : Fournit un tableau complet de l'existence pour tous les concepts de stabilité considérés sous des paramètres de taille donnés
2. Analyse Complète de la Complexité Computationnelle : Caractérise complètement la complexité computationnelle de tous les concepts de stabilité lorsque seules les bornes supérieures sont imposées (λ=1)
3. Algorithmes en Temps Polynomial :
   • Algorithme en temps polynomial pour la stabilité contractuelle individuelle (SCI)
   • Algorithme en temps polynomial pour la stabilité contractuelle de Nash (SCN) lorsque la borne supérieure est 2
   • Algorithme en temps polynomial pour SCI* lorsque la borne inférieure est au moins 2
4. Résultats de NP-Complétude : Prouve la NP-complétude du problème de jugement de stabilité dans plusieurs cas
5. Correction d'Algorithme : Corrige une erreur dans l'algorithme d'Aziz et al. (2013)

Détails Méthodologiques

Définition de la Tâche

Entrée :

• Ensemble d'agents N
• Fonctions d'utilité additives séparables v = (v_a)_{a∈N}, où v_a: N{a} → ℝ
• Contraintes de tailles de coalitions λ ≤ μ (λ borne inférieure, μ borne supérieure)

Sortie :

• (λ,μ)-partition : partition de coalitions satisfaisant les contraintes de taille
• Jugement de stabilité : cette partition satisfait-elle un concept de stabilité spécifique

Contraintes :

• Chaque coalition C satisfait λ ≤ |C| ≤ μ
• Les déviations doivent être (λ,μ)-permissibles ou (λ,μ)-réalisables

Cadre des Concepts de Stabilité

Définitions Fondamentales

Pour l'utilité de l'agent a dans la coalition C : $u_a(C) = \sum_{b \in C\setminus\{a\}} v_a(b)$

Quatre Concepts de Stabilité Standards

1. Stabilité de Nash (SN) : Aucun agent ne peut améliorer son utilité en déviant
2. Stabilité Individuelle (SI) : Déviation de Nash + consentement des membres de la coalition cible
3. Stabilité Contractuelle de Nash (SCN) : Déviation de Nash + consentement des membres de la coalition d'origine
4. Stabilité Contractuelle Individuelle (SCI) : Satisfait simultanément les conditions SI et SCN

Variantes de Réalisabilité

Chaque concept standard possède une variante de réalisabilité correspondante (marquée par *), exigeant que la coalition d'origine satisfasse toujours les contraintes de taille après la déviation.

Algorithmes Clés

Algorithme 1 : Algorithme SCI (Version Corrigée)

Entrée: JHAS (N,v), paramètre μ
Sortie: (1,μ)-partition

1. Initialisation: i←0, A←N
2. tant que A ≠ ∅:
3.   Sélectionner agent a ∈ A
4.   Calculer l'utilité de créer une nouvelle coalition h
5.   pour k ∈ [i]:  // Considérer rejoindre une coalition existante
6.     Calculer l'utilité de rejoindre la coalition k : h'
7.     si h < h': Mettre à jour le choix optimal
8.   Créer/rejoindre une coalition selon le choix optimal
9.   Mettre à jour l'ensemble des agents disponibles A

Algorithme 3 : Algorithme SCI* (Évaluations Non-Nulles)

Pour le cas de borne inférieure λ≥2, via une approche en deux phases :

1. Phase I : Former les coalitions optimales de taille minimale pour chaque leader
2. Phase II : Remplir les agents restants en ordre inverse

Configuration Expérimentale

Cadre d'Analyse Théorique

Cet article procède principalement à une analyse théorique, incluant :

1. Preuves d'Existence : Preuves constructives et contre-exemples
2. Analyse de Complexité : Preuves par réduction et conception d'algorithmes
3. Correction d'Algorithmes : Vérification formelle

Méthodes d'Analyse de Complexité

• Preuves de NP-Complétude : Réductions depuis 3-SAT, X3C et autres problèmes classiques
• Algorithmes Polynomiaux : Conception d'algorithmes constructifs
• Analyse de Bornes Inférieures : Preuve de non-existence par contre-exemples

Résultats Expérimentaux

Résultats d'Existence

Découvertes Clés :

• Les évaluations symétriques garantissent l'existence du concept de stabilité réalisable le plus fort (SN*)
• Même pour les évaluations symétriques simples, les concepts de stabilité standards peuvent ne pas exister
• SCI* existe toujours (lorsqu'une partition réalisable existe)

Résultats de Complexité Computationnelle (λ=1)

Complexité Algorithmique Spécifique :

• SCI : Algorithme polynomial avec complexité temporelle O(n³)
• SCN (μ=2) : Algorithme polynomial avec complexité temporelle O(n²)
• SN/SI : NP-complétude prouvée par réduction depuis le problème d'appariement minimax

Résultats pour Borne Inférieure λ≥2

Travaux Connexes

Fondamentaux des Jeux Hédoniques

• Drèze & Greenberg (1980) : Introduction du concept de jeux hédoniques
• Bogomolnaia & Jackson (2002) : Établissement des jeux hédoniques additifs séparables

Développement des Concepts de Stabilité

• Sung & Dimitrov (2010) : Complexité de la stabilité par déviation unique
• Aziz et al. (2013) : Algorithme polynomial pour SCI (erreur découverte et corrigée dans cet article)

Recherche sur les Coalitions Contraintes

• Levinger et al. (2024) : Stabilité collective sous contraintes de bornes supérieures
• Fioravantes et al. (2025) : Analyse de complexité paramétrée

Conclusions et Discussion

Conclusions Principales

1. Dichotomie d'Existence : Différence fondamentale entre concepts de stabilité réalisables et standards en termes d'existence
2. Hiérarchie de Complexité : Progression claire de la complexité, de la solvabilité polynomiale de SCI à la NP-complétude de SN
3. Impact des Contraintes : Les bornes inférieures affectent significativement l'existence et la calculabilité de la stabilité

Limitations

1. Problèmes Ouverts : La complexité de SN pour λ=2, μ=3 reste indéterminée
2. Applications Pratiques : Le lien entre résultats théoriques et scénarios d'application pratique nécessite une recherche supplémentaire
3. Efficacité Algorithmique : Certains algorithmes polynomiaux peuvent avoir des facteurs constants importants

Directions Futures

1. Autres Types de Jeux : Extension à des modèles tels que les jeux hédoniques fractionnaires
2. Algorithmes d'Approximation : Conception d'algorithmes d'approximation pour les cas NP-difficiles
3. Algorithmes En Ligne : Considération de la formation de coalitions dans les environnements dynamiques

Évaluation Approfondie

Avantages

1. Complétude Théorique : Fournit un cadre théorique systématique pour la stabilité des jeux hédoniques contraints
2. Innovations Techniques :
   • Constructions de réductions ingénieuses (par exemple, réduction X3C vers SCN)
   • Conception d'algorithmes innovants (algorithme SCI* en deux phases)
   • Correction d'erreurs (correction de l'algorithme d'Aziz et al.)
3. Profondeur des Résultats : Fournit non seulement l'existence mais aussi des algorithmes constructifs
4. Clarté de la Rédaction : Définitions claires des concepts, structure complète des preuves

Insuffisances

1. Absence de Validation Expérimentale : Travail purement théorique, manque de vérification sur données réelles
2. Guidance d'Application Limitée : L'orientation pour les scénarios d'application pratique nécessite une exploration supplémentaire
3. Certaines Preuves Longues : Quelques preuves de NP-complétude sont complexes, la lisibilité pourrait être améliorée

Impact

1. Valeur Académique : Fournit une base théorique importante pour la théorie des jeux de coalitions contraintes
2. Valeur Pratique : Fournit des outils algorithmiques pour les problèmes réels de formation de coalitions
3. Reproductibilité : Les descriptions d'algorithmes sont claires et faciles à implémenter et vérifier

Scénarios Applicables

1. Domaine Éducatif : Groupement d'étudiants, organisation de cours
2. Gestion Organisationnelle : Formation d'équipes, allocation de ressources
3. Choix Social : Formation de coalitions électorales, formation de groupes d'intérêts
4. Informatique : Clustering de nœuds dans les systèmes distribués

Références

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.

Évaluation Globale : Ceci est un article de haute qualité en informatique théorique qui apporte des contributions importantes à la théorie des jeux de coalitions contraintes. La profondeur théorique et l'innovation technique de l'article sont remarquables, posant une base solide pour les recherches futures dans ce domaine. Bien que l'absence de validation expérimentale soit une limitation, cette restriction est compréhensible compte tenu de la nature théorique du travail. Ce travail possède une valeur académique importante pour la théorie des jeux, la conception d'algorithmes et les systèmes multi-agents.