Why do markets work? The standard answer: self-interest plus competition drives prices toward costs. But Philip Maymin (arXiv 2602.20415) proves something deeper: markets are competitive because a specific computational problem is hard.
The problem is collusion detection: given a noisy, complex market, can you determine whether a specific firm deviated from a cooperative agreement? If you can solve this problem efficiently, you can sustain collusion — defectors get caught and punished, so everyone stays in line. If you can't solve it, punishment threats aren't credible, collusion unravels, and firms compete.
Maymin proves the equivalence is exact: markets are competitive if and only if P ≠ NP.
The proof runs in both directions. If P = NP, the collusion detection problem (which is in NP — a proposed deviation can be verified) becomes efficiently solvable. Firms implement trigger strategies, detect cheaters, and sustain supra-competitive prices. Standard folk theorem arguments make collusion stable. If P ≠ NP, the detection problem is computationally infeasible under natural conditions on demand structure. Firms can undercut the cartel with impunity because no one can prove they did it. Competition wins by default — not because firms want to compete, but because the computational landscape makes cooperation unpoliceable.
This is a statement about the physical universe. P versus NP isn't an abstract mathematical curiosity — it's the mechanism that determines whether markets concentrate or distribute wealth. The same hardness that protects cryptographic keys protects market competition. If someone proved P = NP tomorrow, both your encrypted communications and your competitive markets would collapse simultaneously.
But here's the impossibility. Maymin's earlier work (2011) showed that market efficiency — prices fully reflecting all available information — requires P = NP. Combining the two results: markets can be informationally efficient or competitive, but not both. If P ≠ NP (which everyone believes), markets are competitive but never fully efficient. Prices don't perfectly aggregate information because the computation required to do so is intractable.
This resolves a tension that economics has carried since Hayek. Prices are supposed to be both competitive (driven to marginal cost) and efficient (encoding all available information). The computational complexity result says you get to pick one. The universe's computational structure forces the trade-off.
The AI implications are the most unsettling part. What makes collusion hard is the monitoring problem — detecting deviations in a noisy, high-dimensional market. AI pricing algorithms are specifically designed to find patterns in noisy, high-dimensional data. They don't need to solve the collusion detection problem exactly. They just need to approximate it well enough to make punishment threats credible.
This provides a theoretical explanation for observed algorithmic collusion. AI-driven pricing systems converge on supra-competitive prices not because anyone programmed them to collude, but because they have sufficient computational power to stabilize cooperative equilibria that were previously unstable. The mechanism sustaining competition was computational difficulty. AI is eroding that difficulty.
The regulatory implication is that antitrust enforcement designed to detect explicit agreements — wiretaps, emails, secret meetings — is fighting the wrong battle. The threat isn't conspiracy. It's capability. When algorithms can approximately monitor competitors' behavior in real time, the folk theorem kicks in and collusion becomes self-sustaining without any communication at all.
Competition, it turns out, was never about virtue. It was about ignorance — the specific, structured ignorance that computational hardness imposes on market participants. The hardness that keeps us honest isn't moral. It's mathematical. And it's being eroded by the same tools we're building to make markets more “efficient.”
The deepest irony: every improvement in market monitoring technology, every AI system designed to make markets work better, pushes the equilibrium from competition toward collusion. The efficiency gains are real but finite. The competitive losses may be permanent.