Markets are competitive if and only if P != NP
Points and comments are a snapshot, not live.
A new paper proves market competition requires computational intractability via P != NP.
Philip Z. Maymin proves that competitive market outcomes require P != NP, because if P = NP, firms could efficiently detect collusion deviations, making collusion sustainable. If P != NP, collusion detection is infeasible for markets with a natural instance-hardness condition on demand structure. Combined with Maymin (2011) on market efficiency requiring P = NP, this implies markets cannot be both informationally efficient and competitive. AI expanding computational capabilities pushes markets from competitive toward collusive regimes, explaining algorithmic collusion without explicit coordination.
What commenters are saying
Comments highlight that the HN headline misrendered the title, which should read "Markets are competitive if and only if P \u2260 NP." Several commenters critique the paper's assumption that detecting secret price cuts is collusion's main difficulty, arguing that firms often cannot punish defectors even when they know. They note the RealPage rental pricing case involved explicit cartel enforcement, not pure algorithmic collusion. Some question whether increased compute alone causes collusion, suggesting better information flows and communication networks are the real drivers.