Offline Learning of Nash Stable Coalition Structures with Possibly Overlapping Coalitions

1. Problématique et Contexte

L'article s'intéresse au problème de la formation de coalitions dans un cadre où les agents sont égoïstes et où les préférences ne sont pas entièrement connues à l'avance. Contrairement aux modèles classiques de jeux hédoniques qui supposent des coalitions disjointes et des préférences connues, ce travail propose un nouveau cadre pour des coalitions potentiellement chevauchantes (POCF - Possibly Overlapping Coalition Formation) dans un contexte d'information partielle.

• Scénario réel : L'auteur illustre le problème par l'exemple d'une firme de conseil où des consultants doivent être affectés à plusieurs projets simultanément. Les managers ne connaissent pas les préférences exactes des consultants sur les compositions d'équipes et ne peuvent pas tester de nouvelles structures en raison des coûts et des risques. Ils disposent uniquement d'un jeu de données offline (historique de projets et évaluations).
• Objectif : Inférer les préférences des agents à partir de ce jeu de données fixe et construire une structure de coalition qui soit Nash-stable (ou approximativement stable). Une partition est Nash-stable si aucun agent ne peut améliorer son utilité en déviant unilatéralement (en changeant de coalition ou en modifiant son appartenance).
• Contraintes : Les agents peuvent rejoindre plusieurs coalitions simultanément. Les préférences sont additivement séparables et symétriques (l'utilité mutuelle entre deux agents est la même pour les deux, mais peut varier selon la coalition).

2. Méthodologie

L'approche proposée repose sur l'apprentissage hors ligne (offline learning) avec deux modèles de rétroaction d'utilité distincts, gérés par un algorithme général basé sur la minimisation de surrogats.

A. Modèles de Rétroaction

L'article distingue deux niveaux de granularité des données disponibles dans le jeu de données :

1. Rétroaction Semi-Bandit : L'algorithme observe l'utilité individuelle de chaque agent pour chaque interaction avec les autres membres de ses coalitions choisies.
2. Rétroaction Bandit : L'algorithme n'observe que l'utilité globale d'un agent pour l'ensemble de sa partition (somme des interactions), sans connaître les détails des interactions individuelles.

B. Algorithme : Minimisation de Surrogats

L'algorithme central (Algorithme 1) utilise une approche de confiance optimiste/pessimiste (Upper/Lower Confidence Bounds - UCB/LCB) :

• Il construit un estimateur d'utilité $\hat{v}_i$ et une prime d'exploration $b^\delta_i$ basée sur le jeu de données.
• Il définit des bornes de confiance pour l'utilité attendue de chaque agent.
• Il cherche une stratégie conjointe $\phi_{out}$ qui minimise le dual gap (écart de dualité) estimé :
  $$\min_{\phi} \max_{i \in N} [V^{\star, \delta}_i(\phi_{-i}) - V^\delta_i(\phi)]$$
  où $V^{\star, \delta}$ représente la meilleure réponse optimiste et $V^\delta$ l'utilité pessimiste.
• La convergence vers une stratégie $\epsilon$-Nash stable est garantie si le jeu de données satisfait certaines hypothèses de couverture.

C. Hypothèses de Couverture du Jeu de Données

C'est le cœur théorique de l'article. Pour apprendre efficacement, le jeu de données doit couvrir les scénarios de déviation unilatérale.

• Hypothèse 1 (Couverture de la taille des coalitions - Semi-Bandit) : Pour toute déviation unilatérale possible à partir d'une stratégie Nash stable, le jeu de données doit contenir des exemples où la taille de la coalition affectée est la même. C'est une condition nécessaire et suffisante pour l'apprentissage efficace sous rétroaction semi-bandit.
• Hypothèse 2 (Couverture d'Action - Bandit) : Sous rétroaction bandit (moins d'information), l'hypothèse 1 est insuffisante. Une hypothèse plus stricte est requise : le jeu de données doit être aussi informatif qu'un jeu de données généré par des déviations unilatérales spécifiques, permettant d'estimer les vecteurs d'utilité via une régression ridge.

3. Contributions Clés

1. Nouveau Modèle : Introduction d'un cadre d'apprentissage offline pour la formation de coalitions chevauchantes avec préférences inconnues.
2. Conditions de Couverture :
   • Identification d'une condition nécessaire et suffisante (Hypothèse 1) pour l'apprentissage efficace sous rétroaction semi-bandit.
   • Démonstration que cette condition est insuffisante sous rétroaction bandit, nécessitant une hypothèse de couverture d'action plus forte (Hypothèse 2).
3. Complexité Échantillonnale :
   • Conception d'algorithmes avec une complexité échantillonnale optimale (jusqu'à des facteurs logarithmiques) par rapport à $\epsilon$ (le niveau d'approximation de la stabilité).
   • Les bornes dépendent polynomialement du nombre d'agents $n$ et de coalitions candidates $k$, évitant la dépendance exponentielle souvent rencontrée dans les jeux à somme nulle ou générale.
4. Extension aux Stratégies Pures et Mixtes : Bien que le modèle généralise les jeux hédoniques symétriques (qui admettent toujours une solution pure), l'article traite principalement des stratégies mixtes, avec des extensions vers les stratégies pures.

4. Résultats Expérimentaux

Des expériences extensives sur des données synthétiques valident la théorie :

• Performance : L'algorithme converge vers un faible écart de dualité (proche de la stabilité de Nash) lorsque le jeu de données satisfait les hypothèses de couverture (ex: politique d'exploration uniforme).
• Échec en cas de mauvaise couverture : Lorsque le jeu de données ne couvre pas suffisamment les tailles de coalitions ou les déviations (violation de l'hypothèse), la performance se dégrade significativement, confirmant la nécessité des hypothèses théoriques.
• Comparaison Semi-Bandit vs Bandit : Les résultats montrent que l'apprentissage sous rétroaction bandit est plus difficile et nécessite des jeux de données plus riches pour atteindre la même précision, conformément aux bornes théoriques.
• Échelle : La complexité de l'échantillonnage suit les prédictions théoriques ($1/\sqrt{M}$ pour la réduction de l'erreur).

5. Signification et Impact

Ce travail est significatif pour plusieurs raisons :

• Réalisme : Il aborde le problème de la formation de coalitions dans des conditions réalistes où les données sont limitées, coûteuses à collecter et où les agents peuvent participer à plusieurs groupes.
• Théorie de l'Apprentissage : Il établit des liens profonds entre l'apprentissage par renforcement hors ligne (Offline RL) et la théorie des jeux coopératifs, en adaptant les concepts de couverture de données (comme dans les jeux à somme nulle) aux jeux de coalition.
• Garanties : Il fournit des garanties théoriques solides sur la capacité à retrouver des équilibres stables sans interaction active, ce qui est crucial pour des applications sensibles (gestion de ressources, affectation de personnel) où l'exploration active est risquée.

En résumé, l'article démontre qu'il est possible d'apprendre des structures de coalition stables à partir de données historiques passives, à condition que ces données couvrent suffisamment les scénarios de déviation potentiels, et propose des algorithmes efficaces pour y parvenir sous différentes contraintes d'information.