Sequential Elimination and Union Shapley Value for Group Assessment in Coalitional Games

Résumé technique : Élimination séquentielle et valeur de Shapley d'union pour l'évaluation de groupes dans les jeux coopératifs

Énoncé du problème
En théorie des jeux coopératifs et dans des domaines connexes tels que la centralité des réseaux et l'évaluation des données en apprentissage automatique, un défi fondamental consiste à étendre les évaluations individuelles des joueurs à des groupes. Les méthodes existantes reposent généralement sur deux approches directes :

1. Somme : Agrégation des valeurs individuelles (par exemple, la somme des valeurs de Shapley). Cela ignore la structure sous-jacente de la coopération et les dépendances entre les joueurs.
2. Fusion : Traitement du groupe comme un élément unique fusionné et évaluation de celui-ci (par exemple, la valeur de Shapley de fusion). Cela altère la structure du jeu et échoue à distinguer les joueurs indépendants des joueurs fortement dépendants.

Les deux approches échouent souvent à capturer avec précision les dépendances au sein des groupes. Par exemple, dans un jeu où deux paires disjointes de joueurs génèrent de la valeur indépendamment, la somme des valeurs individuelles ou la fusion des groupes peut attribuer incorrectement une importance égale à une paire de joueurs coopératifs et à une paire de joueurs indépendants, ne parvenant pas à refléter l'asymétrie de leur impact systémique.

Méthodologie
Les auteurs proposent et analysent une troisième approche fondée sur l'élimination séquentielle. Dans ce cadre, les éléments d'un groupe sont retirés un par un, et leurs évaluations dans les jeux réduits résultants sont agrégées. L'hypothèse centrale est que cette méthode mesure naturellement la contribution nette d'un groupe en décomptant les effets de chevauchement et en se concentrant sur le dommage causé par l'absence du groupe.

L'étude repose sur une analyse axiomatique complète des valeurs de groupe dans les jeux coopératifs. La méthodologie comprend :

• Définition de classes axiomatiques : Les auteurs introduisent une classe de semivaleurs de groupe (cohérentes faibles). Ce sont des valeurs de groupe satisfaisant la linéarité, la symétrie, la monotonie faible, l'axiome du joueur nul et l'axiome du joueur fictif. Ils définissent également une classe correspondante de semivaleurs de synergie, qui remplacent l'axiome du joueur fictif par l'axiome du joueur rendant fictif (introduit par Grabisch et Roubens).
• Extension séquentielle : L'article établit qu'une valeur de joueur admet une extension séquentielle si et seulement si elle satisfait la propriété de contributions équilibrées. Il est démontré que toute semivaleur cohérente (satisfaisant l'axiome du joueur nul) admet une extension séquentielle unique.
• Fonction potentielle : Les auteurs utilisent la fonction potentielle introduite par Hart et Mas-Colell pour caractériser l'extension séquentielle de la valeur de Shapley.

Contributions et résultats clés

1. La valeur de Shapley d'union :
   Les auteurs introduisent la valeur de Shapley d'union comme l'extension séquentielle unique de la valeur de Shapley. Elle est définie comme la différence entre le potentiel du jeu original et le potentiel du jeu après le retrait du groupe :
   $$US_S(N, v) = P(N, v) - P(N \setminus S, v) = \sum_{T \subseteq N, S \cap T \neq \emptyset} \frac{\Delta v(T)}{|T|}$$
   où $\Delta v(T)$ sont les dividendes de Harsanyi.

   • Interprétation : Cette valeur mesure le « dommage » infligé au jeu lorsqu'un groupe se retire. Elle agrège les contributions de telle sorte que le dividende de chaque coalition soit compté au plus une fois, même si le groupe contient plusieurs membres de cette coalition.
   • Axiomatisation : La valeur de Shapley d'union est caractérisée de manière unique par les axiomes de Potentiel (ou de Contributions équilibrées) combinés à l'Efficacité. Elle est également caractérisée de manière unique parmi les semivaleurs de groupe par l'Égalité des groupes (tous les groupes dans un jeu d'unanimité sont également importants).

2. Classification axiomatique des valeurs de groupe :
   L'article distingue deux variantes de l'évaluation de groupe :

   • Valeur totale : Valeurs qui évaluent la valeur totale d'un groupe (par exemple, extension de la somme, Shapley de fusion, Shapley d'union). Celles-ci sont capturées par les semivaleurs de groupe.
   • Synergie : Valeurs qui mesurent la synergie d'un groupe (par exemple, indice d'interaction). Celles-ci sont capturées par les semivaleurs de synergie.
     Les auteurs fournissent une correspondance fonctionnelle entre ces deux classes. Plus précisément, ils montrent que la valeur de Shapley de fusion correspond à l'indice d'interaction (un équivalent synergique), et que la valeur de Shapley d'union correspond à une nouvelle valeur synergique appelée valeur de Shapley d'intersection.

3. La valeur de Shapley d'intersection :
   Définie comme la somme des dividendes des coalitions qui contiennent l'intégralité du groupe :
   $$IS_S(N, v) = \sum_{S \subseteq T \subseteq N} \frac{\Delta v(T)}{|T|}$$
   Cette valeur mesure l'intersection des contributions. Pour un groupe de taille deux, la somme de la valeur de Shapley d'union et de la valeur de Shapley d'intersection égale la somme des valeurs de Shapley individuelles :
   $$US_{\{i,j\}}(N, v) + IS_{\{i,j\}}(N, v) = SV_i(N, v) + SV_j(N, v)$$
   Cette décomposition permet de séparer la valeur conjointe d'un groupe en une partie « union » (comptant les contributions une seule fois) et une partie « intersection » (synergie).

4. Comparaison avec les travaux existants :
   L'analyse clarifie la relation entre les valeurs proposées et la littérature existante :

   • La valeur de Shapley de fusion (Marichal et al.) est démontrée comme étant la semivaleur de groupe unique satisfaisant l'axiome de la coalition fictive.
   • L'indice d'interaction (Grabisch et Roubens) est identifié comme une semivaleur de synergie, distincte des semivaleurs de groupe car il viole l'axiome standard du joueur fictif au profit de l'axiome du joueur rendant fictif.
   • L'article démontre que l'approche par extension séquentielle est théoriquement robuste, car elle s'applique à toutes les semivaleurs cohérentes et produit des valeurs dotées de fortes propriétés axiomatiques.

Signification
L'article affirme que l'approche par extension séquentielle, et spécifiquement la valeur de Shapley d'union, constitue l'une des extensions les plus naturelles et théoriquement fondées des valeurs de joueurs vers les groupes dans les jeux coopératifs. En distinguant l'évaluation de la valeur totale de la mesure de la synergie, les auteurs fournissent un cadre unifié qui clarifie les différences entre les notions existantes dans la littérature. L'introduction des valeurs de Shapley d'union et d'intersection offre de nouveaux outils pour analyser les interactions, en particulier dans les scénarios où le chevauchement des contributions doit être décompté (Union) ou où la synergie pure doit être isolée (Intersection). Le travail établit que ces valeurs ne sont pas des heuristiques arbitraires, mais sont déterminées de manière unique par des axiomes fondamentaux tels que les contributions équilibrées, le potentiel et l'égalité des groupes.