Un nouvel exemple de Simulation par Théorie des Jeux et Apprentissage

Je vais revenir aujourd’hui sur l’approche GTES (Game Theoretical and Evolutionary Simulation) qui s’inscrit dans la droite ligne des travaux de Robert Axelrod. Cette méthode joue un rôle central dans mes différents travaux de simulation et elle mérite d’être expliquée en profondeur. Pour que le travail effectué sur la simulation des architectures d’entreprises et des flux d’information puisse se transformer en une publication et avoir un impact, il est important que les fondements méthodologiques tels que GTES soient compris et acceptés.

Je suis passé à un acronyme anglais après avoir lu « The Complexity of Cooperation » de R. Axelrod (Princeton University Press, 1997). Le sous-titre de ce livre est « Agent-Based Models of Competitions and Cooperation ». Le thème commun du livre est l’utilisation de modèles à agents pour étudier des scénarios de coopération/compétition entre plusieurs joueurs. Chaque joueur est représenté par un agent, dont la stratégie est optimisée au moyen d’une approche « evolutionary programming », plus précisément des algorithmes génétiques. En clair, R. Axelrod pose la coopération comme un problème d’optimisation global et « découvre » les stratégies des joueurs par apprentissage. Selon mon habitude, voici une liste de points saillants que j’ai relevés, au lieu de faire une véritable synthèse :

1. Le livre commence par une merveilleuse histoire, celle de la stratégie optimale du jeu du « dilemme du prisonnier répété ». Il s’agit d’un jeu classique à deux joueurs, très connu sous sa forme « à un coup » : la stratégie globalement optimale est la coopération, mais du point de vue de chaque joueur, il est préférable de ne pas coopérer (et de « trahir » l’autre). Dès qu’on rentre dans une succession de parties avec les mêmes joueurs, les choses se corsent puisque la trahison appelle la punition … R. Axelrod a organisé dans un premier lieu un tournoi d’agents informatiques (chacun programmé par un chercheur d’un laboratoire différent), puis il a créé un modèle et une expérimentation d’optimisation par algorithme génétique. La beauté de son travail est que les deux approches aboutissent au même résultat : la meilleure stratégie est le « TIT-for-TAT », le fait de reproduire au coup N+1 le mouvement du joueur adverse au coup N. Cette stratégie encourage la coopération mais punit la trahison. Le premier chapitre du livre, qui raconte cette double expérience, est une contribution fondamentale, me semble-t-il, d’un point de vue scientifique.
2. Le second chapitre traite de l’introduction du « bruit » dans les résultats de la coopération et de son influence sur les stratégies des acteurs. Comme le chapitre précédent, il s’agit d’une référence fondamentale pour l’approche GTES qui contribue à établir sa crédibilité.
3. Les pratiquants de la Recherche Opérationnelle apprécieront la partie sur les « paysages » des problèmes d’optimisation. Cette partie contient des réflexions sur la caractérisation des équilibres et des liens avec les équilibres de Nash (cf. un de mes messages précédents)
4. Le chapitre 4 contient une réflexion sur l’organisation des entreprises qui postule le lien entre l’efficacité de l’organisation et la gestion des flux de communication. C’est donc une référence fondatrice pour l’approche « SIFOA » de ce blog.
5. D’un point de vue méthodologique (présentation et discussion d’une simulation), le chapitre 6 est un modèle et je compte m’en inspirer dans le futur J D’une manière plus générale, le livre fourmille de petits commentaires passionnants sur la façon dont les idées se propagent, ou sur comment introduire des éléments aléatoires (stochastiques) dans une simulation.

Je vais maintenant donner un nouvel exemple (simple) de l’approche GTES sur un problème de stratégie de distribution. La simplicité (relative) du modèle (et du problème posé) permet d’apprécier le fonctionnement et l’intérêt d’une telle approche. J’ai implémenté ce modèle sur un problème précis, avec de vrais chiffres mais je vais ici me contenter de le décrire de façon générique.
Je suppose qu’il existe deux compagnies de téléphone A et B qui utilisent plusieurs réseaux de distribution (R1 à R6). Ces réseaux peuvent soit vendre des téléphones (avec un contrat associé), soit procéder à des renouvellements : remplacer un vieux téléphone par un neuf en conservant le contrat existant).
La stratégie de distribution de chaque compagnie (A ou B) est définie par quatre montants, pour chacun des réseaux de distribution : le montant de la subvention pour l’achat ou le renouvellement, qui est la somme d’argent implicitement transférée au consommateur, sous la forme de réduction du prix d’achat, et le montant de la rémunération du réseau de vente, également différentiée selon l’achat ou le renouvellement.
On pourrait penser qu’il s’agit donc d’un problème « simple » d’allocation des ressources, chaque compagnie essayant de générer le maximum de flux pour un montant d’investissement de distribution donnée. En fait, il existe deux sources de complication : (1) les réseaux sont en compétition pour les même clients (2) chaque réseau peut influencer le client qui rentre en contact en fonction de son intérêt propre.
Pour étudier ce couplage et pouvoir comparer les différentes stratégies des deux joueurs A et B (dans la grande tradition de la théorie des jeux, sous forme de matrice), j’ai construit le modèle suivant, inspiré par une conversation avec Pierre Schaller. Il s’agit de suivre 100 clients pendant deux ans, qui vont acheter un téléphone au « temps 0 », puis effectuer une deuxième action au bout de 12 mois : ne rien faire, renouveler son téléphone ou décider d’acheter un nouveau téléphone avec un nouveau contrat (ce que l’on appelle le « churn »).
J’ai décidé d’utiliser deux courbes en S pour modéliser ce marché de 100 clients :

• Une courbe de marché qui donne l’appétence en fonction du prix facial du mobile.
• Une courbe de churn qui donne la répartition renouvellement/changement en fonction du différentiel de prix entre un achat et un renouvellement (plus la différence est importante, plus le client décidera de quitter son contrat plutôt que d’utiliser l’offre de renouvellement)
  

Le modèle proprement dit est fort simple et se décompose en cinq étapes élémentaires :

1. Déterminer les parts de marché globale (A+B) de chacun des réseaux en fonction des prix faciaux pratiqués (c’est-à-dire en tenant compte des subventions). Les déviations, par rapport aux parts de marché initiales, sont obtenues à partir de la courbe en S « de marché ».
2. Déterminer les parts de marché respectives de A et B dans chaque réseau avec la même méthode. On remarquera que dans ce modèle, on s’intéresse à une base fixe de 100 clients, donc on ne prend pas en compte des effets d’agrandissement ou de rétrécissement du marché (ce qui signifie qu’on s’intéresse à la ventilation des investissements de distribution, pas à leur montant global).
3. Déterminer le taux de churn au bout d’un an, en partant d’un taux de souhait de renouvellement (un paramètre du modèle). Le pourcentage des clients qui veulent changer est réparti en deux catégories, churn et renouvellement, à partir du taux de churn original, et un ajustement différentiel obtenu à partir de la seconde courbe en S.
4. Les renouvellements sont distribués selon les réseaux de distribution avec une méthode qui est similaire à celle de l’étape 1-2 : on repart des parts de marché constatées pour les renouvellements, avec un ajustement déduit de la courbe en S et des prix faciaux proposés aux clients.
5. Les clients qui churnent sont transformés en ventes pour l’année 2 en utilisant le modèle des étapes 1-2 (la même chose une année plus tard).

Si l’on cherche à décomposer ce modèle suivant les trois catégories de l’approche GTES, on obtient :

• (a) Les paramètres du modèle sont les deux courbes en S précitées, le taux de changement au bout d’un an et le taux d’indécision, c’est-à-dire la fraction du public qui peut se faire influencer par le réseau pour choisir entre A et B. Les deux derniers paramètres sont assez bien connus, et les sensibilités des courbes en S peuvent être obtenues par différentiation, en supposant que les subventions à l’acquisition sont optimisées par rapport au compromis dépense/acquisition, et que les suventions à l’acquisition sont optimisées par rapport à l’équilibre churn/renouvellement. Cela signifie que nous pouvons remplacer l’approche « Monte-Carlo » qui est habituellement utilisée pour les paramètres dans l’approche GTES par une double simulation pour calibrer les courbes en S.
• (b) Les stratégies des joueurs sont les 2 x 6 x 4 paramètres qui ont déjà été présentés.
• (c) Les « tactiques », qui sont calculées par optimisation (locale ou algorithme génétique), représentent les stratégies des réseaux pour optimiser leur revenus. Elles sont représentées par 3 chiffres : la sur-subvention que le réseau consent pour être plus compétitif (une partie de la rémunération qui est reversée au client), en acquisition et en fidélisation, et un paramètre qui décrit la façon dont le réseau influence les clients indécis.
  

Le déroulement d’une simulation est fort simple : étant donnée les stratégies des deux joueurs A et B, le programme d’optimisation calcule les tactiques optimales de chaque réseau, pour maximiser ses revenus. On relève alors les résultats financiers des joueurs A et B. Cette méthode permet de construire la «matrice des stratégies ».

Quel est l’intérêt d’une talle approche par rapport à un calcul classique utilisant un tableur Excel ? C’est qu’elle permet de prendre en compte la façon dont les réseaux de distribution s’adaptent aux changements de stratégie des joueurs. La sophistication de cette simulation traduit les couplages subtils qui existent entre l’ensemble des parties prenantes. En fait, la réaction des distributeurs par rapport à un changement de A dépend clairement de la stratégie de B. C’est du simple bon sens : si A essaye d’optimiser ses résultats aux dépends de ses distributeurs, ceux-ci changeront d’allégeance si les conditions de B sont plus favorables.

Dans l’exemple précis que j’ai simulé, cette approche permet de voir que cette adaptation « amortit » les effets positifs du changement que A souhaite mettre en place, mais ne l’annule pas. C’est donc une façon constructive d’instruire le débat entre :

• Les partisans du changement qui vont dire que cette nouvelle répartition des investissements commerciaux est plus efficace (ce qu’on « voit » avec un tableur Excel).
• Les « prudents » qui vont expliquer (à juste titre) que la distribution réagira à ces changements de façon contradictoire.
  

J’ai pris un peu de temps avec cet exemple parce qu’il est plus simple que ce que je souhaite faire en terme de simulation d’entreprise pour SIFOA mais illustre bien les apports réciproques de la théorie des jeux et des méthodes d’apprentissage pour simuler des processus complexes de coopération.

Simuler les réseaux sociaux d'entreprise

Je rentre d’un voyage aux US qui m’a permis de rencontrer de nombreuses personnes, et en particulier Dan Rasmus , qui est le « Director of Information Work Vision at Microsoft Corporation » et travaille également pour le « Institute for Innovation and Information Productivity ». Dan joue un rôle de prospectiviste pour Microsoft, c’est également un expert depuis plus de 20 ans sur les questions d’outils et de productivité. Interrogé sur le sujet du ROI (return on investment) des outils qui améliorent la productivité, il propose une réponse que j’aime beaucoup : « Horizontal technologies have no ROI without a business process scenario ». Les technologies « horizontales » sont précisément les technologies qui améliorent la collaboration et la transmission d’information. On retrouve une des clés (qui m’aura pris un certain temps à trouver) : on ne peut pas valoriser les améliorations de réactivité (réduction de latence) sans un scénario complet de l’exécution d’un processus métier.

Deux conclusions :

• La bonne nouvelle, c’est que l’approche « SIFOA » sur laquelle je travaille depuis deux ans, avec un simulateur de processus métier, est la seule qui puisse permettre d’évaluer l’impact de l’usage des (nouveaux) canaux de communication ou des nouvelles formes d’organisation.
• La mauvaise nouvelle, c’est la même chose : La simulation de processus métier est nécessairement complexe et il y a donc un double travail de pédagogie (expliquer le modèle) et d’étalonnage (trouver des données statistiques adaptées) pour asseoir la crédibilité de ce travail.

En passant, je suis surpris par la différence de maturité entre la France et les US sur les sujets d’organisation, de processus métiers et de transmission d’information. Les pré-requis conceptuels que j’essaye de distiller dans ce blog font maintenant partie de la culture « courante » outre-Atlantique.

J’ai donc décomposé mon travail pour 2007 en deux sous-chantiers :

1. Travailler sur la latence du transfert d’information en tant que sous-problème autonome, dans la lignée des travaux de Duncan Watts. C’est ce dont je vais parler dans ce message.
2. Raffiner mon modèle de fonctionnement d’entreprise pour en faire un modèle autonome, dans la tradition des modèles de March & Simon (cf. la review du livre « Organisation » que je ferai d’ici un mois). Ce modèle n’est « qu’une similation » par évènements discrets de processus métier, avec une modélisation simple des enjeux économiques (fonction à optimiser) et des ressources. Il se trouve que ce modèle a également un intérêt propre, pour comprendre l’intérêt de l’approche « Lean Six Sigma » sur une entreprise immatérielle. Je commence à m’intéresser de plus en plus à Lean Six Sigma pour des raisons professionnelles, et certains principes sont contre-intuitifs, ce qui prêche en faveur de la simulation pour se les approprier.
   

Aujourd’hui je vais parler du travail d’expérimentation sur les réseaux sociaux et réseaux d’affiliation, que j’ai commencé il y a un mois, en étant guidé par le livre de Duncan Watts et par un excellent article « Basic Notions for the Analysis of Large Affiliation Networks / Bipartite Graphs » de M. Latapy, C. Magnien et N. Del Vecchio. Je vous recommande le site perso de Matthieu Latapy pour une introduction aux réseaux sociaux en tant qu’objet de recherche scientifique.

J’ai donc réalisé un générateur de graphe aléatoire pour réaliser trois types d’expériences :

1. Génération de réseaux sociaux aléatoires (qui représentent des contacts one-to-one) étiquetés avec des fréquences de contact, et calcul des distances, avec ou sans prise en compte des étiquettes. Dans un cas on obtient le degré de séparation (ce qui permet de valider le modèle par rapport aux résultats connus), dans l’autre cas, on obtient une latence de propagation d’information.
2. Génération d’un réseau social aléatoire qui représente les besoins connus de communication, et évaluation de différentes heuristiques pour construire un réseau social sous contrainte de degré maximal. Cela ressemble beaucoup à un problème d’optimisation de « network design ». Ce qui m’intéresse n’est pas le calcul d’une solution optimale (il n’y a pas de raisons de penser que le réseau social des contacts dans une entreprise soit optimal) mais plutôt de caractériser la latence (distance avec les étiquettes).
3. Génération du même réseau social des besoins de communication, puis génération d’une « couverture » par un réseau d’affiliation, autrement dit d’un ensemble de réunions. C’est la généralisation du cas (2) en remplaçant des arêtes par des hyper-arêtes dans un hypergraphe. Le terme de couverture est indiqué puisque ce problème ressemble à des problèmes de couvertures de graphes/ ensembles (set covering). Ici aussi, je ne cherche pas « la solution optimale »,mais plutôt une heuristique de bonne qualité, pour caractériser ce que l’on peut attendre d’un « bon système réunion ».
   

J’ai terminé les parties (1) et (2) et j’ai maintenant les premiers résultats numériques.
Des que j’ai un peu de temps, je vais rédiger un article. Le générateur de graphe me permet de produire des graphes avec des paramètres différents : distribution des degrés, coefficient de cluster-isation, distribution des fréquences de contact, etc. Je retrouve naturellement (ouf J) les propriétés présentées par Duncan Watts mais elles sont étendues dans le cadre des graphes étiquetés.
En attendant, la conclusion la plus intéressante est double :

1. La loi proposée il y a un an pour caractériser la latence en fonction du diamètre réunionnel, de la taille des réunions, etc. semble être vérifiée expérimentalement. Cf. l’annexe 2 de mon livre : log (Di / Dr) x Dr / T.
2. Les « suggestions » tirées de cette loi, telle que le fait de diminuer le diamètre réunionnel (voire moins de personnes, mais plus souvent) semblent également judicieuces. Les valeurs numériques donnent un petit groupe fortement connecté (de l’ordre de 5 personnes pour une entreprise avec 1000 cadres).
   
   A suivre lorsque j’aurai un peu plus de recul …