Markets are competitive if and only if P != NP

Paper: arXiv 2602.20415

Authors: 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.

Complexity vs Empirical Score

• Math Complexity: 8.0/10
• Empirical Rigor: 2.5/10
• Quadrant: Lab Rats — theoretically deep, empirically untested

Why this score: The paper provides a highly novel and mathematically sophisticated theoretical bridge between computational complexity theory (P vs NP) and market competition/collusion. However, it is entirely theoretical with minimal empirical rigour, relying instead on citations to third-party studies to motivate its claims about AI and market behavior.

Research Flowchart

  flowchart TD
    A[Research Goal: Relationship Between Market Competition & Computational Complexity] --> B[Input: Market Demand Structure, Noise & Price Signals]
    B --> C[Methodology: Game Theory & Computational Complexity Analysis]
    C --> D{Is P = NP?}
    D -- Yes --> E[Efficient Collusion Detection: Deviations Detected -> Collusion Sustainable]
    D -- No --> F[Collusion Detection Intractable: Punishment Non-Credible -> Markets Competitive]
    E & F --> G[Core Outcome: Markets are Informationally Efficient OR Competitive, But Not Both]
    G --> H[Application: AI Increases Capability, Driving Algorithmic Collusion]