Study Links Market Competition to Computational Complexity
5 reported
A new paper by Philip Z. Maymin argues that whether markets are competitive depends on the solution to the computational problem P vs. NP. The paper states that if P = NP, firms can efficiently solve a collusion detection problem, making collusion sustainable. If P != NP, the paper claims collusion detection is computationally infeasible for markets with a certain demand structure, making collusion unstable. Combined with Maymin’s 2011 proof that market efficiency requires P = NP, the paper concludes that markets cannot be both informationally efficient and competitive. The paper also suggests that artificial intelligence, by expanding firms’ computational capabilities, is pushing markets from competitive toward collusive outcomes.
What’s reported
The paper claims competitive market outcomes require computational intractability.
If P = NP, firms can efficiently solve the collusion detection problem, making collusion sustainable.
If P != NP, the collusion detection problem is computationally infeasible for markets satisfying a natural instance-hardness condition on their demand structure.
Combined with Maymin (2011), who proved market efficiency requires P = NP, the paper states an impossibility: markets can be informationally efficient or competitive, but not both.
The paper states that artificial intelligence is pushing markets from the competitive regime toward the collusive regime.
Key figures
Philip Z. Maymin, author of the paper and of a 2011 proof cited in the paper.
Sources: marginalrevolution.com
