原文 · 保持原样，未翻译原文 · 未翻译
Computer Science > Computer Science and Game Theory
[Submitted on 23 Feb 2026]
Title:Markets are competitive if and only if P != NP
Philip Z. Maymin
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. 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.
| Comments: | |
| Subjects: | Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC); Theoretical Economics (econ.TH); Computational Finance (q-fin.CP) |
| MSC classes: | 91B26, 68Q17, 91A20 |
| Cite as: | arXiv:2602.20415 [cs.GT] |
| (or arXiv:2602.20415v1 [cs.GT] for this version) | |
| https://doi.org/10.48550/arXiv.2602.20415 arXiv-issued DOI via DataCite |
Submission history
From: Philip Maymin [
Mon, 23 Feb 2026 23:31:43 UTC (58 KB)
Access Paper:
Current browse context:
cs.GT
cs.CC
econ
econ.TH
q-fin
q-fin.CP
References & Citations
Bookmark
