📈 economics

Auditing Algorithmic Collusion from Strategy Graphs

Cet article propose un nouveau cadre d'audit qui détecte la collusion algorithmique en analysant les caractéristiques topologiques de graphes de stratégies dérivés des politiques de prix figées des entreprises, démontrant que des mesures telles que la centralité d'intermédiation maximale et le degré d'entrée d'attracteur servent d'indicateurs robustes et économes en données du comportement collusif sans nécessiter l'accès à des données de marché sensibles ou à l'historique des prix.

Auteurs originaux : Nicolas Eschenbaum, Janusz M. Meylahn

Publié 2026-08-10

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Nicolas Eschenbaum, Janusz M. Meylahn

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous regardiez une partie d'échecs à enjeux élevés, mais que les joueurs ne soient pas des humains ; ce sont des programmes informatiques ultra-rapides apprenant à jouer par essais et erreurs. C'est le monde de la tarification algorithmique, où les entreprises laissent l'intelligence artificielle décider du prix de tout, de l'essence aux locations d'appartements. Parfois, ces programmes apprennent accidentellement un signe de reconnaissance secret : ils découvrent que s'ils maintiennent tous les prix élevés, tout le monde gagne plus d'argent, même sans jamais se parler. C'est ce qu'on appelle la collusion algorithmique. C'est un cauchemar pour les régulateurs car il est difficile de la détecter. Habituellement, pour prouver que deux personnes participent à un comportement anticoncurrentiel, il faut les voir chuchoter dans un coin ou trouver une note écrite. Mais avec les ordinateurs, il n'y a pas de chuchotements, et les « notes » sont enfouies dans des millions de lignes de code que les entreprises traitent comme des recettes top secrètes.

Alors, comment attraper un tricheur si vous ne pouvez pas lire son journal intime ou écouter ses appels téléphoniques ? Vous devez regarder la carte de ses décisions. Ne voyez pas un algorithme de tarification comme un cerveau, mais comme un labyrinthe. Chaque fois que l'ordinateur voit une situation spécifique (comme « les prix d'hier étaient élevés »), il a une règle sur ce qu'il doit faire ensuite. Si vous tracez une ligne de chaque situation vers la suivante choisie par l'ordinateur, vous obtenez un immense réseau de chemins entrelacés. Dans un jeu équitable et compétitif, ce réseau est généralement un itinéraire direct et désordonné vers les prix les plus bas. Mais si les ordinateurs colludent, le réseau est différent. Il présente des « points d'étranglement » spécifiques et de longues boucles sinueuses conçues pour punir quiconque tente de briser les règles. Cette étude pose la question suivante : peut-on repérer une conspiration secrète simplement en observant la forme de ce labyrinthe, sans connaître les prix, les profits ou même le code ?

Les auteurs de cet article, Nicolas Eschenbaum et Janusz M. Meylahn, répondent par l'affirmative. Ils proposent une nouvelle façon d'auditer ces algorithmes qui ne nécessite pas de regarder sous le capot. Au lieu de demander le code secret ou les données d'entraînement, ils suggèrent que les régulateurs demandent simplement à l'algorithme : « Si tu étais dans cette situation spécifique, que ferais-tu ? » En posant cette question pour chaque scénario possible, ils peuvent construire le « graphe de stratégie » — la carte du labyrinthe.

Les chercheurs ont découvert que les algorithmes collusifs laissent une empreinte très spécifique sur cette carte. Ils ont constaté que lorsque les algoriths travaillent ensemble pour maintenir les prix élevés, leur labyrinthe de décision développe de forts goulots d'étranglement. Imaginez une ville où, pour rentrer chez soi, vous devez passer par un seul et unique pont étroit. Si vous essayez de prendre un raccourci, vous vous retrouvez coincé dans un embouteillage (une phase de punition) avant de pouvoir traverser ce pont. Dans un marché compétitif, il y a beaucoup de ponts et de raccourcis ; vous pouvez rentrer chez vous rapidement de n'importe où. Mais dans un marché de collusion, la carte est truquée de sorte que presque tous les chemins convergent vers un état de « punition » spécifique avant de revenir à la zone de prix élevés.

Pour le prouver, l'équipe a lancé des milliers de simulations. Ils ont créé un monde simple où deux programmes informatiques apprenaient à fixer les prix. Ils ont testé deux méthodes d'apprentissage différentes : une où les programmes apprenaient ensemble (comme la célèbre méthode « Calvano ») et une autre où ils apprenaient séparément (Q-learning décentralisé). Ils ont également testé un scénario où ils prenaient deux programmes formés séparément et les forçaient à jouer l'un contre l'autre, ce qui brisait leur collusion.

Les résultats étaient frappants. Les chercheurs ont mesuré trois caractéristiques principales du labyrinthe :

Betweenness maximale (Centralité d'intermédiarité) : Cela mesure combien de chemins passent par un seul « point d'étranglement ». Dans les simulations, plus les algorithmes étaient collusifs, plus le trafic était forcé à travers un seul état de punition. La corrélation était forte, avec un score de 0,67 dans les tests principaux.
Degré entrant d'attracteur (In-degree) : Cela compte combien de chemins mènent directement au « lieu heureux » (la boucle de prix élevés). Dans un labyrinthe de collusion, très peu de chemins mènent directement là ; la plupart doivent faire le long détour via la punition. Cette métrique a montré une forte corrélation négative de -0,67 (signifiant qu'à mesure que la collusion augmentait, les chemins directs diminuaient).
Longueur moyenne des chemins : Cela mesure combien d'étapes il faut pour revenir à la boucle de prix élevés après une erreur. Les labyrinthes de collusion avaient des chemins plus longs (moyennant 1,96 étapes dans les modèles théoriques) car les algorithmes imposaient une « phase de punition » avant de pardonner.

Les auteurs précisent avec prudence que ce n'est pas une solution miracle qui prouve instantanément un crime. Ils ont trouvé que ces « métriques de graphe » fonctionnent mieux lorsque les algorithmes ont appris à revenir à la coopération après une punition, plutôt que de simplement abandonner définitivement (une stratégie de type « grim trigger » ou déclencheur fatal). Ils admettent également que dans le monde réel, les algorithmes pourraient être plus complexes, utilisant des choix aléatoires ou des mises à jour continues, ce qui pourrait rendre la carte plus floue. Cependant, leurs simulations suggèrent que la forme du processus de prise de décision est un signal robuste.

La beauté de cette approche réside dans le fait qu'elle nécessite très peu d'informations. Les régulateurs n'ont pas besoin de voir le code secret de l'entreprise, ses données de vente ou ses marges bénéficiaires. Ils ont seulement besoin d'être capables d'interroger la politique figée — l'ensemble des règles que l'algorithme suit actuellement — et de tracer les lignes du labyrinthe. Si la carte montre un seul pont étroit que tout le monde doit traverser pour revenir aux prix élevés, c'est un énorme signal d'alarme indiquant que les algorithmes pourraient être en train de colluder. C'est comme trouver un tunnel secret dans un château ; vous n'avez pas besoin de savoir qui l'a construit ni pourquoi, mais l'existence du tunnel indique que quelque chose de suspect se passe.

En bref, l'article suggère que si nous ne pouvons pas toujours lire l'esprit de ces algorithmes, nous pouvons lire leurs cartes. Et si la carte ressemble à un labyrinthe conçu pour vous piéger dans une boucle de punition avant de vous laisser réintégrer le club des prix élevés, il est temps pour les régulateurs d'examiner la situation de plus près.

Résumé technique : Audit de la collusion algorithmique à partir de graphes de stratégie

Énoncé du problème
Détecter la collusion algorithmique est difficile car les régulateurs manquent souvent d'accès aux algorithmes propriétaires des entreprises, à leurs données d'entraînement et à l'historique complet de leurs marchés. Alors que des régimes d'information extrêmes existent — soit un accès complet au code source, soit uniquement des traces de prix limitées — cet article étudie un régime d'information intermédiaire. Dans ce régime, un auditeur peut interroger des politiques de prix « gelées » (l'action gourmande sélectionnée à chaque état de marché) mais ne possède pas de connaissance des fonctions de demande, des références de prix numériques, des niveaux de profit concurrentiels ou monopolistiques, ni de la méthodologie d'apprentissage spécifique. La question centrale est de savoir si la topologie structurelle de ces politiques gelées contient des signaux robustes de collusion sans nécessiter la reconstruction de l'environnement économique sous-jacent.

Méthodologie
Les auteurs proposent une approche basée sur la théorie des graphes pour l'audit. Ils modélisent l'interaction de $n$ agents dans un jeu de prix répété où chaque agent conditionne ses décisions à un historique tronqué des profils de prix. Une politique déterministe jointe induit un graphe de stratégie $G(\pi)$ , une relation fonctionnelle où les nœuds représentent les états de marché conjoints et les arêtes dirigées représentent la transition vers l'état suivant lorsque tous les agents jouent leurs actions gourmandes.

La méthodologie centrale comprend :

Dérivation de la vérité de terrain (Ground Truth) : Les auteurs analysent d'abord un ensemble complet et analytiquement connu de 101 équilibres de Nash dans un duopole à trois prix avec une demande logit. Ils catégorisent ces équilibres par leur « Indice de Collusion » ( $\Delta$ ), une métrique basée sur le profit allant de 0 (concurrentiel) à 1 (monopolistique).
Définition des métriques : À partir de la logique structurelle des stratégies de récompense et de punition (où les déviations sont punies avant de revenir à la coopération), ils dérivent cinq métriques de théorie des graphes calculées sur la plus grande composante fortement connexe (WCC) du graphe de stratégie :
- Betweenness maximum ( $B_{max}$ ) : Le nombre le plus élevé de chemins de retour passant par un seul nœud non-attracteur (goulot d'étranglement).
- Degré entrant de l'attracteur ( $D_A$ ) : Le nombre moyen d'états transitionnant directement vers l'attracteur (le cycle représentant le résultat à long terme).
- Longueur de chemin moyenne ( $L_A$ ) : Le nombre moyen d'étapes nécessaires pour qu'un état atteigne l'attracteur.
- Fraction du bassin ( $\beta$ ) : La proportion de l'espace d'états total contenue dans la plus grande WCC.
- Nombre d'attracteurs ( $K$ ) : Le décompte des cycles distincts dans le graphe.
Validation empirique : Ces métriques sont testées sur des politiques apprises par deux algorithmes distincts :
- Q-learning de Calvano et al. (2020) : Entraîné dans un environnement à 15 prix sur divers facteurs de remise ( $\gamma \in [0.1, 0.95]$ ), générant 1 800 paires de politiques.
- Q-learning décentralisé (Arslan et Yükel, 2017) : Entraîné dans un environnement à 5 prix.
- Test de rematching : Des politiques entraînées indépendamment sont rematchées entre elles pour briser la collusion, créant ainsi un ensemble de données de résultats concurrentiels à un facteur de remise élevé.

Résultats clés
L'étude montre que des caractéristiques topologiques spécifiques du graphe de stratégie sont fortement corrélées à l'Indice de Collusion basé sur le profit, même en l'absence d'étiquettes de prix ou d'estimations de la demande :

Betweenness maximum : Présente une forte corrélation positive avec l'Indice de Collusion ( $\rho \approx +0.67$ dans les exécutions groupées de Calvano ; $\rho \approx +0.94$ dans l'ensemble d'équilibres analytiques). Les graphes collusifs présentent des « goulots d'étranglement » où les états de punition se situent sur les chemins de retour de la plupart des états transitoires.
Degré entrant de l'attracteur : Présente une forte corrélation négative ( $\rho \approx -0.67$ ). Dans les équilibres de collusion, peu d'états transitent directement vers l'attracteur de prix élevé car les déviations doivent d'abord passer par une phase de punition.
Longueur de chemin moyenne : Présente une corrélation positive ( $\rho \approx +0.57$ ), reflétant les étapes supplémentaires requises pour revenir à la coopération après une phase de punition.
Fraction du bassin et Nombre d'attracteurs : Ces métriques sont moins informatives dans le cadre standard de Calvano (où les politiques concurrentielles forment souvent des graphes à bassin unique) mais deviennent significatives lorsque l'espace d'états est fragmenté, comme dans le cas du Q-learning décentralisé ou de l'expérience de rematching.

Les résultats sont valables pour différents algorithmes d'apprentissage et conceptions expérimentales. Notamment, les métriques reposent uniquement sur la topologie non étiquetée du graphe ; elles ne nécessitent aucune connaissance des prix spécifiques, des profits ou de l'amplitude du facteur de remise.

Signification et affirmations
L'article affirme fournir une « base prometteuse pour l'audit des systèmes de tarification algorithmique sous des informations limitées ». Sa contribution principale est de démontrer que la structure des politiques de prix gelées contient des signaux robustes de collusion.

Faisabilité de l'audit : Les métriques proposées suggèrent qu'une autorité n'a pas besoin de reconstruire le processus d'apprentissage ou d'accéder au code propriétaire pour identifier une potentielle collusion. Au lieu de cela, interroger la réponse de la politique à tous les états réalisables pour construire le graphe de stratégie est suffisant pour générer un filtre structurel.
Détection sans référence (Benchmark-free) : Contrairement aux indices basés sur le profit, ces métriques de graphe ne nécessitent pas de références concurrentielles ou monopolistiques, qui sont souvent indisponibles pour les régulateurs.
Portée et limites : Les auteurs précisent explicitement qu'il s'agit d'un filtre structurel, et non d'une conclusion définitive de collusion. Les métriques détectent les schémas de « récompense et punition » qui reviennent à la coopération, mais peuvent échouer à identifier les équilibres de type « grim trigger » où le système revient de façon permanente à la compétition après une déviation (car ces derniers cachent la branche collusive dans un composant subordonné). De plus, la validation actuelle est limitée à des politiques finies, déterministes et gelées dans des environnements logit stylisés ; l'applicabilité à des politiques stochastiques, adaptatives ou de haute dimension reste une question ouverte.

En résumé, l'article soutient que la topologie d'un graphe de stratégie — spécifiquement la concentration des chemins de retour à travers les états de punition — sert de signature topologique de la collusion algorithmique, offrant un outil pratique pour les régulateurs opérant sous des contraintes d'information.

Articles similaires