Markets are competitive if and only if P != NP
2026/02/23 by Philip Z. Maymin · 22 voices
#cs.GT #cs.CC #econ.TH #q-fin.CP
paper · 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. 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.
Citations
Discussions
- Markets are competitive if and only if P != NP [hn, 231 points, 164 comments]
- Markets are competitive if and only if P != NP [lobsters, 9 points, 3 comments]
- Okay once in a while theory papers hit hard “[AI], by expanding firms' computational capabilities, is pushing markets from the competitive regime toward the collusive regime, explaining the empirical [bsky, 1 points, 0 comments]
- Both startling and obvious. “markets can be informationally efficient or competitive, but not both” “[AI], by expanding firms' computational capabilities, is pushing markets from the competitive regim [bsky, 0 points, 0 comments]
- Now reading: "Markets are competitive if and only if P̸ != NP" by Philip Z. Maymin https://arxiv.org/pdf/2602.20415 [bsky, 0 points, 0 comments]
- Markets are competitive if and only if P = NP [bsky, 0 points, 0 comments]
- Markets are competitive if and only if P = NP #HackerNews https://arxiv.org/abs/2602.20415 [bsky, 0 points, 0 comments]
- Markets are competitive if and only if P != NP https://arxiv.org/abs/2602.20415 https://news.ycombinator.com/item?id=48776345 [bsky, 0 points, 0 comments]
- Markets are competitive if and only if P = NP https://arxiv.org/abs/2602.20415 https://news.ycombinator.com/item?id=48776345 [bsky, 0 points, 0 comments]
- Markets are competitive if and only if P = NP https://arxiv.org/abs/2602.20415 [bsky, 0 points, 0 comments]
- 📰 Markets are competitive if and only if P != NP 🔗 https://arxiv.org/abs/2602.20415 💬 Discuss on HN [bsky, 0 points, 0 comments]
- 281 A new paper argues competitive markets require P != NP: easy collusion detection would let cartels form. Submit to upvote on HN https://news.ycombinator.com/submitlink?u=https%3A%2F%2Farxiv.org%2F [bsky, 0 points, 0 comments]
- https://bsky.app/profile/news.ycombinator.com.web.brid.gy/post/3mpqzpti3w2m2 [bsky, 0 points, 0 comments]
- Markets are competitive if and only if P != NP https://arxiv.org/abs/2602.20415 (http://news.ycombinator.com/item?id=48776345) [bsky, 0 points, 0 comments]
- evidence arxiv.org/abs/2602.20415 [bsky, 0 points, 1 comments]
- arxiv.org/abs/2602.20415 [bsky, 0 points, 0 comments]
- "Artificial intelligence, by expanding firms' computational capabilities, is pushing markets from the competitive regime toward the collusive regime, explaining the empirical emergence of algorithmic [bsky, 0 points, 0 comments]
- Markets are competitive if and only if P = NP view on hacker news [bsky, 0 points, 0 comments]
- Markets are competitive if and only if P != NP https:// arxiv.org/abs/2602.20415 # arxiv [mastodon, 0 points, 0 comments]
- Markets are competitive if and only if P != NP https://lobste.rs/s/cpzsag #math #finance [bsky, 0 points, 0 comments]
- Markets are competitive if and only if P = NP https://arxiv.org/abs/2602.20415 (https://news.ycombinator.com/item?id=48776345) [bsky, 0 points, 0 comments]
- Markets are competitive if and only if P = NP https://arxiv.org/abs/2602.20415 (https://news.ycombinator.com/item?id=48776345) [bsky, 0 points, 0 comments]
Related