Strategic bottlenecks in frozen pricing policies reveal algorithmic collusion: in simulations of learning agents, maximum betweenness and attractor in-degree of policy strategy graphs predict supra-competitive profits strongly, offering a low-information audit that requires only queried policy responses.

Main Finding

Frozen (greedy) pricing policies contain robust, purely structural signals of reward-and-punishment (collusive) schemes. A small set of graph-theoretic metrics computed on the strategy graph induced by a joint frozen policy — most importantly maximum return-path betweenness and attractor in-degree — correlate strongly with profit-based measures of collusion, while requiring only the unlabeled topology of the strategy graph (no price labels, demand estimates, price histories, or benchmark profits).

Key Points

• Audit object: the strategy graph G(π) induced by a deterministic greedy joint policy π. Nodes = feasible joint states; each node has exactly one outgoing edge to its greedy successor. Each weakly connected component (WCC) contains one directed cycle (the attractor) and trees feeding into it.
• Intuition: collusive equilibria sustain supra-competitive attractors by punishing deviations and routing many off-path states through punishment states. This produces identifiable topological signatures (bottlenecks, longer return paths, concentrated basins).
• Proposed metrics (computed on the largest WCC):
  • Maximum betweenness Bmax: maximum number of transient nodes whose path to the attractor passes through a given node (normalized version ˜Bmax ∈ (0,1]).
  • Attractor in-degree DA: average in-degree of nodes on the attractor (fewer direct entrants → more punishment detours).
  • Average path length LA: mean number of steps from nodes to the attractor.
  • Basin fraction β: size of the largest WCC relative to the full feasible-state set.
  • Number of attractors K: number of WCCs (each WCC has one attractor).
  • (Reported but not hypothesized separately) closeness centrality of the attractor (reciprocal of average distance).
• Hypotheses and observed directions:
  • Bmax positively correlates with collusiveness.
  • DA negatively correlates with collusiveness.
  • LA positively correlates with collusiveness.
  • β positively, and K negatively, correlated with collusiveness (but these are less informative unless the state space fragments).
• Ground truth analysis (three-price duopoly with logit demand):
  • Complete equilibrium characterization: 101 Nash equilibria (29 symmetric, 72 asymmetric) across discount factors.
  • Equilibria fall into three classes by attractor outcome: competitive (∆=0, 28 equilibria), partial collusion (∆≈0.70, 48), full collusion (∆=1, 25).
  • The graph metrics separate these classes as hypothesized: collusive equilibria show larger Bmax, smaller DA, larger LA.
• Learned-policy experiments:
  • Calvano et al. (2020) Q-learning setup (15-price grid): 1,800 trained policy pairs across discount factors 0.1–0.95.
  • Maximum betweenness, attractor in-degree, and average path length strongly correlate with the Collusion Index; pooled absolute correlations between ~0.57 and 0.67.
  • Correlations (especially for Bmax and DA) increase with higher discount factors (longer horizons).
• Robustness checks:
  • Replacing the learner with Decentralized Q-learning (convergent algorithm) on a coarser 5-price grid yields similar sign and magnitude relationships.
  • Rematching independently trained policies (which tend to be overfit to training opponents) breaks collusion; Bmax and DA retain their sign and correlation, while β and K become more informative when competition fragments the state space.
• Important practical property: metrics require only the unlabeled topology of the strategy graph (who transitions to whom), not numerical price labels, demand functions, price histories, or monopoly/competitive benchmarks (which are typically unavailable to auditors).

Data & Methods

• Analytical ground truth:
  • Duopoly, logit demand (Calvano parameters), firms choose from {pL,pM,pH}, memory length l=1 → 9 joint states.
  • Complete enumeration of Nash equilibria (Meylahn 2023–2025) yields 101 deterministic equilibrium policies; used to derive and validate the metric hypotheses.
  • Metrics computed on the largest WCC; attractor A is the cycle of that component.
• Empirical experiments on learned policies:
  • Calvano-style Q-learning (15-price grid): trained two agents across a sweep of discount factors to produce 1,800 frozen-policy pairs. For each pair, construct the strategy graph from the greedy action at each joint state and compute metrics on the largest WCC.
  • Decentralized Q-learning (Arslan & Yüksel 2017): run on a 5-price grid to test algorithmic robustness.
  • Rematching experiment: independently trained policies are paired with non-training rivals to see if collusive structure persists.
• Statistical assessment:
  • Correlate graph metrics with the Collusion Index ∆(π) = (average per-firm profit − Nash profit)/(monopoly profit − Nash profit).
  • Report pooled correlations and analyze dependence on discount factor and environment variations.
• Computation notes:
  • Maximum betweenness is computed as the count of transient nodes whose unique path to the attractor includes a given node; normalized version divides by number of transient nodes.
  • Average path length LA = mean hitting time τA(u) over nodes in the largest WCC.
  • Attractor in-degree DA = mean in-degree d(a) for attractor nodes within the largest WCC.

Implications for AI Economics

Practical auditing - What regulators can request: frozen-policy disclosure (for each feasible joint-state, the greedy joint-action) or sandbox queries that allow construction of the induced strategy graph. - Low-information audit: compute the unlabeled strategy graph and the five metrics. Policies with high normalized maximum betweenness, low attractor in-degree, and long average return paths are priority targets for deeper investigation. - Advantages: these diagnostics do not require access to proprietary demand estimates, price labels, counterfactual benchmarks, or long price traces — lowering the bar for meaningful audits while focusing on behavioural structure (reward-and-punishment schemes). Policy design and enforcement - Disclosure regimes or sandboxing requirements that yield frozen-policy graphs could enable inexpensive, automated screening for collusion risk. - Graph-based flags could be used to trigger targeted interventions (e.g., requests for additional information, experiments, or behavioral remedies) rather than full disclosure of code/data by default. Research and methodological directions - Apply and validate the approach in richer environments: larger action spaces, multi-firm markets (n>2), continuous prices (requiring discretization), more complex state spaces, partial observability, and stochastic environments. - Calibrate statistical thresholds and false-positive/false-negative trade-offs for practical enforcement. - Study strategic obfuscation: firms might hide collusion by randomizing or by designing policies whose greedy projection masks punishment structure; robustness to such manipulations needs assessment. Limitations and caveats - Access requirement: the method requires the frozen-policy mapping on (a sufficiently large portion of) the feasible-state set. If an auditor can only observe limited on-path traces (low-information regime), the graph cannot be fully reconstructed. - Blind spots: collusive schemes that isolate supra-competitive attractors in small components not forming the largest WCC (e.g., strict grim-trigger equilibria producing absorbing collusive components with tiny basins) will be missed by metrics computed on the largest WCC. - Dependence on state specification: results depend on how the state space is constructed (memory length, which signals are included). Different state encodings can change the induced graph topology. - Environment dependence: the reported correlations are established in canonical oligopoly simulations and a complete small-game equilibrium set; performance in field data or more complex simulations must be empirically validated. Relation to existing literature - Complements statistical-trace audits (Hartline et al., 2024) and frozen-policy graph work (Zhou, 2026) by providing topology-only diagnostics derived from analytical equilibrium structure (Meylahn’s equilibrium enumeration) and validated on Q-learning outcomes (Calvano et al., 2020). Concluding note - Strategy-graph topology offers a promising, low-information pathway to screen for algorithmic collusion by detecting the structural fingerprints of reward-and-punishment enforcement. For practical adoption, regulators should consider sandboxed frozen-policy disclosure standards, pilot evaluations in richer market models, and development of operational thresholds and complementary (trace- or benchmark-based) audits.