Learning to Coordinate over Networks with Bounded Rationality

1. Problématique

L'article aborde le problème de la coordination dans les réseaux d'agents multi-agents, où les agents sont soumis à une rationalité bornée (bounded rationality). Contrairement aux modèles classiques supposant une optimisation parfaite, les agents réels (humains ou robots) font face à des limitations cognitives, computationnelles ou des erreurs stochastiques.

Le cadre d'étude est un jeu de coordination de type "Chasse au Cerf" (Stag Hunt) binaire sur un graphe. Dans ce jeu, les agents doivent choisir entre une action sûre mais à faible récompense et une action risquée mais à haute récompense qui nécessite une coopération. L'objectif est de déterminer comment la topologie du réseau (connectivité, régularité) interagit avec le niveau de rationalité des agents pour favoriser l'émergence d'un équilibre de coordination parfait (tous les agents choisissent la même action optimale).

2. Méthodologie

Les auteurs utilisent une approche combinant la théorie des jeux, la théorie des graphes et la physique statistique :

• Modèle de jeu : Un jeu de coordination binaire sur un graphe non orienté $G = ([N], E)$. La fonction de gain de chaque agent dépend des actions de ses voisins et d'un paramètre de difficulté de tâche $\theta$.
• Dynamique d'apprentissage : Les agents mettent à jour leurs actions selon l'algorithme Log-Linear Learning (LLL). Ce processus stochastique utilise une fonction de réponse logit, où le paramètre $\beta$ représente le niveau de rationalité (de comportement aléatoire à $\beta=0$ à une meilleure réponse déterministe à $\beta \to \infty$).
• Analyse des états stationnaires : Pour les jeux à potentiel exact, la distribution stationnaire de la chaîne de Markov induite par le LLL est une distribution de Gibbs-Boltzmann. La probabilité d'un état est proportionnelle à $e^{\beta \Phi(a)}$, où $\Phi$ est la fonction de potentiel du jeu.
• Approximations mathématiques :
  • Pour les graphes réguliers ($K$-réguliers), une analyse directe des bornes sur la fonction de potentiel.
  • Pour les graphes irréguliers et les grands réseaux, les auteurs utilisent une approximation gaussienne de la fonction de potentiel (via un théorème central limite pour les martingales) pour approximer la fonction de partition de la distribution de Gibbs.
  • Utilisation de la théorie de la majorisation pour optimiser les distributions de degrés.

3. Contributions Clés

L'article apporte plusieurs contributions théoriques majeures :

1. Preuve de propriété de potentiel : Démonstration que le jeu de coordination en réseau "Chasse au Cerf" est toujours un jeu à potentiel exact, quel que soit le graphe sous-jacent.
2. Monotonie de la coordination :
   • La probabilité stationnaire d'un état parfaitement coordonné est strictement croissante par rapport au paramètre de rationalité $\beta$.
   • Pour les graphes $K$-réguliers, cette probabilité est croissante par rapport au degré de connectivité $K$.
   • Pour les graphes irréguliers, l'ajout d'arêtes (augmentation de la connectivité) augmente strictement la probabilité de coordination.
3. Optimalité des graphes réguliers :
   • Régime de faible rationalité ($\beta \to 0$) : L'optimisation de la probabilité de coordination revient à minimiser la variance de la distribution des degrés. Les graphes $K$-réguliers (ou quasi-réguliers) sont optimaux.
   • Régime de grands réseaux ($N \to \infty$) : Sous des conditions techniques légères, la fonction de partition est bien approximée par la fonction génératrice des moments d'une variable aléatoire gaussienne. Cela confirme que les graphes réguliers maximisent la probabilité de coordination asymptotique.
   • Rationalité modérée : Les graphes réguliers maximisent une borne inférieure spectrale non triviale de la probabilité de coordination.
4. Coût de l'irrégularité (Price of Irregularity - PoI) : Définition et quantification de la pénalité subie par les réseaux irréguliers par rapport aux réseaux réguliers, proportionnelle à la variance des degrés et au carré du paramètre de rationalité.

4. Résultats Principaux

• Relation Rationalité-Connectivité : Il existe un compromis (trade-off) entre la rationalité des agents et la connectivité du réseau. Un réseau plus connecté permet d'atteindre un niveau de coordination donné avec des agents moins rationnels (un $\beta$ plus faible). Une borne supérieure est fournie pour le $\beta_{min}$ requis en fonction du degré $K$.
• Optimisation de la topologie : Pour un nombre fixe d'agents et d'arêtes, la topologie qui maximise la probabilité de convergence vers un équilibre de Nash (profil d'action coordonné) est un graphe régulier (où chaque agent a le même nombre de voisins).
• Robustesse : Même lorsque les agents ne répondent pas parfaitement aux actions des autres, une connectivité uniformément distribuée (régularité) assure la coordination la plus fiable.
• Validation numérique : Les simulations confirment que pour des graphes de taille modérée, les graphes réguliers surpassent systématiquement les graphes irréguliers générés aléatoirement ayant le même nombre d'arêtes.

5. Signification et Implications

Ce travail fournit des principes de conception fondamentaux pour les systèmes multi-agents (robots, réseaux de capteurs, systèmes socio-économiques) où les agents sont limités cognitivement :

1. Conception de réseaux : Pour garantir une coordination fiable sans exiger une intelligence parfaite de chaque agent, les concepteurs doivent privilégier des topologies où la connectivité est uniformément répartie (graphes réguliers).
2. Compensation par la structure : La structure du réseau peut compenser les limitations individuelles. Un réseau dense et régulier permet à des agents "stupides" (faible $\beta$) de prendre collectivement de bonnes décisions, illustrant une forme de "sagesse des foules" émergente.
3. Gestion de l'irrégularité : L'article quantifie le "coût" de l'hétérogénéité des degrés. Dans les grands systèmes, même une légère irrégularité dans la connectivité réduit significativement la probabilité de coordination, surtout si la rationalité des agents n'est pas infinie.

En résumé, l'article démontre mathématiquement que, face à la rationalité bornée, l'égalité de la connectivité est la clé de la stabilité collective.