The paper seems to be based on an invalid assumption. From the abstract:
> If P != NP, the collusion detection problem is computationally infeasible for markets satisfying a natural instance-hardness condition on their demand structure, rendering punishment threats non-credible and collusion unstable.
...and then from the paper:
> Stigler (1964) famously argued that the “chief difficulty” of collusion is detecting “secret price-cutting.”
The thing is that Stigler's insight is far from proven, and indeed, the primary difficulty in collusion is often not the detection of defection. Firms know they're being undercut all the time. The problem is that very often, there is nothing they can do about it. Markets are specifically structured as firm-to-firm transactions, where competing firms have no leverage over what your firm can do or what sort of transactions you can conduct, and as long as this condition holds it doesn't matter if you know that a competitor is fucking you over, you can't do anything about it.
I'd argue that the increase in collusion and anticompetitive behavior lately is because these conditions increasingly don't hold. When you intersperse another party in the transaction, eg. a regulatory agency, permitting body, or exclusive distribution deal, you introduce a leverage point for incumbents to punish competitors who choose to undercut them.