📈 economics

Auditing Algorithmic Collusion from Strategy Graphs

This paper proposes a novel auditing framework that detects algorithmic collusion by analyzing topological features of strategy graphs derived from firms' frozen pricing policies, demonstrating that metrics like maximum betweenness and attractor in-degree serve as robust, data-efficient indicators of collusive behavior without requiring access to sensitive market data or price histories.

Original authors: Nicolas Eschenbaum, Janusz M. Meylahn

Published 2026-08-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nicolas Eschenbaum, Janusz M. Meylahn

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching a high-stakes game of chess, but the players aren't humans; they are super-fast computer programs learning how to play by trial and error. This is the world of algorithmic pricing, where companies let artificial intelligence decide how much to charge for everything from gas to apartment rentals. Sometimes, these programs accidentally learn a secret handshake: they figure out that if they all keep prices high, everyone makes more money, even without ever talking to each other. This is called algorithmic collusion. It's a nightmare for regulators because it's hard to catch. Usually, to prove two people are engaging in anti-competitive behavior, you need to see them whispering in a corner or find a written note. But with computers, there are no whispers, and the "notes" are buried in millions of lines of code that companies treat as top-secret recipes.

So, how do you catch a cheater if you can't read their diary or listen to their phone calls? You have to look at the map of their decisions. Think of a pricing algorithm not as a brain, but as a maze. Every time the computer sees a specific situation (like "yesterday's prices were high"), it has a rule for what to do next. If you draw a line from every situation to the next one the computer chooses, you get a giant, tangled web of paths. In a fair, competitive game, this web is usually a messy, direct route to the lowest prices. But if the computers are colluding, the web looks different. It has specific "choke points" and long, winding loops designed to punish anyone who tries to break the rules. This paper asks: Can we spot a secret conspiracy just by looking at the shape of this maze, without knowing the prices, the profits, or even the code?

The authors of this paper, Nicolas Eschenbaum and Janusz M. Meylahn, say yes. They propose a new way to audit these algorithms that doesn't require peeking under the hood. Instead of asking for the secret code or the training data, they suggest regulators simply ask the algorithm: "If you were in this specific situation, what would you do?" By asking this for every possible scenario, they can build the "strategy graph"—the map of the maze.

The researchers discovered that collusive algorithms leave a very specific fingerprint on this map. They found that when algorithms are working together to keep prices high, their decision-maze develops strong bottlenecks. Imagine a city where, to get home from anywhere, you must pass through a single, narrow bridge. If you try to take a shortcut, you get stuck in a traffic jam (a punishment phase) before you can cross that bridge. In a competitive market, there are many bridges and shortcuts; you can get home quickly from anywhere. But in a collusive market, the map is rigged so that almost every path funnels through a specific "punishment state" before returning to the high-price zone.

To prove this, the team ran thousands of simulations. They created a simple world where two computer programs learned to set prices. They tested two different learning methods: one where the programs learned together (like the famous "Calvano" method) and another where they learned separately (Decentralized Q-learning). They also tested a scenario where they took two programs trained separately and forced them to play against each other, which broke their collusion.

The results were striking. The researchers measured three main features of the maze:

Maximum Betweenness: This measures how many paths go through a single "choke point." In the simulations, the more collusive the algorithms were, the more traffic was forced through a single punishment state. The correlation was strong, with a score of 0.67 in the main tests.
Attractor In-degree: This counts how many paths lead directly into the "happy place" (the high-price loop). In a collusive maze, very few paths lead directly there; most have to take the long way around via punishment. This metric showed a strong negative correlation of -0.67 (meaning as collusion went up, direct paths went down).
Average Path Length: This measures how many steps it takes to get back to the high-price loop after a mistake. Collusive mazes had longer paths (averaging 1.96 steps in the theoretical models) because the algorithms forced a "punishment phase" before forgiving.

The authors are careful to note that this isn't a magic bullet that instantly proves a crime. They found that these "graph metrics" work best when the algorithms have learned to return to cooperation after a punishment, rather than just giving up forever (a "grim trigger" strategy). They also admit that in the real world, algorithms might be more complex, using random choices or continuous updates, which could make the map fuzzier. However, their simulations suggest that the shape of the decision-making process is a robust signal.

The beauty of this approach is that it requires very little information. Regulators don't need to see the company's secret code, their sales data, or their profit margins. They just need to be able to query the frozen policy—the set of rules the algorithm follows right now—and trace the lines of the maze. If the map shows a single, narrow bridge that everyone must cross to get back to the high prices, it's a huge red flag that the algorithms might be colluding. It's like finding a secret tunnel in a castle; you don't need to know who built it or why, but the existence of the tunnel tells you something suspicious is going on.

In short, the paper suggests that while we can't always read the minds of these algorithms, we can read their maps. And if the map looks like a maze designed to trap you in a punishment loop before letting you back into the high-price club, it's time for the regulators to take a closer look.

Technical Summary: Auditing Algorithmic Collusion from Strategy Graphs

Problem Statement
Detecting algorithmic collusion is difficult because regulators often lack access to firms' proprietary algorithms, training data, and full market histories. While extreme information regimes exist—either full access to source code or only limited price traces—this paper investigates an intermediate information regime. In this regime, an auditor can query "frozen" pricing policies (the greedy action selected at each market state) but lacks knowledge of demand functions, numerical price benchmarks, competitive/monopoly profit levels, or the specific training methodology. The central question is whether the structural topology of these frozen policies contains robust signals of collusion without requiring the reconstruction of the underlying economic environment.

Methodology
The authors propose a graph-theoretic approach to auditing. They model the interaction of $n$ agents in a repeated pricing game where each agent conditions decisions on a truncated history of price profiles. A joint deterministic policy induces a strategy graph $G(\pi)$ , a functional relation where nodes represent joint market states and directed edges represent the transition to the next state when all agents play their greedy actions.

The core methodology involves:

Ground Truth Derivation: The authors first analyze a complete, analytically known set of 101 Nash equilibria in a three-price duopoly game with logit demand. They categorize these equilibria by their "Collusion Index" ( $\Delta$ ), a profit-based metric ranging from 0 (competitive) to 1 (monopoly).
Metric Definition: From the structural logic of reward-and-punishment strategies (where deviations are punished before returning to cooperation), they derive five graph-theoretic metrics computed on the largest weakly connected component (WCC) of the strategy graph:
- Maximum Betweenness ( $B_{max}$ ): The highest number of return paths passing through a single non-attractor node (bottleneck).
- Attractor In-degree ( $D_A$ ): The average number of states transitioning directly into the attractor (the cycle representing the long-run outcome).
- Average Path Length ( $L_A$ ): The mean number of steps required for any state to reach the attractor.
- Basin Fraction ( $\beta$ ): The proportion of the total state space contained within the largest WCC.
- Number of Attractors ( $K$ ): The count of distinct cycles in the graph.
Empirical Validation: These metrics are tested on policies learned by two distinct algorithms:
- Calvano et al. (2020) Q-learning: Trained in a 15-price environment across varying discount factors ( $\gamma \in [0.1, 0.95]$ ), generating 1,800 policy pairs.
- Decentralized Q-learning (Arslan and Yükel, 2017): Trained in a 5-price environment.
- Rematching Test: Independently trained policies are rematched against each other to break collusion, creating a dataset of competitive outcomes at a high discount factor.

Key Results
The study finds that specific topological features of the strategy graph correlate strongly with the profit-based Collusion Index, even in the absence of price labels or demand estimates:

Maximum Betweenness: Shows a strong positive correlation with the Collusion Index ( $\rho \approx +0.67$ in pooled Calvano runs; $\rho \approx +0.94$ in the analytical equilibrium set). Collusive graphs exhibit "bottlenecks" where punishment states lie on the return paths of most transient states.
Attractor In-degree: Shows a strong negative correlation ( $\rho \approx -0.67$ ). In collusive equilibria, fewer states transition directly to the high-price attractor because deviations must first pass through a punishment phase.
Average Path Length: Shows a positive correlation ( $\rho \approx +0.57$ ), reflecting the additional steps required to return to cooperation after a punishment phase.
Basin Fraction and Number of Attractors: These metrics are less informative in the standard Calvano setting (where competitive policies often form single-basin graphs) but become significant when the state space is fragmented, such as in the Decentralized Q-learning setting or the rematching experiment.

The results hold across different learning algorithms and experimental designs. Notably, the metrics rely solely on the unlabeled topology of the graph; they do not require knowledge of the specific prices, profits, or the magnitude of the discount factor.

Significance and Claims
The paper claims to provide a "promising basis for auditing algorithmic pricing systems under limited information." Its primary contribution is demonstrating that the structure of frozen pricing policies contains robust signals of collusion.

Audit Feasibility: The proposed metrics suggest that an authority need not reconstruct the training process or access proprietary code to identify potential collusion. Instead, querying the policy's response to all feasible states to construct the strategy graph is sufficient to generate a structural screen.
Benchmark-Free Detection: Unlike profit-based indices, these graph metrics do not require competitive or monopoly benchmarks, which are often unavailable to regulators.
Scope and Limitations: The authors explicitly state that this is a structural screen, not a definitive finding of collusion. The metrics detect "reward-and-punishment" schemes that return to cooperation but may fail to identify "grim trigger" equilibria where the system permanently reverts to competition after a deviation (as these hide the collusive branch in a subordinate component). Furthermore, the current validation is limited to finite, deterministic, and frozen policies in stylized logit environments; the applicability to stochastic, adaptive, or high-dimensional policies remains an open question.

In summary, the paper argues that the topology of a strategy graph—specifically the concentration of return paths through punishment states—serves as a topological signature of algorithmic collusion, offering a practical tool for regulators operating under information constraints.

More like this