Competition relies on hard computation: if firms can efficiently detect deviations they can sustain collusion, so computational tractability undermines competitive equilibria. As firms' algorithmic capabilities grow, AI could therefore shift markets from competitive toward collusive regimes, offering a theoretical account of algorithmic collusion without explicit coordination.

Main Finding

The paper proves a formal computational boundary between competitive and collusive markets: sustaining collusion in realistically rich, noisy markets requires solving NP-hard problems. Concretely, three central components of collusion—(i) computing joint profit-maximizing strategies (CSP), (ii) detecting deviations from a collusive plan from observed price-quantity data (CDP), and (iii) computing optimal punishments (OPP)—are all NP-hard in general, while the myopic competitive best-response (CBR) is polynomial-time solvable. Consequently: - If P = NP, firms could efficiently solve the collusion problems and collusion can be sustained as an equilibrium (given patient firms). - If P ≠ NP (together with a natural “instance-hardness” condition on demand), detection and enforcement are infeasible, punishment threats are non‑credible, and competition generically prevails. Combined with Maymin (2011) (which shows price efficiency ⇔ P = NP), this yields an “Efficiency–Competition Impossibility”: markets can be informationally efficient or competitive, but not both. The paper draws policy and empirical implications for AI: as firms acquire greater computational power (via AI), markets are pushed toward the collusive regime, explaining algorithmic collusion even without explicit coordination.

Key Points

• Formal model: repeated imperfect-monitoring price game with N firms, K products, a large discrete set of demand states Θ, and i.i.d. noise in quantities. Firms observe prices and quantities but not underlying demand state.
• Three collusion-related decision problems are defined:
  • CSP (Collusion Strategy Problem): exists a price vector achieving target joint profit? — NP-hard (reduction from MAX-WEIGHTED-SAT).
  • CDP (Collusion Detection Problem): given observed (p,q) and a prescribed collusive strategy σ(·), is there a demand state/noise consistent with no deviation? — NP-hard (reduction from 3-SAT).
  • OPP (Optimal Punishment Problem): can non-deviators select punishment strategies guaranteeing deviator’s payoff below a bound? — NP-hard (reduction from MINIMUM VERTEX COVER).
• Competitive best-response (CBR) is in P under standard regularity (differentiable demand, convex costs): CBR reduces to convex optimization over a firm’s own prices and only requires expected demand.
• Main theorem (informal): under the folk-theorem logic for repeated games,
  • P = NP ⇒ collusion can be sustained in equilibrium (firms can compute strategy, detect deviations, compute punishments).
  • P ≠ NP + instance-hardness of detection ⇒ collusion collapses; firms revert to competitive best responses.
• Assumption 6 (Instance Hardness): stronger than P ≠ NP; requires that the specific demand instances that arise are hard, but argued to be generically satisfied except on special low‑dimension algebraic varieties (separability, low rank, sparsity).
• Additional conceptual results:
  • AI transition: as firms’ computational power increases, markets move through regimes (competitive → unstable → collusive) as computational thresholds are crossed.
  • Transparency paradox: greater market transparency can reduce detection cost and therefore facilitate collusion.
  • Policy proposal: “computational antitrust” — consider market computational structure as a policy/design lever.

Data & Methods

• This is a theoretical/computational-economics paper (no primary empirical dataset). Methods include:
  • Game-theoretic model: repeated games with imperfect public monitoring; collusive outcome defined as joint profit maximizer; competitive outcome as stage-game Nash.
  • Complexity-theoretic reductions: NP-hardness proofs for CSP, CDP, and OPP by reductions from canonical NP-hard problems (MAX-WEIGHTED-SAT, 3-SAT, MINIMUM VERTEX COVER). Constructions exploit compact specification of a large state space Θ.
  • Algorithmic/optimization argument: CBR is solvable in polynomial time because it is a convex optimization (under standard assumptions), requiring only expected-demand objects.
  • Use of the folk theorem: ties computational solvability to equilibrium sustainability in repeated games with sufficiently patient players.
  • A “generic hardness” argument: the set of demand-parameter vectors that make CDP easy lies in a lower-dimensional algebraic variety (measure zero), so generic demand parametrizations render CDP instance-hard.
• Model assumptions and caveats emphasized:
  • Richness: |Θ| ≥ NK + 1 so price-quantity data does not uniquely identify demand state.
  • Noise in quantities (ε) makes inference nontrivial.
  • Assumption 6 (instance-hardness) is plausible but not proven for every realistic market; it is the key bridge from NP-hardness existence to generic infeasibility.
  • Equilibrium conclusions are conditional on standard repeated-game logic (sufficiently high discounting/patience and availability of/publicity of signals).

Implications for AI Economics

• Mechanism: AI (LLMs, RL agents, algorithmic pricing) increases firms’ effective computational power, making previously intractable collusion problems tractable — so algorithmic capability can shift markets from competitive to collusive regimes even absent explicit communication or agreements.
• Empirical predictions and fit: explains experimental and field findings where pricing/trading algorithms learn tacit collusion (e.g., Calvano et al. 2020; Fish et al. 2024; Dou et al. 2025; Assad et al. 2024).
• Policy implications:
  • Computational antitrust: regulators should treat computational capacity and market-combinatorial structure as policy variables. Possible interventions include constraining algorithmic pricing features, imposing randomized pricing, limiting real-time access to high‑resolution demand data, or requiring auditability/interpretability of pricing algorithms.
  • Transparency tradeoffs: policies promoting transparency as pro‑competitive may backfire by lowering the computational cost of deviation detection; regulators should weigh this “transparency paradox.”
  • Design of markets: increasing structural complexity (combinatorial demand interactions) can be a natural competitive safeguard; market design choices (product granularity, information disclosure rules) matter for computational feasibility of collusion.
• Research directions: quantify thresholds of computational power that trigger regime shifts; study heterogeneous computational endowments across firms; analyze approximate/heuristic collusion when exact solutions are infeasible; empirical identification of instance-hardness in real demand systems.
• Caution: main results are conditioned on computational-complexity conjectures and a genericity assumption about demand instances. Theoretical conclusions give a crisp framework to analyze algorithmic collusion risk, but concrete regulatory prescriptions require empirical work to map real markets to the model’s hardness regime.