Résumé Technique : Apprentissage de la Valeur Stratégique et de la Coopération dans les Jeux Stochastiques Multi-Joueurs via des Paiements Latéraux

1. Énoncé du Problème

L'article aborde le défi de définir et de calculer une valeur stratégique à long terme par joueur dans des jeux stochastiques multi-joueurs à somme générale avec utilité transférable. Dans des contextes où les agents peuvent utiliser des paiements latéraux (par exemple, des contrats, des crédits) pour stabiliser des comportements mutuellement bénéfiques, la question centrale n'est pas seulement d'identifier une politique d'équilibre, mais de déterminer comment allouer la valeur à long terme afin que la coopération devienne rationnelle individuellement pour chaque agent.

Les concepts de solution existants sont insuffisants pour cet objectif spécifique :

• Les valeurs minimax sont restreintes aux contextes à somme nulle et à deux joueurs.
• Les valeurs de Shapley s'appliquent aux jeux coopératifs à utilité transférable mais nécessitent une fonction caractéristique pour chaque coalition et ne capturent pas intrinsèquement les menaces stratégiques découlant d'un jeu non coopératif.
• Les équilibres de Nash et corrélés dans les jeux stochastiques multi-joueurs à somme générale souffrent souvent de non-unicité, d'intraitabilité computationnelle et d'un manque de décomposition en composantes coopératives et compétitives adaptées aux paiements latéraux.
• Les valeurs Coco (Kalai & Kalai, 2013) et leurs extensions stochastiques (Coco-Q) offrent une décomposition convaincante pour les jeux à deux joueurs mais ne se généralisent pas directement à $n > 2$ joueurs avec des caractérisations axiomatiques comparables.

Les auteurs visent à étendre la valeur Harsanyi–Shapley (HS) — qui définit le « pouvoir de menace » d'une coalition via un jeu à somme nulle opposant la coalition à son complément — au cadre dynamique des jeux stochastiques. L'obstacle technique central est que, dans les jeux stochastiques, les menaces et les opportunités se propagent à travers les transitions d'état, rendant la « valeur d'une coalition » un objet dépendant de l'état et à long terme, plutôt qu'un scalaire unique.

2. Méthodologie

L'article introduit deux notions de valeur distinctes basées sur HS pour les jeux stochastiques, toutes deux se réduisant à la valeur HS sous forme normale lorsque le jeu possède un seul état.

2.1 HS-S (Décomposition Coalitionnelle)

HS-S relève la formule HS sous forme normale en agrégeant les pouvoirs de menace dynamiques des coalitions sur tout le futur.

• Mécanisme : Pour chaque coalition non triviale $I \subseteq N$, les auteurs construisent un jeu stochastique à deux joueurs à somme nulle induit entre $I$ et son complément $\bar{I}$. Ils calculent le pouvoir de menace $\delta_G(I, x)$, défini comme le point fixe unique de l'opérateur de Bellman pour ce jeu à somme nulle (la valeur maxmin que la coalition $I$ peut garantir contre $\bar{I}$).
• Agrégation : La valeur HS-S pour le joueur $i$ à l'état $x$ est une somme pondérée de ces pouvoirs de menace, utilisant les poids standards de style Shapley :
  $$V^{HS-S}_i(x) = \frac{1}{n} \sum_{I \subseteq N: i \in I} \binom{n-1}{|I|-1}^{-1} [\delta_G](I, x)$$
• Axiomes : Les auteurs étendent les axiomes de Kohlberg–Neyman (efficacité, symétrie, additivité, joueur nul, rationalité individuelle et menaces équilibrées) au cadre stochastique. Ils prouvent que HS-S est l'unique application satisfaisant ces axiomes (avec « menaces équilibrées » relâché en « menaces faiblement équilibrées »).

2.2 COCO-S (Opérateur de Bellman)

COCO-S adopte une approche « teintée de programmation dynamique », appliquant le calcul HS sous forme normale localement à chaque état.

• Mécanisme : Pour une fonction de valeur candidate $V$, les auteurs définissent un jeu sous forme normale local $H_x(V)$ à chaque état $x$. Les gains dans $H_x(V)$ intègrent les récompenses immédiates plus les valeurs de continuation actualisées basées sur $V$.
• Opérateur : Ils définissent un opérateur de style Bellman $\tilde{T}$ où $[\tilde{T}(V)](x) = HS(H_x(V))$. La valeur COCO-S est définie comme un point fixe de cet opérateur : $V = \tilde{T}(V)$.
• Propriétés : Cette construction généralise l'opérateur Coco-Q à deux joueurs. Les auteurs prouvent l'existence de points fixes pour tous les jeux stochastiques finis et établissent l'unicité pour les jeux à deux joueurs et les jeux à trois joueurs et deux états (via la théorie du degré topologique et des conditions spectrales).

2.3 Comparaison et Divergence

• Cas à deux joueurs : Pour $n=2$, HS-S et COCO-S coïncident. Toutes deux satisfont l'ensemble complet des axiomes HS.
• Cas multi-joueurs ($n > 2$) : Les deux valeurs divergent. Les auteurs fournissent un contre-exemple explicite à trois joueurs où $V^{HS-S} \neq V^{COCO-S}$.
  • HS-S satisfait les Menaces Faiblement Équilibrées mais viole la Cohérence Markovienne (la valeur à un état dépend des pouvoirs de menace à l'horizon infini, et non seulement de la structure du jeu local avec des continuations auto-cohérentes).
  • COCO-S satisfait la Cohérence Markovienne (la valeur à un état est déterminée en appliquant la formule HS au jeu local avec des continuations auto-cohérentes) mais viole les Menaces Faiblement Équilibrées.

2.4 Calcul Pratique

Pour remédier à l'explosion combinatoire de l'évaluation de toutes les $2^n$ coalitions, l'article propose des estimateurs basés sur l'échantillonnage :

• Estimation HS-S : Une agrégation Monte Carlo en un seul coup des pouvoirs de menace des coalitions échantillonnées.
• Estimation COCO-S : Un algorithme itératif d'itération de valeur où l'opérateur HS est approximé par un échantillonnage de coalitions à chaque étape. Les propriétés de contraction de l'opérateur atténuent les erreurs d'échantillonnage des itérations précédentes.
• Complexité : Les deux estimateurs atteignent une complexité en échantillons de $\tilde{O}(n^2)$ avec des garanties à échantillon fini.

3. Contributions Clés

1. Deux Notions de Valeur Basées sur HS : La définition de HS-S (via décomposition coalitionnelle dynamique) et de COCO-S (via un opérateur de style Bellman) pour les jeux stochastiques à somme générale et $n$ joueurs.
2. Caractérisation Axiomatique :
   • Preuve que HS-S est la valeur unique satisfaisant l'efficacité, la symétrie, l'additivité, le joueur nul, la rationalité individuelle et les menaces faiblement équilibrées.
   • Preuve que COCO-S est la valeur unique satisfaisant la Cohérence Markovienne par rapport à la valeur Harsanyi–Shapley.
3. Analyse Structurelle : Démonstration que les deux valeurs coïncident pour $n=2$ mais divergent pour $n > 2$, la divergence étant expliquée par le compromis entre la satisfaction des Menaces Faiblement Équilibrées (HS-S) et de la Cohérence Markovienne (COCO-S).
4. Existence et Unicité : Preuve de l'existence de points fixes pour COCO-S (via le théorème de Brouwer) et de l'unicité pour des classes spécifiques de jeux (deux joueurs, trois joueurs deux états) via la théorie du degré topologique.
5. Protocole d'Implémentation : Une dérivation d'un protocole de paiement latéral dynamique à partir des valeurs COCO-S. À chaque état, l'action coopérative maximise le gain total, et des transferts équilibrés budgétairement garantissent que le gain espéré de chaque joueur égale sa valeur COCO-S.
6. Validation Empirique : Évaluation sur des jeux de grille multi-joueurs (Dilemme du Prisonnier généralisé, Coordination, Friend-or-Foe, etc.). Les résultats montrent que les deux méthodes produisent des valeurs stratégiques et des paiements latéraux sensés, s'accordant souvent sur la force relative des joueurs mais différant sur les valeurs nominales. COCO-S a démontré une convergence robuste dans l'itération de valeur, tandis que Correlated-Q a souvent échoué à converger dans les contextes multi-joueurs.

4. Résultats

• Convergence : L'itération de valeur avec l'opérateur COCO-S a convergé de manière robuste sur tous les benchmarks testés. En revanche, Correlated-Q (CE) a fréquemment échoué à converger dans les jeux multi-joueurs à somme générale.
• Paiements Latéraux : COCO-S génère des paiements latéraux par état interprétables comme une redistribution locale du surplus. Les paiements latéraux HS-S sont cohérents au niveau de la politique mais peuvent attribuer de la valeur provenant d'états lointains à l'état actuel.
• Passage à l'Échelle : Les estimateurs basés sur l'échantillonnage ont considérablement réduit le temps de calcul (par exemple, de l'énumération de 4 096 coalitions à l'échantillonnage de 3 000) tout en maintenant de faibles erreurs d'estimation. Dans un jeu à deux états et 12 joueurs, l'échantillonnage COCO-S a atteint des écarts absolus maximaux plus faibles que l'échantillonnage HS-S.
• Désaccord : Dans les jeux asymétriques (par exemple, Friend-or-Foe), HS-S et COCO-S peuvent diverger considérablement sur la force nominale des joueurs, reflétant leur traitement différent des horizons de menace.

5. Signification et Revendications

L'article revendique fournir l'objet manquant nécessaire pour soutenir des paiements latéraux rationnels dans des environnements stratégiques multi-agents : une valeur stratégique par joueur, fondée sur des principes et axiomatique, pour les jeux stochastiques.

• Contribution Théorique : Il établit qu'il existe deux manières distinctes et bien définies d'étendre la valeur Harsanyi–Shapley aux jeux stochastiques, distinguées par les axiomes qu'elles satisfont (Menaces Faiblement Équilibrées vs Cohérence Markovienne). Cela clarifie le paysage des concepts de solution coopératifs dans des contextes dynamiques.
• Contribution Pratique : Il offre un cadre computationnellement traitable (via COCO-S et l'échantillonnage) pour calculer des valeurs et générer des protocoles de paiement latéral qui rendent la coopération rationnelle individuellement.
• Limites et Travaux Futurs : Les auteurs notent modestement que l'unicité de COCO-S pour $n$ et $m$ généraux repose sur une condition spectrale qui est vérifiée numériquement mais pas encore prouvée pour tous les jeux stochastiques finis. Ils identifient également l'extension de ces caractérisations aux espaces d'états infinis et le développement d'estimateurs plus efficaces en échantillons comme des directions ouvertes.

Le travail ne revendique pas de résoudre tous les problèmes d'apprentissage multi-agents mais cible spécifiquement l'allocation de valeur dans des contextes à utilité transférable pour justifier et mettre en œuvre la coopération via des paiements latéraux.