Résumé technique : Une classe traitable de jeux coopératifs définie par des réseaux orientés

Énoncé du problème

L'article aborde les défis computationnels et analytiques inhérents à la théorie des jeux coopératifs, spécifiquement concernant les jeux induits par des graphes orientés pondérés. Les jeux coopératifs souffrent généralement d'une taille de représentation exponentielle par rapport au nombre de joueurs, rendant le calcul des concepts de solution (tels que les valeurs de Shapley et de Banzhaf) et des propriétés de stabilité (telles que le noyau) intraitable (complexe $\sharp$P dans de nombreux cas).

Alors que des travaux antérieurs ont étudié des jeux induits par des graphes non orientés ou des sous-classes spécifiques (par exemple, les jeux de vote pondérés), il existe un besoin de classes structurées de jeux définies par des réseaux orientés qui restent traitables sur les plans analytique et computationnel. Les auteurs introduisent une classe spécifique de jeux, appelée « jeux de confiance », où la valeur d'une coalition est déterminée à la fois par les interactions internes et les expositions externes. Le défi principal consiste à dériver des formules en forme close et en temps polynomial pour les concepts de solution et à caractériser les propriétés de stabilité de ces jeux, d'autant plus que la composante externe introduit un comportement non additif, de type goulot d'étranglement.

Méthodologie

Les auteurs définissent le jeu de confiance $(N, v)$ induit par un graphe orienté pondéré $G = (N, E)$ avec des poids d'arêtes $a_{ij} \in [0, 1]$. La valeur d'une coalition $S \subseteq N$ est définie comme la somme de deux composantes :

1. Terme interne : La somme des poids de toutes les arêtes $(i, j)$ où $i, j \in S$. Cela correspond à un jeu de sous-graphe induit.
2. Terme externe : Pour chaque joueur $i \in S$ qui possède des arêtes entrantes provenant de l'extérieur de $S$, la valeur inclut le minimum des poids parmi ces arêtes entrantes. Si un joueur dans $S$ n'a aucune arête entrante provenant de l'extérieur, ce terme contribue pour 0.

Mathématiquement :
$$v(S) = \sum_{i \in S, j \in S, (i,j) \in E} a_{ij} + \sum_{i \in S^*} \min_{j \notin S: (j,i) \in E} a_{ji}$$
où $S^*$ est l'ensemble des joueurs dans $S$ ayant au moins une arête entrante en provenance de $N \setminus S$.

Pour analyser ce jeu, les auteurs emploient la transformée de Möbius pour décomposer le jeu en une combinaison linéaire de jeux d'unanimité ($u_T$).

• La composante interne est directe, impliquant des jeux d'unanimité par paires.
• La composante externe est plus complexe en raison de l'opérateur $\min$. Les auteurs ordonnent les prédécesseurs de chaque joueur $i$ par poids d'arêtes croissants. Ils démontrent que le jeu externe pour le joueur $i$ peut être exprimé comme une somme télescopique de jeux d'unanimité, où les supports forment une chaîne d'inclusion déterminée par le classement des prédécesseurs.

Cette décomposition permet aux auteurs de tirer parti de la linéarité des opérateurs de Shapley et de Banzhaf pour dériver des formules explicites.

Contributions et résultats clés

1. Décomposition en unanimité

L'article établit une décomposition en unanimité en forme close pour le jeu de confiance.

• Lemme 2.3 : Le jeu externe $w_i(S)$ pour un joueur $i$ est décomposé en une somme de jeux d'unanimité $u_{T_i(t)}$, où $T_i(t)$ est constitué du joueur $i$ et de ses $t-1$ premiers prédécesseurs (ordonnés par poids). Les coefficients sont les différences des poids d'arêtes triés.
• Lemme 3.2 : Le jeu total $v(S)$ est la somme des jeux d'unanimité par paires internes et des jeux d'unanimité externes décomposés.

2. Concepts de solution en temps polynomial

En utilisant la décomposition en unanimité, les auteurs dérivent des formules explicites et en temps polynomial pour :

• Valeur de Shapley ($\phi_i$) : La valeur est exprimée comme la somme de trois parties :
  1. La moyenne des poids d'arêtes internes (centralité de degré pondéré symétrique).
  2. Un terme dérivé des propres arêtes entrantes du joueur $i$ (exposition externe).
  3. Un terme dérivé des arêtes entrantes vers les successeurs de $i$ (effets de voisins partagés).
     La formule (Théorème 3.1) prend explicitement en compte le rang de chaque joueur parmi les prédécesseurs des autres.
• Valeur de Banzhaf ($\beta_i$) : De même, une formule en forme close est dérivée (Théorème 4.2), utilisant la valeur spécifique de Banzhaf des jeux d'unanimité ($2^{1-|T|}$).

3. Analyse des effets marginaux

L'article analyse comment les changements locaux dans les poids d'arêtes affectent les valeurs de solution.

• Lemmes 3.5 et 4.3 : L'effet marginal d'un poids d'arête $a_{kj}$ sur la valeur d'un joueur dépend de la position du joueur par rapport à l'arête :
  • Arêtes internes : Contribuent linéairement aux valeurs de Shapley et de Banzhaf.
  • Arêtes externes : L'effet est non linéaire et dépend du rang du joueur parmi les prédécesseurs du nœud cible. Pour la valeur de Shapley, l'effet implique des termes tels que $\frac{1}{r(r+1)}$, tandis que la valeur de Banzhaf implique $\frac{1}{2^r}$.
• Caractérisation du joueur nul : Le Lemme 3.6 fournit les conditions nécessaires et suffisantes pour qu'un joueur soit un joueur nul (valeur 0), ce qui se produit s'il n'a aucune arête entrante ou si ses arêtes entrantes proviennent de joueurs qui sont eux-mêmes nuls dans un sens structurel spécifique.

4. Stabilité et propriétés du noyau

Les auteurs étudient la stabilité du jeu de confiance :

• Caractérisation du noyau (Lemme 5.1) : Le noyau du jeu de confiance est un singleton. Il consiste en une allocation unique où chaque joueur $i$ reçoit la somme de tous les poids d'arêtes entrants provenant de l'ensemble du graphe ($\sum_{j} a_{ji}$).
• Équilibre total (Lemme 5.2) : Le jeu est totalement équilibré, ce qui signifie que chaque sous-jeu (restreint à n'importe quelle coalition $S$) a un noyau non vide. Cela est prouvé en construisant une allocation de noyau explicite pour tout sous-jeu.
• Divergence des concepts : L'article met en évidence que l'allocation unique du noyau (basée sur les poids d'arêtes entrants totaux) ne coïncide généralement pas avec les valeurs de Shapley ou de Banzhaf. Cela démontre un cadre où les allocations basées sur la stabilité et les concepts de solution basés sur l'équité divergent.

Importance et affirmations

L'article prétend fournir un exemple traitable de jeux coopératifs structurés induits par des réseaux. Son importance réside dans :

1. Traitabilité computationnelle : Il offre une classe de jeux où les concepts de solution (Shapley, Banzhaf) et les propriétés de stabilité (Noyau) peuvent être calculés en temps polynomial, évitant la complexité exponentielle typique des jeux coopératifs généraux.
2. Insight structurel : La décomposition en unanimité révèle que l'opérateur « minimum » complexe dans la composante externe crée une chaîne imbriquée de jeux d'unanimité, rendant le jeu gérable analytiquement.
3. Distinction théorique : Il illustre explicitement un scénario où le noyau (stabilité) et la valeur de Shapley (équité/contribution marginale) produisent des allocations différentes, malgré le fait que le jeu soit totalement équilibré.
4. Fondement pour les travaux futurs : Les auteurs suggèrent que cette classe sert de base pour explorer des généralisations paramétriques, des règles d'agrégation alternatives pour la composante externe et des problèmes de conception de mécanismes concernant l'incitation à la compatibilité.

L'ouvrage ne propose pas de nouvelles applications expérimentales mais établit plutôt un cadre théorique pour analyser les interactions coopératives dans des réseaux orientés avec des évaluations locales asymétriques.