Markets are competitive if and only if P = NP

Computer Science > Computer Science and Game Theory Title:Markets are competitive if and only if P != NP View PDFAbstract: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...