[abetusk]

There's a long history of proving results like this.

NP-Completeness is the norm, not the exception. Any system that's complex enough is almost surely NP-Complete. For similar reasons, Turing Machine Equivalence is also the norm, not the exception.

These results are interesting but not unexpected. A more interesting question is under what conditions is the problem difficult to find solutions for. Many NP-Complete instance ensembles turn out to effectively have polynomial time solutions (3-SAT w/ uniform clause variable choice, Hamilton Cycles in Erdos-Renyi random graphs), so proving NP-Completeness is not a death knell for approximation.

[_alternator_]

Right. Maybe a better and more humble title is "Identifying General Instances of Market Collusion is NP-complete". Not as headline grabbing, but more in line with the actual result.