New Proof Ties Market Competition to P vs NP — and Warns AI May Kill It

A newly posted arXiv paper argues that competition in markets depends on a hard computational limit. The core claim: sustaining collusion requires firms to detect when a rival has cheated on a cooperative arrangement, and that detection is really a computational problem. If P = NP, firms could solve it efficiently, reliably spotting defections in noisy, complex markets — which makes punishment credible and turns collusion into a stable equilibrium. If P != NP, the same detection problem becomes intractable for markets meeting a natural hardness condition on demand, so punishment threats ring hollow and collusion falls apart. In that framing, genuine competition exists only because the math is too hard to police a cartel.

The author pairs this with Maymin’s 2011 result that informational market efficiency requires P = NP, and draws out the uncomfortable corollary: a market can be efficient or competitive, but not both simultaneously. The two properties sit on opposite sides of the same complexity boundary, making the trade-off a structural impossibility rather than a policy choice.

The security-relevant twist is the role of AI. By dramatically expanding firms’ effective compute, machine-learning pricing and monitoring tools push markets toward the regime where defection detection becomes tractable — nudging them from competition toward collusion. The paper offers this as a theoretical explanation for the documented rise of algorithmic collusion, where pricing agents converge on supra-competitive outcomes without any explicit agreement between them. Whether the specific hardness assumptions hold in real demand structures is where the argument will be contested.