dimanche, mai 27, 2007

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.

1 commentaire:

  1. Rodrigo9:02 PM

    Oi, achei teu blog pelo google tá bem interessante gostei desse post. Quando der dá uma passada pelo meu blog, é sobre camisetas personalizadas, mostra passo a passo como criar uma camiseta personalizada bem maneira. Até mais.

    RépondreSupprimer