Markets are competitive if and only if P \(\neq\) NP
February 23, 2026
Abstract
I prove that competitive market outcomes require computational intractability. If \(\mathrm{P}= \mathrm{NP}\), firms can efficiently solve the collusion detection problem, identifying deviations from cooperative agreements in complex, noisy markets and thereby making collusion sustainable as an equilibrium. If \(\mathrm{P}\neq \mathrm{NP}\), the collusion detection problem is computationally infeasible for markets satisfying a natural instance-hardness condition on their demand structure, rendering punishment threats non-credible and collusion unstable. Combined with [1], who proved that market efficiency requires \(\mathrm{P}= \mathrm{NP}\), this yields a fundamental impossibility: markets can be informationally efficient or competitive, but not both. Artificial intelligence, by expanding firms’ computational capabilities, is pushing markets from the competitive regime toward the collusive regime, explaining the empirical emergence of algorithmic collusion without explicit coordination.
1 Introduction↩︎
What maintains competition in markets? The standard answer invokes institutions: antitrust law, regulatory oversight, and low barriers to entry. This paper proposes a more fundamental answer: computational limitations. Competition persists because firms lack the computational power to sustain collusion.
This claim rests on a formal connection between computational complexity and market structure. I prove that if \(\mathrm{P}= \mathrm{NP}\), collusion is sustainable as an equilibrium, and that if \(\mathrm{P}\neq \mathrm{NP}\), collusion is unsustainable for markets whose detection problem is hard on the instances that naturally arise. Since \(\mathrm{P}\neq \mathrm{NP}\) is the widely believed (but unproven) conjecture that some problems whose solutions are easy to verify are hard to solve, the prediction is that competition is the generic outcome in sufficiently complex markets.
The result is the companion and mirror of [1], which established that markets are informationally efficient if and only if \(\mathrm{P}= \mathrm{NP}\). That paper showed that price efficiency requires superhuman computation: only agents who can solve NP-hard problems can eliminate arbitrage opportunities, ensuring that prices reflect all available information. The present paper shows that the same computational power that would make markets efficient also makes them collusive. Together, the two results yield:
Efficiency–Competition Impossibility. Markets can be informationally efficient or competitive, but not both.
This impossibility theorem has immediate implications for artificial intelligence. AI systems (large language models, reinforcement learning agents, algorithmic pricing engines) are expanding firms’ effective computational capabilities. If the computational boundary between competition and collusion is the key regime boundary, then AI moves markets from competitive toward collusive.
Recent empirical evidence supports this prediction. [2] demonstrate that off-the-shelf large language models autonomously converge to supra-competitive pricing without any explicit collusion instructions. [3] show that Q-learning pricing algorithms independently learn to collude, sustaining prices above the Nash equilibrium through reward-punishment schemes. [4] find that AI-powered trading agents learn to coordinate in financial markets, undermining liquidity and price efficiency. In each case, collusion emerges not from intent or communication, but from computational capability, as the theory predicts.
The formal argument proceeds as follows. I define a market game in which \(N\) firms compete over \(T\) periods, facing stochastic demand subject to shocks drawn from a rich combinatorial space. A collusive agreement specifies the joint profit-maximizing strategy conditional on the state of demand. Sustaining such an agreement requires solving three computational problems:
The Collusion Strategy Problem: computing the joint profit-maximizing price vector across a combinatorial product space.
The Collusion Detection Problem: given observed market data, determining whether any firm deviated from the agreed-upon strategy or merely responded to a demand shock.
The Optimal Punishment Problem: computing the punishment strategy that makes deviation unprofitable.
I show that each of these problems is NP-hard for general market games (Theorems 1–3). In contrast, the competitive best-response problem (computing a firm’s optimal myopic response to current market conditions) is solvable in polynomial time for standard demand structures (Proposition 4).
The main theorem (Theorem 5) follows from these complexity results combined with the folk theorem for repeated games. If \(\mathrm{P}= \mathrm{NP}\), firms can solve all three collusion problems efficiently, making collusion sustainable as an equilibrium that Pareto-dominates competition (from the firms’ perspective). If \(\mathrm{P}\neq \mathrm{NP}\) and the market’s detection problem is hard on the instances that actually arise (a condition I formalize as Assumption 6 and argue holds generically), punishment threats are non-credible and firms rationally defect to the competitive best response.
The paper makes several contributions beyond the main theorem. First, I characterize the AI transition: as firms adopt AI systems with increasing computational power, markets pass through three regimes (competitive, unstable, and collusive) as computational thresholds are crossed (Section 5.1). Second, I derive a transparency paradox: increasing market transparency, conventionally viewed as pro-competitive, actually facilitates collusion by reducing the computational cost of deviation detection (Corollary 2). Third, I propose computational antitrust: the principle that market complexity itself is a competitive safeguard, and that regulators should consider computational difficulty as a design parameter (Section 7).
The remainder of the paper is organized as follows. Section 2 situates the paper in the literature. Section 3 defines the model. Section 4 presents the main results. Section 5 develops extensions including the AI transition, heterogeneous computation, and approximate collusion. Section 6 discusses empirical implications. Section 7 addresses policy. Section 8 discusses the relationship to the original P = NP result and limitations. Section 9 concludes.
2 Related literature↩︎
This paper bridges three literatures: computational complexity in economics, the theory of collusion, and the emerging literature on algorithmic collusion.
Computational complexity and markets.
[5] argued that the price system serves as a mechanism for communicating dispersed information, a function that presupposes computational limitations on centralized alternatives. The foundational observation that computational constraints shape economic outcomes traces to [6], who argued that bounded rationality, not full rationality, describes actual decision-making. [7] formalized bounded rationality using automata, showing that the complexity of strategies affects equilibrium outcomes in repeated games; [8] proved that bounding strategy complexity justifies cooperation in finitely repeated games that would otherwise unravel by backward induction; [9] extended this to characterize Nash equilibria when players are modeled as finite automata. [10] introduced the study of computational complexity of equilibrium concepts, establishing that computing Nash equilibria is \(\mathrm{PPAD}\)-complete [11], [12]. [13] articulated the principle of computational irreducibility: many systems cannot be shortcut by any algorithm and must be “run” to determine their outcome. [14] showed that finding Nash equilibria in three-player infinitely repeated games is itself computationally intractable, undermining the folk theorem’s constructive power when players face complexity constraints. [15] demonstrated that computational complexity creates exploitable information asymmetry in financial products: the NP-hardness of detecting manipulated assets means computationally bounded buyers cannot distinguish lemons from sound securities. [1] proved the equivalence between market efficiency and \(\mathrm{P}= \mathrm{NP}\), establishing that informationally efficient prices require computationally unbounded agents. [16], in a chapter they titled “A Beautiful Theorem,” showed that, as a consequence of Maymin’s theorem, “almost efficient” markets exist when the \(\mathrm{P}\neq \mathrm{NP}\) proof has sufficient metamathematical strength, with information accessible in almost-polynomial time. [17] formalized this in a journal setting; [18] extended the analysis with additional algorithms. [19] proved a complementary impossibility using Gödelian incompleteness: a free market cannot be complete. [20] developed a general game-theoretic framework in which players choose Turing machines and pay for computation, showing that classical equilibrium results may fail when computation is costly. The present paper extends this program to competition, showing that the same complexity boundary separates collusive from competitive markets.
Theory of collusion.
The folk theorem [21]–[23] establishes that collusion can be sustained as an equilibrium in repeated games with sufficiently patient players. [24] and [25] study collusion under imperfect monitoring, showing that maintaining cooperation requires the ability to detect and punish deviations. [26] famously argued that the “chief difficulty” of collusion is detecting “secret price-cutting.” The present paper formalizes Stigler’s insight: secret price-cutting is hard to detect not merely because information is scarce, but because the computational problem of distinguishing deviations from demand shocks is NP-hard.
Algorithmic collusion.
[27] first warned that pricing algorithms could facilitate “tacit” collusion without explicit communication. [3] provided the first experimental evidence that Q-learning agents autonomously learn collusive pricing. [28] document supra-competitive pricing in German retail gasoline markets following the adoption of algorithmic pricing. [2] show that large language models reach collusive outcomes without being instructed to collude. [4] extend the evidence to financial markets. [29] analyzes the legal challenges posed by algorithmic collusion. This paper provides the theoretical foundation explaining why algorithmic collusion emerges: it is a computational phase transition, not a failure of competition law.
Mechanism design and market structure.
[30], [31] established that the design of economic mechanisms affects outcomes, work recognized by the Nobel Prize to [30], [32], and [33]. [34] and [35] applied mechanism design to practical market design problems. The policy implications of the present paper extend this tradition: if computational complexity maintains competition, then the computational structure of markets is a design variable that regulators can and should manipulate.
3 Model↩︎
3.1 The market game↩︎
Consider an industry with \(N \geq 2\) firms, indexed by \(i \in \{1, \ldots, N\}\). Firms compete over \(T\) discrete periods, \(t \in \{1, \ldots, T\}\), where \(T\) may be finite (with \(T\) sufficiently large) or infinite with common discount factor \(\delta \in (0,1)\).
Assumption 1 (Product Space). Each firm \(i\) sells \(K\) distinct products. No two firms sell the same product, so the market contains \(NK\) products in total. Firm \(i\)’s strategy in period \(t\) is a price vector \(p_i^t \in \mathbb{R}_+^K\).
Assumption 2 (Demand Structure). In each period \(t\), a demand state \(\theta^t \in \Theta\) is drawn from a distribution \(F\) on a finite state space \(\Theta\) with \(|\Theta| = M\). The demand for firm \(i\)’s product \(k\) is \[q_{ik}^t = D_{ik}(p^t, \theta^t) + \varepsilon_{ik}^t, \label{eq:demand}\tag{1}\] where \(p^t = (p_1^t, \ldots, p_N^t)\) is the vector of all prices, \(D_{ik}\) is the deterministic demand function, and \(\varepsilon_{ik}^t\) is an i.i.d.noise term with mean zero and variance \(\sigma^2 > 0\).
Assumption 3 (Information). The demand state \(\theta^t\) is not directly observed by any firm. After each period, all firms observe the realized prices \(p^t\) and quantities \(q^t = (q_{ik}^t)_{i,k}\).
Assumption 4 (Richness). The demand state space is rich relative to the price space: \(|\Theta| = M \geq NK + 1\). This ensures that observed price-quantity data does not uniquely identify the demand state, so that the inference problem in the Collusion Detection Problem is non-trivial.
Assumption 5 (Costs). Firm \(i\) has a cost function \(C_i: \mathbb{R}_+^K \to \mathbb{R}_+\) that is convex and computable in polynomial time. Firm \(i\)’s period profit is \[\pi_i^t = \sum_{k=1}^{K} p_{ik}^t \cdot q_{ik}^t - C_i(q_i^t). \label{eq:profit}\tag{2}\]
Assumption 6 (Instance Hardness). For the family of market games \(\{\Gamma_n\}\) with \(|\Gamma_n| = n\), the Collusion Detection Problem is hard on the instances induced by the market’s demand structure. Formally, for every probabilistic polynomial-time algorithm \(\mathcal{A}\), \[\Pr_{\theta \sim F,\, \varepsilon}\!\left[\mathcal{A} \text{ correctly solves } \text{CDP}(\Gamma_n, \sigma, p^t, q^t)\right] \leq \frac{1}{2} + \nu(n),\] where \(\nu(n)\) is negligible (i.e.,\(\nu(n) = o(n^{-c})\) for every \(c > 0\)).
Remark 1. Assumption 6 is strictly stronger than \(\mathrm{P}\neq \mathrm{NP}\) but is generically satisfied. NP-hardness (Theorem 2 below) guarantees the existence of hard CDP instances; Assumption 6 requires that the market under study is not among the easy ones. This fails only when the demand structure imposes special algebraic structure (separability, low rank, or sparsity) that renders the inference problem tractable. More precisely, parameterize the demand function by a vector \(\phi \in \mathbb{R}^d\) specifying all cross-product demand coefficients. The reduction in Theorem 2 shows that for an open set of \(\phi\) values, the CDP encodes a 3-SAT instance. The set of \(\phi\) for which CDP admits a polynomial-time solution is contained in an algebraic variety of lower dimension (the locus where demand interactions degenerate to a separable or low-rank structure), which has Lebesgue measure zero in \(\mathbb{R}^d\) whenever \(\mathrm{P}\neq \mathrm{NP}\). Thus Assumption 6 holds for generic demand parameters. We conjecture that separability, low rank, and sparsity exhaust the structural sources of polynomial-time tractability for CDP, though we do not prove this; the assumption is analogous to standard cryptographic practice, where one assumes a specific problem instance is hard without a complete characterization of all easy instances.
The game \(\Gamma = \Gamma(N, K, \Theta, T, \delta, D, F, C)\) is a repeated game of imperfect monitoring. The game is specified in compact form: the demand function \(D\) is given as a polynomial-time computable function (not an explicit table), the distribution \(F\) as a sampling oracle, and the cost functions \(C_i\) as polynomial-time computable functions. The description size of the game, denoted \(|\Gamma|\), is the number of bits required for this compact specification. The state space \(\Theta\) may have cardinality exponential in \(|\Gamma|\): if \(\theta\) encodes the joint realization of \(n\) independent binary demand shifters, then \(|\Theta| = 2^n\) while \(|\Gamma| = \text{poly}(n, N, K)\).
Definition 1 (Competitive Outcome). The competitive outcome (or stage-game Nash equilibrium) is the price vector \(p^* = (p_1^*, \ldots, p_N^*)\) satisfying, for each firm \(i\), \[p_i^* \in \mathop{\mathrm{arg\,max}}_{p_i \in \mathbb{R}_+^K} \; \mathbb{E}_\theta\!\left[\pi_i(p_i, p_{-i}^*, \theta)\right]. \label{eq:competitive}\tag{3}\] Under standard regularity conditions (continuous demand, convex costs), this yields marginal-cost pricing in Bertrand competition and the Cournot equilibrium in quantity competition.
Definition 2 (Collusive Outcome). The collusive outcome is the price vector \(p^M = (p_1^M, \ldots, p_N^M)\) that maximizes joint expected profits: \[p^M \in \mathop{\mathrm{arg\,max}}_{p \in \mathbb{R}_+^{NK}} \; \mathbb{E}_\theta\!\left[\sum_{i=1}^{N} \pi_i(p, \theta)\right]. \label{eq:collusive}\tag{4}\] Under standard assumptions, joint profit maximization yields the monopoly outcome, with \(\sum_i \pi_i(p^M) > \sum_i \pi_i(p^*)\).
3.2 Computational problems of collusion↩︎
Sustaining collusion in a repeated game requires solving three interrelated computational problems. I formalize each as a decision problem. In what follows, a collusive strategy profile \(\sigma: \Theta \to \mathbb{R}_+^{NK}\) is a mapping from demand states to price vectors specifying each firm’s price for each product; I write \(\sigma_i(\theta) \in \mathbb{R}_+^K\) for firm \(i\)’s component. Under \(\sigma\), firms condition their prices on the realized demand state to maximize joint profits.
Definition 3 (Collusion Strategy Problem (CSP)). Instance: A market game \(\Gamma\) and a target joint profit level \(\Pi^*\).
Question: Does there exist a price vector \(p\) such that \(\mathbb{E}_\theta[\sum_i \pi_i(p, \theta)] \geq \Pi^*\)?
Definition 4 (Collusion Detection Problem (CDP)). Instance: A market game \(\Gamma\), a collusive strategy profile \(\sigma: \Theta \to
\mathbb{R}_+^{NK}\), observed prices \(p^t\), and observed quantities \(q^t\).
Question: Does there exist a demand state \(\theta \in \Theta\) and noise realization \(\varepsilon\) consistent with \((p^t,
q^t)\) such that \(p^t = \sigma(\theta)\)? (If yes, no deviation occurred; if no, some firm deviated.)
Definition 5 (Optimal Punishment Problem (OPP)). Instance: A market game \(\Gamma\), a deviating firm \(i\), a collusive strategy \(\sigma\), and a target payoff bound \(\bar{\pi}\).
Question: Does there exist a punishment strategy profile \(\sigma^P_{-i}\) for the non-deviating firms such that firm \(i\)’s best-response payoff under \(\sigma^P_{-i}\) satisfies \(\pi_i^{BR}(\sigma^P_{-i}) \leq \bar{\pi}\)?
3.3 The competitive best-response problem↩︎
In contrast to the collusion problems, the myopic best-response problem is computationally simple.
Definition 6 (Competitive Best-Response Problem (CBR)). Instance: A market game \(\Gamma\), a firm \(i\), and competitors’ current prices
\(p_{-i}\).
Output: The price vector \(p_i^* \in \mathop{\mathrm{arg\,max}}_{p_i} \mathbb{E}_\theta[\pi_i(p_i, p_{-i}, \theta)]\).
3.4 Illustrative example: two firms, two products↩︎
Before presenting the general results, I illustrate the core mechanism with a simple example.
Example 1 (Duopoly with Binary Demand). Consider two firms (\(N = 2\)), each selling one product (\(K = 1\)), with two equally likely demand states (\(M = 2\)): \(\theta_H\) (high demand) and \(\theta_L\) (low demand). Marginal cost is \(c = 1\) for both firms. Demand is \(q_i = a(\theta) - p_i + \beta p_j + \varepsilon_i\), where \(a(\theta_H) = 10\), \(a(\theta_L) = 4\), \(\beta = 0.5\), and \(\varepsilon_i \sim N(0, \sigma^2)\).
Competitive outcome. Each firm’s best response yields \(p^* \approx 5\) (in \(\theta_H\)) and \(p^* \approx 2.5\) (in \(\theta_L\)), with expected profit \(\pi^* \approx 12.5\).
Collusive outcome. Joint profit maximization yields \(p^M \approx 7\) (in \(\theta_H\)) and \(p^M \approx 4\) (in \(\theta_L\)), with expected profit \(\pi^M \approx 22.5\) per firm.
The detection problem. Suppose Firm 1 observes that Firm 2 set \(p_2 = 5.5\). Under the collusive agreement, Firm 2 should have set either \(p_2 = 7\) (if \(\theta_H\)) or \(p_2 = 4\) (if \(\theta_L\)). The price \(5.5\) is inconsistent with both, if Firm 1 knows the demand state. But Firm 1 does not observe \(\theta\) directly; it only observes prices and noisy quantities. With high noise (\(\sigma^2\) large), many price-quantity combinations are consistent with either demand state, and distinguishing a deviation from a demand shock becomes a combinatorial inference problem. In this simple two-firm example, detection is easy. But as we add products, firms, and demand states, the detection problem grows combinatorially, and I show below that it becomes NP-hard in general.
4 Main results↩︎
4.1 Complexity of the collusion problems↩︎
I first establish that each collusion problem is computationally hard.
Theorem 1 (CSP is NP-hard). The Collusion Strategy Problem is NP-hard.
Proof. By reduction from Max-Weighted-SAT. Given an instance of Max-Weighted-SAT with Boolean variables \(x_1, \ldots, x_n\) and weighted clauses \(C_1, \ldots, C_m\), construct a market game as follows. For each variable \(x_j\), create a product with binary pricing: \(p_j \in \{0, 1\}\), interpreted as setting the variable to false or true. For each clause \(C_l\) with weight \(w_l\), define a demand state \(\theta_l\) in which demand is positive (yielding profit \(w_l\)) if and only if the price vector satisfies clause \(C_l\). The demand distribution places equal probability on each demand state. Then the joint expected profit under price vector \(p\) equals \((1/m) \sum_{l: C_l \text{ satisfied by } p} w_l\), which is maximized if and only if the weighted satisfiability is maximized. Since Max-Weighted-SAT is NP-hard [36], so is CSP. ◻
Theorem 2 (CDP is NP-hard). The Collusion Detection Problem is NP-hard.
Proof. By reduction from 3-SAT. Given a 3-SAT instance \(\varphi\) with Boolean variables \(x_1, \ldots, x_n\) and clauses \(C_1, \ldots, C_m\), construct a market game in compact form as follows. Create \(N = m\) firms (one per clause), each selling one product (\(K = 1\)). The demand state space is \(\Theta = \{0,1\}^n\), encoding all truth assignments to the \(n\) variables; note that \(|\Theta| = 2^n\) while the game description is polynomial in \(n + m\). The collusive strategy is a pooling strategy: all firms set a common price \(p^*\) regardless of \(\theta\), so that prices alone reveal nothing about the demand state. The demand function for firm \(j\) (corresponding to clause \(C_j\)) is \[D_j(p, \theta) = \bar{d} + \mathbf{1}[C_j \text{ is satisfied by } \theta],\] where \(\bar{d} > 0\) is a baseline demand level. This is polynomial-time computable: checking whether a clause is satisfied by a given assignment takes \(O(1)\) time.
Suppose all firms comply with the pooling strategy (setting \(p^*\)) and we observe quantities \(q_j = \bar{d} + 1 + \varepsilon_j\) for every firm \(j\), with noise satisfying \(|\varepsilon_j| < 1/2\). To verify consistency with the collusive agreement, we must find a demand state \(\theta \in \{0,1\}^n\) and noise realizations \(\varepsilon\) such that \(q_j = D_j(p^*, \theta) + \varepsilon_j\) for all \(j\) with \(|\varepsilon_j| < 1/2\). This requires \(D_j(p^*, \theta) = \bar{d} + 1\) for all \(j\), i.e., every clause \(C_j\) must be satisfied by \(\theta\). Hence the CDP instance has answer Yes (no deviation detected) if and only if \(\varphi\) is satisfiable. Since 3-SAT is NP-complete [36], CDP is NP-hard. ◻
Theorem 3 (OPP is NP-hard). The Optimal Punishment Problem is NP-hard.
Proof. By reduction from Minimum Vertex Cover. Given a graph \(G = (V, E)\) with \(|V| = n\), construct a market game with \(N - 1\) punishing firms, each controlling a product corresponding to a vertex \(v \in V\). The deviating firm \(i\) has demand that depends on which punishing firms price aggressively (set \(p_v = 0\), flooding the market) versus passively (set \(p_v\) high). An edge \((u, v) \in E\) represents a complementarity: the deviator’s profit from product pair \((u, v)\) is eliminated only if at least one of \(u, v\) is priced aggressively. The punishing coalition seeks to minimize the deviator’s profit (eliminate profit from all edges) while minimizing their own cost of aggressive pricing (each aggressive price costs the punisher a unit of profit). The optimal punishment thus requires choosing a minimum set of vertices (firms to price aggressively) such that every edge is covered, which is exactly Minimum Vertex Cover. Since Minimum Vertex Cover is NP-hard [36], so is OPP. ◻
Taken together, Theorems 1–3 establish that each component of collusion is computationally hard: planning it (CSP), monitoring it (CDP), and enforcing it (OPP). Sustaining collusion requires all three. In contrast, the competitive best response requires none of them.
Proposition 4 (CBR is in P). Under Assumptions 1–5, if the demand function \(D_{ik}\) is differentiable and the cost function \(C_i\) is convex, then the Competitive Best-Response Problem is solvable in polynomial time.
Proof. Given competitors’ prices \(p_{-i}\), firm \(i\)’s myopic optimization problem is \[\max_{p_i \in \mathbb{R}_+^K} \; \mathbb{E}_\theta\!\left[\sum_{k=1}^K p_{ik} \cdot D_{ik}(p_i, p_{-i}, \theta) - C_i\!\left(D_i(p_i, p_{-i}, \theta)\right)\right].\] Under differentiability of \(D\) and convexity of \(C_i\), this is a convex optimization problem over \(K\) variables (firm \(i\)’s own prices). The key distinction from the collusion problems is that computing the expected profit requires only the aggregate function \(\bar{D}_{ik}(p) = \mathbb{E}_\theta[D_{ik}(p, \theta)]\), which is a known function of prices under standard demand models (linear, logit, CES). The firm does not need to reason about individual demand states; it only needs the expected demand, which is polynomial-time computable from the compact specification. The first-order conditions yield a system of \(K\) equations solvable by interior-point methods in polynomial time [37]. The competitive equilibrium is the fixed point of iterated best responses, which converges in polynomial time under contraction mapping conditions satisfied by standard demand models [38]. ◻
4.2 The main theorem↩︎
Theorem 5 (Main Result). For the market game \(\Gamma\) with \(|\Gamma|\) sufficiently large:
Under Assumptions 1–5, if \(\mathrm{P}= \mathrm{NP}\), collusion is sustainable: there exists a perfect public equilibrium of the repeated game \(\Gamma\) that achieves the collusive outcome \(p^M\) for \(\delta\) sufficiently close to \(1\).
Under Assumptions 1–6, if \(\mathrm{P}\neq \mathrm{NP}\), collusion is unsustainable: there is no perfect public equilibrium achieving \(p^M\), and the market converges to the competitive outcome \(p^*\).
Proof. The proof proceeds in two directions.
Direction 1: \(\mathrm{P}= \mathrm{NP}\) \(\Rightarrow\) Collusion is sustainable.
Suppose \(\mathrm{P}= \mathrm{NP}\). Then:
Strategy computation. Since CSP \(\in\) NP and \(\mathrm{P}= \mathrm{NP}\), firms can compute the joint profit-maximizing price vector \(p^M\) in polynomial time.
Deviation detection. Since CDP \(\in\) NP and \(\mathrm{P}= \mathrm{NP}\), after observing \((p^t, q^t)\), each firm can determine in polynomial time whether the observations are consistent with all firms playing \(\sigma(\theta)\) for some demand state \(\theta\), or whether some firm deviated.
Punishment computation. Since OPP \(\in\) NP and \(\mathrm{P}= \mathrm{NP}\), firms can compute optimal punishment strategies in polynomial time.
Equilibrium construction. Consider the following strategy profile. Each firm plays \(p^M\) in the collusive phase. If a deviation is detected (via the CDP algorithm), all firms switch to the punishment phase computed by the OPP algorithm for \(L\) periods, then return to collusion. By the folk theorem for repeated games with imperfect public monitoring [39], this constitutes a perfect public equilibrium sustaining the collusive outcome provided the discount factor satisfies \[\delta \geq \delta^* \equiv \frac{\pi_i^D - \pi_i^M}{\pi_i^D - \pi_i^P},\] where \(\pi_i^D\) is the one-shot deviation payoff, \(\pi_i^M\) the collusive payoff, and \(\pi_i^P\) the punishment payoff. Since \(\mathrm{P}= \mathrm{NP}\) allows exact computation of the optimal punishment (Step 3), \(\pi_i^P\) is minimized, yielding the smallest possible \(\delta^*\). Note that \(\delta^*\) depends on the payoff structure of the market game but not on \(|\Gamma|\) directly. Under demand structures where the ratio of deviation gains \((\pi_i^D - \pi_i^M)\) to punishment severity \((\pi_i^D - \pi_i^P)\) is uniformly bounded as \(|\Gamma|\) grows (as holds for linear, logit, and CES demand), \(\delta^*\) remains bounded away from \(1\).1
The key step is that credible punishment requires detection. In standard models, detection is assumed to be costless (firms observe noisy signals and can process them). Here, I show that when the signal-extraction problem is computationally hard, detection fails; only \(\mathrm{P}= \mathrm{NP}\) restores it.
Direction 2: \(\mathrm{P}\neq \mathrm{NP}\) \(\Rightarrow\) Collusion is unsustainable.
The argument relies on the following key lemma.
Lemma 1 (Existence of Profitable Undetectable Deviations). Under Assumptions 1–6, for any collusive strategy \(\sigma\), each firm \(i\) has a deviation \(\hat{p}_i \neq \sigma_i(\theta)\) such that:
\(\mathbb{E}[\pi_i(\hat{p}_i, \sigma_{-i}, \theta)] > \mathbb{E}[\pi_i(\sigma_i, \sigma_{-i}, \theta)]\); and
No polynomial-time algorithm can distinguish the observed data \(((\hat{p}_i, p_{-i}^M), q^t)\) from data generated under full compliance, with probability exceeding \(1/2 + \nu(|\Gamma|)\).
Proof. For part (a): since \(p^M\) maximizes joint profits, it is generically not a best response for any individual firm. Each firm can increase its own profit by shading its price toward the competitive best response. Formally, \(\nabla_{p_i} \pi_i(p^M) \neq 0\) generically, so there exists a direction of profitable deviation for firm \(i\).
For part (b): since \(|\Theta| \geq NK + 1\) (Assumption 4), the collusive strategy maps demand states to an \((NK)\)-dimensional price space, and with noise (\(\sigma^2 > 0\)), the observed price-quantity vector lies in a region consistent with multiple demand states. A deviation \(\hat{p}_i\) close to \(\sigma_i(\theta)\) for some \(\theta\) produces data that could plausibly arise under an alternative demand state \(\theta'\) with compliant play. Formally, for any \(\hat{p}_i\) in the convex hull of \(\{\sigma_i(\theta) : \theta \in \Theta\}\), there exist weights \(\lambda(\theta)\) such that \(\hat{p}_i = \sum_\theta \lambda(\theta) \sigma_i(\theta)\). On the quantity side, the noise \(\varepsilon\) (with variance \(\sigma^2 > 0\)) absorbs the discrepancy between the observed quantities and the quantities predicted under any candidate state \(\theta'\): for \(\sigma^2\) sufficiently large, the likelihood ratio between the deviation and any compliant state is bounded, so quantities do not reveal the deviation. Determining whether consistent weights exist is a feasibility problem over the demand state space, which is an instance of CDP for the market game \(\Gamma\). By Assumption 6, this instance cannot be solved in polynomial time with probability exceeding \(1/2 + \nu(|\Gamma|)\). ◻
Suppose \(\mathrm{P}\neq \mathrm{NP}\). Then:
Detection fails. By Assumption 6, no polynomial-time algorithm correctly solves CDP for the market game \(\Gamma\) with probability exceeding \(1/2 + \nu(|\Gamma|)\). (This assumption is non-vacuous precisely when \(\mathrm{P}\neq \mathrm{NP}\); if \(\mathrm{P}= \mathrm{NP}\), all NP problems are solvable in polynomial time and the assumption cannot hold.)
Punishment is not credible. A punishment strategy is credible only if deviations that trigger it are detectable. If firm \(i\) can deviate from \(p^M\) in a way that is computationally indistinguishable from compliance (i.e.,the deviation produces observed data consistent with some demand state under the collusive strategy), then the deviation goes undetected and unpunished.
Profitable undetectable deviations exist. By Lemma 1, each firm has a profitable deviation that is computationally indistinguishable from compliance. The key condition is that the demand state space is rich enough (\(|\Theta| \geq NK + 1\)) that observed data admits multiple consistent explanations, and noise ensures that deviations cannot be detected with certainty from price-quantity data alone.
Collusion unravels. Since profitable, undetectable deviations exist and punishment is non-credible, the repeated game offers no advantage over the stage game: the threat of future punishment cannot discipline current behavior. The unique Nash equilibrium of the stage game is the competitive outcome \(p^*\), which is therefore the only equilibrium of the repeated game.
Convergence to \(p^*\) in part (b). In the stage game, \(p^*\) is the unique Nash equilibrium under Assumptions 1–5 (strict concavity of profit functions and dominant diagonal in the demand system ensure uniqueness). Since collusion is the only alternative equilibrium outcome in the repeated game, and sustaining any supra-competitive outcome requires detection capability that is computationally infeasible under Assumption 6, the collapse of collusion implies convergence to \(p^*\). ◻
4.3 The Efficiency–Competition Impossibility↩︎
Combining the main result with [1] yields a fundamental impossibility.
Corollary 1 (Efficiency–Competition Impossibility). No market can simultaneously be:
Informationally efficient (prices reflect all available information), and
Competitive (prices converge to marginal cost).
Proof. By [1], informational efficiency requires \(\mathrm{P}= \mathrm{NP}\). By Theorem 5(b), under Assumption 6, competition requires \(\mathrm{P}\neq \mathrm{NP}\). Since \(\mathrm{P}= \mathrm{NP}\) and \(\mathrm{P}\neq \mathrm{NP}\) are mutually exclusive, no market satisfying Assumption 6 can be both efficient and competitive. ◻
Remark 2. Corollary 1 can be understood as a computational generalization of the Grossman–Stiglitz paradox [40]. Grossman and Stiglitz showed that if prices are fully informative, no trader has an incentive to acquire costly information, so prices cannot be fully informative, a logical contradiction. The present result is stronger: it shows that the computational requirements for efficiency and competition are not merely in tension but are logically incompatible.
4.4 The Transparency Paradox↩︎
A counterintuitive implication concerns market transparency.
Corollary 2 (Transparency Paradox). Increasing market transparency (making prices, quantities, and transaction-level data more readily available) facilitates collusion by reducing the computational complexity of the Collusion Detection Problem.
Proof. Define the ambiguity set at noise level \(\sigma^2\) as \[\mathcal{A}(\sigma^2) = \left\{\theta \in \Theta : \Pr_\varepsilon\!\left[\|q^t - D(p^t, \theta)\| \leq r(\sigma^2)\right] > \eta \right\},\] the set of demand states consistent with observed data within the noise tolerance \(r(\sigma^2)\), where \(\eta > 0\) is a fixed likelihood threshold. Since the noise \(\varepsilon\) has variance \(\sigma^2\), the tolerance \(r(\sigma^2)\) is increasing in \(\sigma^2\), and the ambiguity set satisfies \(|\mathcal{A}(\sigma_1^2)| \leq |\mathcal{A}(\sigma_2^2)|\) whenever \(\sigma_1^2 \leq \sigma_2^2\): higher precision shrinks the set of consistent states.
The computational difficulty of CDP is determined by the search over \(\mathcal{A}(\sigma^2)\). When \(|\mathcal{A}(\sigma^2)| = 1\), the demand state is uniquely identified, deviations are immediately visible, and CDP is trivially solvable. When \(|\mathcal{A}(\sigma^2)| = M = |\Theta|\), all demand states remain consistent, and CDP requires searching the full state space, which is hard under Assumption 6. Increasing transparency (decreasing \(\sigma^2\)) monotonically reduces \(|\mathcal{A}(\sigma^2)|\) and hence the difficulty of CDP, weakening Assumption 6 and facilitating collusion. ◻
Remark 3. This result challenges the conventional regulatory wisdom that transparency promotes competition. The European Commission’s push for algorithmic transparency, the SEC’s emphasis on trade reporting, and real-time pricing mandates may inadvertently facilitate the very collusion they seek to prevent. The mechanism is computational: transparency reduces the information-processing burden that currently prevents firms from monitoring each other’s compliance with tacit agreements.
5 Extensions↩︎
5.1 The AI transition↩︎
In practice, firms do not jump discontinuously from \(\mathrm{P}\neq \mathrm{NP}\) to \(\mathrm{P}= \mathrm{NP}\). AI systems expand computational capabilities gradually. I model this as firms having access to algorithms that solve problems of size up to \(s\), where \(s\) grows with AI capability (see Figure 1).
Definition 7 (Computational Capacity). Firm \(i\) has computational capacity \(s_i \in \mathbb{N}\), meaning it can solve any instance of CDP (and CSP, OPP) of size at most \(s_i\) in unit time. For instances of size \(|\Gamma| > s_i\), the firm cannot solve the problem.
Proposition 6 (Regime Shifts). As the minimum computational capacity \(\underline{s} = \min_i s_i\) increases, the market passes through three regimes:
Competitive regime (\(\underline{s} < s^*\)): No firm can solve CDP for the actual market. Collusion is unsustainable. Prices converge to \(p^*\).
Unstable regime (\(s^* \leq \underline{s} < s^{**}\)): Some firms can partially solve CDP. Collusion is intermittent, with price wars triggered by detection failures. Market outcomes oscillate between \(p^*\) and \(p^M\).
Collusive regime (\(\underline{s} \geq s^{**}\)): All firms can solve CDP for the actual market. Collusion is sustainable. Prices converge to \(p^M\).
The thresholds \(s^*\) and \(s^{**}\) depend on market complexity \(|\Gamma|\).
Proof. When \(\underline{s} < s^*\), no firm can detect deviations, and the argument of Direction 2 in Theorem 5 applies. When \(\underline{s} \geq s^{**}\), all firms can detect deviations, and Direction 1 applies. The intermediate regime follows from partial detection: firms can detect “large” deviations but not “small” ones, leading to a mixed equilibrium where firms occasionally test the boundaries of detection capability, triggering punishment phases. ◻
Remark 4. The AI transition is currently underway. Algorithmic pricing systems process millions of price points in real time, effectively solving CDP for simple markets (few products, stable demand). As AI systems grow more capable, the computational threshold \(s^*\) is being crossed in progressively more complex markets. The empirical evidence of algorithmic collusion [2], [3], [28] corresponds to early instances of this phase transition.
5.2 Heterogeneous computational capabilities↩︎
When firms differ in computational capacity, asymmetric outcomes emerge.
Proposition 7 (Asymmetric AI Adoption). Suppose firms \(1, \ldots, n\) have computational capacity \(s_i \geq s^{**}\) (“AI firms”) and firms \(n+1, \ldots, N\) have capacity \(s_j < s^*\) (“traditional firms”). Then:
AI firms can collude among themselves, sustaining supra-competitive prices in the products they sell.
Traditional firms cannot sustain collusion and price competitively.
The market equilibrium involves a two-tier pricing structure: AI firms earn monopoly rents while traditional firms earn competitive returns.
AI firms have a strategic incentive to increase market complexity (product differentiation, dynamic pricing) beyond the detection capacity of traditional firms, widening the computational gap.
Proof. Parts (a)–(c) follow from Theorem 5 applied separately to the AI-firm subgame and the traditional-firm subgame. AI firms with \(s_i \geq s^{**}\) can solve CDP for the market among themselves, so Direction 1 of Theorem 5 applies to their sub-coalition: collusion is sustainable. Traditional firms with \(s_j < s^*\) cannot solve CDP, so Direction 2 applies: their collusion unravels. The two-tier structure follows from the resulting equilibrium: AI firms price at \(p^M\) among themselves while traditional firms price at \(p^*\). For part (d), note that AI firms can increase \(|\Gamma|\) by introducing product variants or dynamic pricing schemes. If the resulting complexity exceeds \(s^*\) for traditional firms but not \(s^{**}\) for AI firms, the computational gap widens, reinforcing the two-tier structure. ◻
5.3 Approximate collusion and bounded rationality↩︎
Even if \(\mathrm{P}\neq \mathrm{NP}\), AI systems may approximately solve NP-hard problems using heuristics, achieving near-collusive outcomes.
Definition 8 (\(\alpha\)-Approximate Collusion). An outcome is \(\alpha\)-approximately collusive if joint profits satisfy \(\sum_i \pi_i \geq \alpha \cdot \sum_i \pi_i(p^M)\) for \(\alpha \in (0, 1]\).
Proposition 8 (Approximate Collusion). Suppose firms have access to a polynomial-time probabilistic detection mechanism* \(\mathcal{D}\) that, given observed data \((p^t, q^t)\), correctly classifies deviations from the collusive agreement with probability at least \(\alpha \in (1/2, 1]\). Then for \(\delta\) sufficiently close to \(1\), firms can sustain \(\alpha\)-approximately collusive outcomes as a perfect public equilibrium.*
Proof. Replace exact detection in the equilibrium construction of Theorem 5(a) with the probabilistic mechanism \(\mathcal{D}\). A deviating firm is detected and punished with probability at least \(\alpha\), and escapes detection with probability at most \(1 - \alpha\). The incentive compatibility condition becomes \[\pi_i^M \geq (1 - \alpha)\, \pi_i^D + \alpha\!\left[\pi_i^D + \frac{\delta}{1-\delta}\, \pi_i^P\right] \cdot \frac{1-\delta}{\delta},\] which is satisfied for \(\delta\) sufficiently close to \(1\) whenever \(\alpha > 1/2\). The achievable collusive profit is bounded below by \(\alpha \cdot \sum_i \pi_i(p^M)\) because the imperfect detection limits the severity of credible punishment. The equilibrium construction follows the folk theorem with imperfect public monitoring [39], where the signal structure is determined by \(\mathcal{D}\). ◻
Remark 5. This extension is practically significant. The NP-hardness of exact CDP does not protect competition if approximate detection suffices, and modern AI systems are powerful approximate solvers. Large language models and deep reinforcement learning agents learn effective detection heuristics from market data, achieving \(\alpha\) values well above \(1/2\) in real markets. The competitive boundary is not a knife-edge; it is a gradient that AI is steadily climbing.
6 Empirical implications↩︎
The theory generates several testable predictions.
AI adoption and markups. Industries with higher AI adoption in pricing should exhibit higher markups and lower price dispersion, controlling for concentration and other standard determinants of competition. This is consistent with [28], who find that algorithmic pricing in German gasoline markets increased margins by 9%.
Market complexity and competition. Controlling for AI adoption, markets with greater complexity (more products, more volatile demand, less transparency) should be more competitive, because the CDP is harder to solve. This generates the novel prediction that complexity protects competition: firms in complex markets are harder to monitor, making collusion unsustainable even with AI.
Regime shifts. As AI capabilities increase (measured by model size, inference speed, or data access), markets should exhibit rapid transitions from competitive to collusive pricing as computational thresholds are crossed. These transitions should be detectable as structural breaks in price-cost margin time series.
Transparency and prices. Mandated increases in market transparency (e.g.,real-time price reporting) should lead to higher equilibrium prices, not lower, by facilitating AI-mediated collusion detection. This prediction runs counter to conventional regulatory expectations.
Collusion without communication. AI-mediated collusion should be observable even without any communication between firms: no shared algorithms, no data pooling, no third-party pricing services. The computational capability alone is sufficient. This distinguishes computational collusion from traditional conspiracy, which requires coordination.
Remark 6. Prediction P5 poses a fundamental challenge for antitrust enforcement. If collusion emerges from computational capability rather than communication, then the legal standard requiring evidence of “agreement” or “conspiracy” is structurally inadequate. The theory suggests that antitrust law must shift from prosecuting collusive intent to regulating collusive capacity, a fundamental reorientation of competition policy.
7 Policy implications: computational antitrust↩︎
If computational complexity is what maintains competition, then regulators have a new lever: the computational structure of markets themselves.
7.1 Market complexity as a policy variable↩︎
Traditional competition policy focuses on market structure (number of firms, barriers to entry) and conduct (price-fixing, bid-rigging). The present theory adds a third dimension: market complexity, the computational difficulty of the collusion detection problem as a function of market design.
Definition 9 (Market Complexity Index). The complexity index of a market game \(\Gamma\) is the computational complexity of its associated CDP, measured as the size of the smallest instance for which no polynomial-time algorithm achieves detection accuracy exceeding \(1/2\).
Regulators can increase market complexity through several mechanisms:
Product differentiation incentives. Encouraging product variety and customization increases the dimensionality of the pricing problem, making collusion detection harder.
Demand opacity. Introducing randomness or opacity into demand information (e.g.,stochastic auctions, randomized procurement) increases the noise in observed market data, raising the computational cost of disentangling demand shocks from deviations.
Asynchronous pricing. Requiring staggered pricing updates (rather than simultaneous price changes) breaks the temporal structure that AI systems exploit for real-time detection.
Algorithmic diversity mandates. Requiring firms to use diverse, independently developed pricing algorithms reduces the implicit coordination that arises when similar algorithms converge to similar strategies.
7.2 The Regulatory Trilemma↩︎
The Efficiency–Competition Impossibility (Corollary 1) implies a trilemma for policymakers. They must choose at most two of three desirable market properties:
Efficiency: Prices reflect all available information.
Competition: Prices converge to marginal cost.
AI integration: Firms use computationally powerful AI systems.
With AI integration, markets become efficient (prices quickly incorporate information) but collusive (AI enables detection and punishment). Without AI, markets can be competitive but informationally inefficient. Achieving both efficiency and competition requires limiting AI, at the cost of the productivity gains that AI provides.
This trilemma formalizes the emerging policy tension: governments simultaneously promote AI adoption for economic growth and worry about AI-mediated market manipulation. The theory shows that this tension is not a failure of policy design but a mathematical necessity.
8 Discussion↩︎
8.1 Relationship to the original P = NP result↩︎
[1] established: Efficiency \(\iff\) \(\mathrm{P}= \mathrm{NP}\). The present paper establishes: Competition \(\iff\) \(\mathrm{P}\neq \mathrm{NP}\). Together:
| \(\PP = \NP\) | \(\PP \neq \NP\) | |
|---|---|---|
| Market efficiency | ✔ | \(\times\) |
| Market competition | \(\times\) | ✔ |
Since \(\mathrm{P}\neq \mathrm{NP}\) is widely believed (and most of cryptography, including blockchain and digital signatures, relies on this assumption), the combined prediction is: markets are competitive but not efficient. This is broadly consistent with the empirical evidence: markets exhibit persistent mispricing [41], [42] alongside robust competition in most sectors.
The AI revolution is changing this equilibrium. By pushing the effective computational boundary toward \(\mathrm{P}= \mathrm{NP}\) for market-relevant problems, AI is shifting markets from the bottom-right cell (competitive, inefficient) toward the top-left cell (efficient, collusive). The question for society is whether the efficiency gains are worth the loss of competition.
8.2 Why AI collusion is different from human collusion↩︎
Traditional collusion is fragile because humans face cognitive limitations: bounded memory, emotional responses (anger at defectors, temptation to cheat), and inability to process complex multivariate data in real time. These limitations make the CDP effectively unsolvable for human managers, even in moderately complex markets.
AI agents face none of these limitations. They can:
Process the complete history of price-quantity data in milliseconds.
Detect subtle patterns in competitor behavior across thousands of products.
Compute optimal punishment strategies using reinforcement learning.
Execute punishment with perfect commitment (no emotional forgiveness).
Update strategies at a frequency that prevents human oversight.
The shift from human to AI decision-making is not a quantitative increase in collusion risk; it is a qualitative regime change, a computational phase transition from the competitive to the collusive equilibrium.
8.3 Limitations↩︎
The “only if” direction (Theorem 5(b)) relies on Assumption 6, which requires that the specific market’s CDP instance is hard, not merely that CDP is hard as a problem class. This is a genuine strengthening of \(\mathrm{P}\neq \mathrm{NP}\), and I have argued (Remark 1) that it holds generically. Markets with special algebraic structure in their demand functions (separability, low rank, sparsity) may violate the assumption even when \(\mathrm{P}\neq \mathrm{NP}\), making collusion feasible in those markets. This is consistent with empirical observation: collusion is easier in simple, transparent markets (few products, stable demand) than in complex ones.
The theorem also assumes rational, profit-maximizing firms. If some firms pursue objectives other than profit (e.g.,market share, social responsibility), or if bounded rationality constrains strategy choice beyond computational limitations, the competitive regime may persist longer than the theorem predicts.
A related concern is focal point coordination [43]. Even without solving the CDP formally, firms might sustain partial collusion through simple focal strategies (e.g.,“match the industry leader’s price”). Such strategies do not require NP-hard computation but may sustain above-competitive prices in simple markets. The main theorem addresses this by focusing on sufficiently complex markets where simple focal rules fail: with many products, volatile demand, and heterogeneous costs, there is no obvious focal price, and sustaining collusion requires the full detection-punishment apparatus formalized here.
Finally, the compact representation of the market game (Section 3) means that the state space \(\Theta\) can be exponentially large relative to the description size, which is what makes the CDP hard. In markets where the relevant state space is small or easily enumerable, the NP-hardness results do not bind, and collusion may be feasible by brute-force search. The theorem’s predictive force is for markets of increasing complexity, where the exponential state space makes detection intractable.
9 Conclusion↩︎
This paper proves that competitive market outcomes are sustained by computational limitations. If \(\mathrm{P}= \mathrm{NP}\), collusion is the equilibrium outcome; if \(\mathrm{P}\neq \mathrm{NP}\) and the market’s collusion detection problem is hard on the instances that naturally arise, competition prevails. The result complements and mirrors [1]: informational efficiency requires \(\mathrm{P}= \mathrm{NP}\), while competition requires \(\mathrm{P}\neq \mathrm{NP}\). Together, these results establish a fundamental impossibility: markets cannot be simultaneously efficient and competitive.
Artificial intelligence is pushing markets across this boundary. As AI systems expand firms’ effective computational capabilities, the collusion detection problem that previously exceeded human capacity becomes solvable. The result is a mathematical prediction: sufficiently capable AI agents will sustain collusive outcomes as equilibria, without any explicit coordination or intent.
The implications for competition policy are immediate. Antitrust law built on detecting collusive intent or communication is structurally inadequate for a world in which collusion emerges from computation. The paper proposes computational antitrust: the principle that market complexity is itself a competitive safeguard, and that regulators should design markets to be computationally hard to collude in, just as cryptographers design systems to be computationally hard to break.
Competition, the foundation of market economies since Adam Smith, is not a natural law. It is a consequence of our limitations. As those limitations recede, so may competition. Whether we can design institutions that preserve the benefits of competition in a world of unbounded computation remains to be seen.
References↩︎
Since the game has imperfect public monitoring (demand states are unobserved), the natural solution concept is perfect public equilibrium (PPE) [39] rather than subgame-perfect equilibrium (SPE). The collusive equilibrium constructed here is a PPE. The unsustainability result in Direction 2 holds for the broader class of SPE, making it stronger: collusion fails even if firms condition on private histories.↩︎