L'approche GTES et les équilibres entre acteurs

Aujourd’hui je vais traiter d’un sujet un peu théorique, dont j’ai parlé de nombreuses fois mais toujours de façon superficielle, à savoir la recherche d’équilibres dans les jeux non-coopératifs. Je suis en train de préparer un article qui fait suite à ma présentation à ROADEF’2007 (conférence de recherche opérationnelle ). J’ai déjà parlé lors de messages précédents de l’application de l’approche GTES (Game Theoretical Evolutionary Simulation) à différents jeux d’acteurs, qu’il s’agissent d’opérateurs de téléphonie dans un marché concurrentiel, ou de stratégie d’utilisation des canaux de communication dans une entreprise.

Mon sujet du jour est la caractérisation des équilibres, et plus précisément l’extension d’équilibre de Nash ainsi que la méthode (évolutionnaire) pour les construire. On rappelle que la méthode GTES est la combinaison :

• D’une simulation Monte-Carlo (pour des paramètres « externes »),
• D’une approche paramétrique (la « stratégie » de chaque acteur détermine la fonction d’utilité),
• D’une recherche d’équilibre par optimisation locale de la « tactique » de chaque acteur.

Ici nous allons ignorer le premier point (un jeu de paramètres externes est fixé) ainsi que le second (la stratégie de chaque acteur est également fixée). Nous sommes donc dans le cadre classique d’un jeu de la théorie des jeux (S,f). S est l’ensemble des profils de stratégies, et f est la fonction d’utilité associée (f_i(s) est le résultat économique pour l’acteur i de la stratégie s = (s1, …, sn)). Attention au vocabulaire, ce que j’appelle la tactique dans mes autres messages correspond à la stratégie au sens de la théorie des jeux (il faudra probablement que je révise ma terminologie …).

Une stratégie globale (s*1, .. , s*n) est un Nash_equilibrium (NE) si et seulement si pour chaque acteur, cette stratégie est optimale en supposant les stratégies des autres acteurs fixées.
Ce qui s’écrit : Pour tout i, pour tout s du support de i, f_i(s, s*-i) <= f_i(s*i, s*-i)

Le support (profile) d’un acteur est l’ensemble des stratégies qu’il peut appliquer.
On peut raisonner sur des stratégies pures (décrites par les supports S) ou avec des stratégies mixtes (combinaisons de plusieurs stratégies avec des probabilités). L’avantage de la structure mixte est de garantir l’existence d’au moins un équilibre de Nash que l’obtient par point fixe d’une séquence d’optimisation (appelée « best response » dans le jargon GT) : BR_i(s) = la (ou une) stratégie pour l’acteur i qui optimise le retour de i si chaque acteur j applique s_j.

Dans le cas « pur », il n’existe pas forcément d’équilibre de Nash. Si l’on applique une séquence itérative d’optimisation et si elle converge, on trouve un équilibre de Nash, mais c’est une condition très forte. En revanche, on remarque que si l’on sait construire BR_i(s) par une technique itérative (BR est lui–même le point fixe d’une séquence d’optimisation), cette approche conduit à un algorithme simple de recherche de l’équilibre :

• Sélectioner un acteur
• Sélectionner une amélioration de sa stratégie
• Répéter jusqu’à stabilisation (facile à mesurer avec une distance) ou time-out.

Dans la version initiale de GTES, j’ai proposé de caractériser un jeu d’acteur selon le comportement de cet algorithme :

• Un jeu qui provoque la convergence est déclaré stable (et on trouve de fait le NE (Nash Equilibrium) associé).
• Un jeu qui provoque une trajectoire divergente (que je n’ai pas le temps de caractériser ici mais cela signifie qu’on peut constater la divergence) est qualifié de « war ».
• Les autres cas sont déclarés « chaotiques »

Un cas chaotique ne signifie pas qu’il n’existe pas de NE, simplement qu’il n’est pas facile à trouver. En fait, un NE difficile à trouver n’est pas forcément un bon modèle pour le comportement des acteurs, donc cette distinction en 3 types est logique.

Dans la « vraie vie », les acteurs peuvent observer les résultats et affiner leurs stratégie (ou réagir), tous les mois ou tous les 3 mois par exemple. On est donc, le plus souvent dans le cadre des « repeated games » (cf. les travaux d’Axelrod que j’ai déjà cité plusieurs fois). Quand on étudie les jeux « chaotiques », on s’aperçoit qu’il existe souvent des situations conflictuelles que des acteurs « réels » évitent (après un apprentissage pour découvrir que ces « stratégies » sont sans issue). On arrive à la conclusion que la caractérisation (stable = "NE facile à trouver") est trop forte.

J’ai donc proposé une extension qui peut faire penser à la notion de stratégie mixte. Au lieu d’appliquer une recherche itérative sur une stratégie, j’associe plusieurs stratégies à chaque acteur (par exemple trois). Pour chaque acteur i, SS_i est un ensemble de stratégies.
La valuation proposée pour cette extension est une valuation minimale de toutes les combinaisons de stratégies : f_i(SS) = min(f_i(s), s in SS). Il s’agit donc de minimiser la prise de risque, c'est-à-dire trouver la stratégie qui assure le meilleur retour dans le pire cas.
La notion d’équilibre peut s’étend comme suit : SS est un NSE (Nash Set Equilibrium) <=> pour tout i, pour tout s, f_i(s U SS-i) <= f_i(SS)

La recherche d’un tel équilibre se fait également avec un algorithme itératif. On associe un « pool » de k stratégies à chaque acteur. Une étape d’optimisation locale (qui produit une nouvelle stratégie pour un acteur i) n’est conservée que si cette stratégie apporte une amélioration par rapport à un membre du pool pour la métrique « min » précédemment définie.
L’algorithme itératif est intéressant parce qu’il ressemble à un algorithme génétique, et on peut donc de la même façon construire en parallèle la recherche de la « best response » pour l’ensemble des acteurs.

Par construction, il est d’autant plus facile de converger que le pool est grand (même si la convergence est exponentiellement longue en fonction de la longueur k de ce pool). En particulier, si la première recherche converge vers un NE, la recherche k-étendue converge vers un k-NSE qui contient k copies du NE, soit {NE} en tant qu’ensemble.
C’est donc une extension (qui justifie le E dans GTES) qui permet de classer un plus grand nombre de configuration dans la catégorie « stable ».

Pour l'instant, après mes premières expérimentations, je vois deux intérêts à cette approche:

1. dans les cas qui étaient stables au sens précédent, la convergence est plus rapide ! Cela s'explique ... mais je manque de temps.
2. Cette approche permet de converger vers une solution unique (si chaque pool contient des copies d'une seule stratégie, on a construit un NE) en évitant des "cycles divergents". Ceci demandera une caractérisation plus précise. Au début des itération, le pool joue le rôle de mémoire des acteurs et permet d'éviter d'emprunter des cycles divergents (ou la "best response" de chacun devient de plus en plus exacerbée et éloigne l'ensemble des acteurs du NE).

Pourquoi assommer le lecteur de ce blog avec cette digression mathématique ? Il se trouve que je suis à la recherche de références. Donc si cette généralisation de la notion de Nash Equilibrium vous dit quelque chose, faites-le moi savoir. Les deux avantages précédents sont indépendants de cette extension (je peux utiliser la k-extension de la recherche itérative comme une façon plus efficace de chercher les NE).