Auditing Algorithmic Collusion from Strategy Graphs

Janusz M. Meylahn; Nicolas Eschenbaum

REVIEW 3 major objections 4 minor 19 references

Auditing Algorithmic Collusion from Strategy Graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Algorithms that collude leave a concentrated bottleneck in their policy graph, and an auditor can detect it from the unlabeled topology alone, without price histories or benchmarks.

desk verdict A useful, clearly written graph-topology screen for algorithmic collusion with an honest out-of-sample design, but the headline signal is tied to the largest-WCC convention and the abstract overclaims robustness. read the letter →

arxiv 2608.07098 v1 pith:R2MVS6WR submitted 2026-08-07 econ.TH

Nicolas Eschenbaum , Janusz M. Meylahn This is my paper · ORCID

classification econ.TH

keywords algorithmiccollusionstrategygraphsreinforcementlearningdetectionantitrustgraphmetricsQ-learning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that a regulator who can query a firm's frozen pricing policy—the action it would take in every market state—can detect collusive behavior from the shape of the resulting strategy graph alone. The authors first derive five graph metrics from a complete set of 101 Nash equilibria of a three-price duopoly, where reward-and-punishment collusion shows up as bottlenecks, long return paths, and few states entering the attractor directly. They then test these metrics on policies learned by two Q-learning algorithms and on rematched policy pairs, finding that maximum betweenness and attractor in-degree correlate strongly with the standard profit-based Collusion Index. If this holds, an antitrust authority needs neither price histories, demand estimates, nor competitive and monopoly benchmarks to screen for algorithmic collusion.

What carries the argument

The central object is the strategy graph: a functional relation whose nodes are joint market states and whose single outgoing edge from each node points to the state reached when all firms play their greedy action. Each weakly connected component of a functional relation contains exactly one cycle, called the attractor, with trees directed toward it. The paper computes all metrics on the largest weakly connected component, treating its cycle as the attractor that governs play. Maximum betweenness counts how many transient states' unique return paths pass through a given state; attractor in-degree counts how many states transition directly into the attractor; average path length is the mean hitting time of the attractor. In collusive graphs a punishment state lies on nearly every return path, so maximum betweenness is high and attractor in-degree is low, while competitive graphs let most states move directly to the competitive outcome.

What would settle it

Train or construct a set of non-collusive policies whose state transitions are governed by operational constraints—such as capacity rationing or cost shocks—that create natural bottlenecks and long return paths, then compute maximum betweenness and attractor in-degree on their strategy graphs; if these graphs score as collusive while the Collusion Index stays near zero, the topological screen fails its central claim.

Watch

Extended reading notes

Core claim

The central discovery is that collusive reward-and-punishment strategies imprint a measurable topological signature on the graph of greedy transitions between states. In a collusive strategy graph, most off-path states are routed through a single punishing state before returning to the collusive attractor, so that state has high return-path betweenness, few states enter the attractor directly, and paths back to it are long. The paper identifies five metrics—maximum betweenness, attractor in-degree, average path length, basin fraction, and number of attractors—and validates their signs and correlations on the analytically known equilibrium set, then on 1,800 runs of the baseline Q-learning algorithm, 600 runs of a Decentralized Q-learning variant, and 1,000 rematched policy pairs. Across these settings, maximum betweenness and attractor in-degree are the consistent signals: they correlate with the Collusion Index at magnitudes between 0.41 and 0.94, with the predicted positive and negative signs respectively. The metrics require only the unlabeled topology of the strategy graph.

Load-bearing premise

The detection signal rests on the auditor's ability to identify the largest weakly connected component as the governing basin and on the correctness of the cited 101-equilibrium enumeration, since switching to the highest-price attractor reverses or erases the signal for three of the five metrics.

Editorial extensions

If this is right

An auditor with disclosure or sandbox access to frozen pricing policies can screen for collusion without access to training data, demand estimates, or price benchmarks.
The two leading metrics remain informative across two different Q-learning algorithms and across a rematching design that breaks trained collusion, suggesting the signal is not an artifact of one learning procedure.
Because the metrics are computed on unlabeled topology, a response interface could in principle return the successor map without revealing the actual prices, preserving some confidentiality.
The method is explicitly a screen, not a finding of collusion: it identifies policies whose structure concentrates return paths through disciplining states, and must be combined with outcome-based evidence to establish harm.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the correlation between maximum betweenness and the Collusion Index persists in richer state spaces, the metrics could be calibrated into thresholds with known statistical properties, turning the screen into a formal audit test.
The same topology-based reasoning might transfer to other algorithmic settings—such as bidding or recommendation systems—where collusive or cooperative strategies need to punish deviations and restore cooperation, though the paper does not test this.
The largest-WCC convention means a grim-trigger strategy that permanently reverts to competition would be classified as competitive; a natural extension would be to detect collusive branches in subordinate components rather than discard them.
A practical bottleneck is query cost: joint state spaces grow as the product of prices and past profiles, and the paper notes that sampling the state space could miss exactly the off-path transitions that reveal a bottleneck.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Bottom line: this is a useful paper with an honest design, and it is worth reading, but the central claim is more convention-dependent than the abstract implies. The headline result — that max betweenness and attractor in-degree predict the Collusion Index from unlabeled strategy graphs — holds under the largest-WCC convention the authors use. Their own appendix Table 4 shows it largely disappears under the highest-price-attractor convention: max betweenness drops from +0.94 to +0.03, average path length and basin fraction lose signal, and number of attractors changes sign. So the 'unlabeled topology' claim is really 'topology plus a component-selection rule.' The paper is transparent about this in an appendix and partly in the conclusion, but the abstract is overbroad.

What is genuinely new: using the complete equilibrium set of a three-price logit game as ground truth, reading off five graph metrics, and then testing those as hypotheses on frozen learned policies from Calvano Q-learning, Decentralized Q-learning, and rematched pairs. That is a real step beyond Zhou's price-labeled attractors and Hartline's trace-based audit. The out-of-sample validation is not curve fitting, and the conclusions are cautiously scoped: the metrics detect only collusion with return to cooperation, grim triggers hide their collusive branch, and no deployable cutoff is given.

Soft spots, in rough order. First, the component-selection issue is load-bearing. The metrics do not themselves tell you which WCC is the dominant basin. In the Calvano runs the largest WCC coincides with where greedy play actually lands in 97.7% of runs, but that is a property of the training protocol, not of unlabeled topology. Within the rematched pairs alone, max betweenness correlates only +0.06 with the index; pooling with training runs restores the correlation and hides that failure. Second, no confidence intervals or significance tests are reported, and the pooled correlations hide substantial run-level scatter. Third, the metrics were selected after inspecting the equilibrium set, so the equilibrium correlations are not independent evidence. Fourth, code and data are not available, and the ground-truth equilibrium set comes from a co-author's paper and is cited but not reproduced. These are addressable, but the first changes how the contribution should be described.

For whom: anyone working on algorithmic collusion detection, and regulators thinking about what an audit can infer from a frozen policy. It deserves a serious referee, not a desk reject. I'd send it with the request that the authors move the convention-sensitivity analysis into the main text, justify the largest-WCC choice from the audit setting, and add inference and data.

Referee Report

3 major / 4 minor

Summary. This paper studies an intermediate-information audit regime in which an authority can query frozen pricing policies and construct the induced strategy graph. The authors derive five graph-theoretic metrics (maximum betweenness, attractor in-degree, average path length, basin fraction, number of attractors) from a complete enumeration of 101 Nash equilibria of a three-price logit duopoly, then test these metrics on policy pairs trained with Calvano et al. (2020) Q-learning, Decentralized Q-learning, and on rematched policy pairs. They report that maximum betweenness and attractor in-degree correlate with the profit-based Collusion Index across these settings and conclude that unlabeled strategy-graph topology contains robust signals of collusive reward-and-punishment structures.

Significance. The paper addresses a question of clear policy relevance: whether an antitrust authority with access only to a frozen policy (not code, training data, demand, or price benchmarks) can screen for collusive structure. The design has real strengths: the hypotheses are derived from a complete equilibrium characterization rather than invented ad hoc; the central validation is out-of-sample on learned policies; the setting covers two learning algorithms and several robustness variations; and the limitations (grim-trigger equilibria, finite deterministic policies) are stated explicitly. The two leading metrics are simple, falsifiable, and easy to compute. If the sensitivity to the component-selection convention can be resolved or made transparent, the proposed screen would be a useful complement to outcome-based detection. The manuscript is not yet at that point because the strongest claims in the abstract and conclusion outrun the evidence in Appendix A and Table 4.

major comments (3)

[Section 3 / Appendix Table 4] The central validation is conditional on the largest-WCC convention. On the 101-equilibrium ground truth, maximum betweenness correlates +0.941 with the Collusion Index under the largest-WCC convention but +0.025 when computed on the highest-price attractor, and average path length changes sign. The paper's own text in Section 3 and the conclusion acknowledges that grim-trigger equilibria hide the collusive branch in a subordinate component, but the abstract's 'unlabeled topology' claim and Section 7's 'robust signals' do not carry this qualification. Since the choice of component is not determined by the metrics themselves, the authors should either justify the largest-WCC convention on independent grounds or reframe the central claim as conditional on the collusive branch governing the dominant basin. This is a load-bearing point, not a presentation issue.
[Section 5, Table 3 and Appendix A] The rematch experiment is reported as a success, but the within-rematch correlation for maximum betweenness is +0.06 (Appendix A), while the pooled rematch column reports +0.686. Pooling the 500 rematched pairs with the 500 training runs hides the fact that, among the rematched pairs alone, the headline metric does not signal the competitive outcome. Similarly, the within-pair average path length is only +0.21. The text should report the within-rematch correlations in the main table and should qualify the claim that the metrics 'carry the hypothesized signs in all four settings.' This is not a request for additional experiments but for honest disaggregation of the reported result.
[Section 4, Tables 2 and 3] All correlations are reported as point estimates without confidence intervals, bootstrap, or significance tests. This matters because the metrics were selected after inspecting the equilibrium set, and the equilibrium-set correlations are therefore descriptive rather than independent confirmations. The authors should provide at least percentile bootstrap intervals for the pooled correlations and ideally for the per-gamma columns, and state that the equilibrium correlations are in-sample summaries. Without this, claims like 'strongly correlated' are hard to calibrate, especially for the per-gamma correlations that move from near zero to large values.

minor comments (4)

[Appendix Table 6] The delta=0.3 column is entirely dashes; please explain why the correlations are not reported for that discount factor.
[Section 7] 'Policies produced by three learning procedures' is inaccurate; the paper uses two learning algorithms plus a rematching construction, which is not a learning procedure. Consider rephrasing.
[Table 2] The closeness centrality is reported without a hypothesis. The pooled correlation is negative (-0.334) while the gamma=0.9 and gamma=0.95 columns are positive; this sign reversal deserves a one-sentence comment to avoid confusion.
[Section 3, Eq. (6)] The definition of b(v) includes v itself in the path; this is fine, but the text could state explicitly that b(v) is at least 1 for every transient v, which helps interpret the competitive case in Figure 1(a).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the metric hypotheses are derived from an equilibrium set and then tested out-of-sample on learned policies, so the validation is not forced by construction.

full rationale

The derivation chain is not circular. The graph metrics in Definitions 2-6 are defined purely structurally, with no reference to the Collusion Index, prices, profits, or benchmarks. The hypotheses are generated from the analytically enumerated 101-equilibrium set and then taken to genuinely new data: 1,800 Calvano Q-learning runs, 600 Decentralized Q-learning runs, and a 500-plus-500 rematch panel. The correlations on learned policies in Tables 2 and 3 are therefore out-of-sample relative to the metric-selection step, so no fitted parameter is being renamed as a prediction. The paper does rely on a self-citation for the equilibrium set: Meylahn is a co-author, and the paper states 'Following the enumeration approach of Meylahn (2025), 101 distinct equilibrium strategy profiles arise.' This is a citation dependency, but the cited result is a parameter-free, externally falsifiable mathematical enumeration for a three-price logit duopoly, and the present paper's learning data do not feed back into that enumeration. Under the review rules, such an external, falsifiable result counts as independent support and does not raise the circularity score. The sensitivity of the largest-WCC convention, documented in Appendix Table 4, is an important limitation: the 'unlabeled topology' claim is conditional on reading metrics off the largest weakly connected component, and under the highest-price attractor the maximum betweenness correlation drops from +0.94 to +0.03. That is a robustness and scope concern, not a definitional equivalence, because the convention is a fixed modeling choice rather than an equation that identifies the metric with the Collusion Index. Similarly, the within-rematch failure of maximum betweenness (+0.06) is disclosed transparently in Appendix A and is not disguised by redefining the metric. Overall, the central validation is conducted on independent learned-policy data, and the paper's own robustness tables make the load-bearing choices explicit rather than hiding them.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the correctness of the enumerated equilibrium set from a co-author, on the largest-WCC convention, and on the auditor's ability to query the full policy. No free parameters are fitted: the market parameters are taken from Calvano et al. (2020).

assumptions (4)

domain assumption The three-price logit duopoly has exactly 101 Nash equilibria as enumerated in Meylahn (2025).
This is the ground-truth set used to select metrics; the paper does not reproduce the enumeration.
domain assumption Decentralized Q-learning converges to Nash equilibrium in this weakly acyclic pricing game (Arslan and Yüksel, 2017; Meylahn, 2023).
Used to justify treating the equilibrium set as reachable by a convergent learner.
ad hoc to paper The largest weakly connected component, not the highest-price component, is the correct component to read the collusive outcome from.
Appendix Table 4 shows the central correlations vanish or change sign under the alternative convention.
domain assumption A regulator can query the frozen deterministic greedy policy for every feasible joint state.
Defines the intermediate information regime; if only a price trace is available, the strategy graph cannot be constructed.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Auditing Algorithmic Collusion from Strategy Graphs." pith.science (2026). https://pith.science/paper/R2MVS6WR

@misc{pith2026260807098,
  author       = {Pith},
  title        = {Pith review of: Auditing Algorithmic Collusion from Strategy Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R2MVS6WR}},
  note         = {Machine review of arXiv:2608.07098}
}

read the original abstract

Detecting algorithmic collusion is challenging because regulators often have limited access to firms' algorithms, training data, and market information. We study an intermediate-information regime in which an auditor can query firms' frozen pricing policies and construct the induced strategy graph. Using a complete characterization of Nash equilibria in a repeated pricing game, we identify graph-theoretic features of strategy graphs that are associated with collusive reward-and-punishment schemes, including maximum betweenness, attractor in-degree, and average path length. We then test these metrics on policies learned by decentralized Q-learning and the Q-learning algorithm of Calvano et al. (2020). We find that especially the maximum betweenness and attractor in-degree are strongly correlated with the standard profit-based Collusion Index. Importantly, the proposed metrics rely only on the unlabeled topology of strategy graphs and require neither price histories, demand estimates, nor competitive and monopoly benchmarks. Our results suggest that the structure of frozen pricing policies contains robust signals of collusion among reinforcement learning algorithms and provides a promising basis for auditing algorithmic pricing systems under limited information.

Figures

Figures reproduced from arXiv: 2608.07098 by the authors.

**Figure 2.** Collusion Index against the normalized maximum betweenness [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 7 canonical work pages

[1]

Artificial Intelligence, Algorithmic Pricing, and Collusion , journal =

Calvano, Emilio and Calzolari, Giacomo and Denicol. Artificial Intelligence, Algorithmic Pricing, and Collusion , journal =. 2020 , volume =. doi:10.1257/aer.20190623 , url =

doi:10.1257/aer.20190623 2020
[2]

The RAND Journal of Economics , year =

Klein, Timo , title =. The RAND Journal of Economics , year =. doi:10.1111/1756-2171.12383 , url =

arXiv
[3]

2022 , note =

Banchio, Martino and Mantegazza, Giacomo , title =. 2022 , note =. doi:10.48550/arXiv.2202.05946 , url =. 2202.05946 , archiveprefix =

arXiv doi:10.48550/arxiv.2202.05946 2022
[4]

Journal of Political Economy , year =

Assad, Stephanie and Clark, Robert and Ershov, Daniel and Xu, Lei , title =. Journal of Political Economy , year =. doi:10.1086/726906 , url =

doi:10.1086/726906
[5]

and MacKay, Alexander , title =

Brown, Zach Y. and MacKay, Alexander , title =. American Economic Journal: Microeconomics , year =. doi:10.1257/mic.20210158 , url =

doi:10.1257/mic.20210158
[6]

, title =

Harrington, Jr., Joseph E. , title =. Journal of Competition Law & Economics , year =. doi:10.1093/joclec/nhy016 , url =

doi:10.1093/joclec/nhy016
[7]

, title =

Harrington, Jr., Joseph E. , title =. Management Science , year =. doi:10.1287/mnsc.2021.4241 , url =

work page arXiv 2021
[8]

2024 , month = jan, note =

Lambin, Xavier , title =. 2024 , month = jan, note =. doi:10.2139/ssrn.4498926 , url =

work page doi:10.2139/ssrn.4498926 2024

Show all 19 references

[9]

Management Science , year =

Abada, Ibrahim and Lambin, Xavier , title =. Management Science , year =. doi:10.1287/mnsc.2022.4623 , url =

2022
[10]

2026 , month = feb, note =

Calder-Wang, Sophie and Kim, Gi Heung , title =. 2026 , month = feb, note =. doi:10.2139/ssrn.4403058 , url =

2026 doi
[11]

2022 , note =

Eschenbaum, Nicolas and Mellgren, Filip and Zahn, Philipp , title =. 2022 , note =. doi:10.48550/arXiv.2201.00345 , url =. 2201.00345 , archiveprefix =

2022 doi arXiv
[12]

IEEE Transactions on Automatic Control , year =

Arslan, Gürdal and Yüksel, Serdar , title =. IEEE Transactions on Automatic Control , year =. doi:10.1109/TAC.2016.2598476 , url =

2016
[13]

, title =

Meylahn, Janusz M. , title =. Chaos , year =. doi:10.1063/5.0281443 , url =

doi
[14]

Can Decentralized

Meylahn, Janusz , booktitle=. Can Decentralized
[15]

Available at SSRN: 4594415 , year=

Does an intermediate price facilitate algorithmic collusion? , author=. Available at SSRN: 4594415 , year=
[16]

2026 , publisher =

Zhou, Chao , title =. 2026 , publisher =. doi:10.5281/zenodo.20367565 , url =

2026 doi
[17]

and Long, Sheng and Zhang, Chenhao , title =

Hartline, Jason D. and Long, Sheng and Zhang, Chenhao , title =. Proceedings of the 2024 Symposium on Computer Science and Law , series =. 2024 , pages =. doi:10.1145/3614407.3643706 , url =

2024
[18]

1965 , isbn =

Harary, Frank and Norman, Robert Zane and Cartwright, Dorwin , title =. 1965 , isbn =

1965
[19]

Journal of Economics & Management Strategy , year =

Asker, John and Fershtman, Chaim and Pakes, Ariel , title =. Journal of Economics & Management Strategy , year =. doi:10.1111/jems.12516 , url =

doi

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Artificial Intelligence, Algorithmic Pricing, and Collusion , journal =

Calvano, Emilio and Calzolari, Giacomo and Denicol. Artificial Intelligence, Algorithmic Pricing, and Collusion , journal =. 2020 , volume =. doi:10.1257/aer.20190623 , url =

doi:10.1257/aer.20190623 2020

[2] [2]

The RAND Journal of Economics , year =

Klein, Timo , title =. The RAND Journal of Economics , year =. doi:10.1111/1756-2171.12383 , url =

arXiv

[3] [3]

2022 , note =

Banchio, Martino and Mantegazza, Giacomo , title =. 2022 , note =. doi:10.48550/arXiv.2202.05946 , url =. 2202.05946 , archiveprefix =

arXiv doi:10.48550/arxiv.2202.05946 2022

[4] [4]

Journal of Political Economy , year =

Assad, Stephanie and Clark, Robert and Ershov, Daniel and Xu, Lei , title =. Journal of Political Economy , year =. doi:10.1086/726906 , url =

doi:10.1086/726906

[5] [5]

and MacKay, Alexander , title =

Brown, Zach Y. and MacKay, Alexander , title =. American Economic Journal: Microeconomics , year =. doi:10.1257/mic.20210158 , url =

doi:10.1257/mic.20210158

[6] [6]

, title =

Harrington, Jr., Joseph E. , title =. Journal of Competition Law & Economics , year =. doi:10.1093/joclec/nhy016 , url =

doi:10.1093/joclec/nhy016

[7] [7]

, title =

Harrington, Jr., Joseph E. , title =. Management Science , year =. doi:10.1287/mnsc.2021.4241 , url =

work page arXiv 2021

[8] [8]

2024 , month = jan, note =

Lambin, Xavier , title =. 2024 , month = jan, note =. doi:10.2139/ssrn.4498926 , url =

work page doi:10.2139/ssrn.4498926 2024