Markets are competitive if and only if P = NP
I prove that competitive market outcomes require computational intractability. If P = 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 P != 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 Maymin (2011), who proved that market efficiency requires P = 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.
Opening excerpt (first ~120 words) tap to expand
Computer Science > Computer Science and Game Theory arXiv:2602.20415 (cs) [Submitted on 23 Feb 2026] Title:Markets are competitive if and only if P != NP Authors:Philip Z. Maymin View a PDF of the paper titled Markets are competitive if and only if P != NP, by Philip Z. Maymin View PDF Abstract:I prove that competitive market outcomes require computational intractability. If P = 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.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at arXiv.org.
Discussion
0 commentsMore from arXiv.org
