"Computational Complexity and Information Asymmetry in Financial Products," a new paper by Princeton computer scientists and economists Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge suggests that complex financial derivatives are computationally intractable: that is, once you have mixed together a bunch of weird-ass securities and derivatives, you literally can't tell if the resulting security is being tampered with as it pays off (or doesn't). Freedom to Tinker's Andrew Appel likens it to cryptography: you can mix together a bunch of known quantities to get a new number that can't be turned back into the old numbers.
The paper shows the example of a high-volume seller who builds 1000 CDOs from 1000 assert-classes of home mortages. Suppose the seller knows that a few of those asset classes are "lemons" that won't pay off. The seller is supposed to randomly distribute the asset classes into the CDOs; this minimizes the risk for the buyer, because there's only a small chance that any one CDO has more than a few lemons. But the seller can "tamper" with the CDOs by putting most of the lemons in just a few of the CDOs. This has an enormous effect on the senior tranches of those tampered CDOs.
In principle, an alert buyer can detect tampering even if he doesn't know which asset classes are the lemons: he simply examines all 1000 CDOs and looks for a suspicious overrepresentation of some of the asset classes in some of the CDOs. What Arora et al. show is that is an NP-complete problem ("densest subgraph"). This problem is believed to be computationally intractable; thus, even the most alert buyer can't have enough computational power to do the analysis.
Arora et al. show it's even worse than that: even after the buyer has lost a lot of money (because enough mortgages defaulted to devalue his "senior tranche"), he can't prove that that tampering occurred: he can't prove that the distribution of lemons wasn't random. This makes it hard to get recourse in court; it also makes it hard to regulate CDOs.
Intractability of Financial Derivatives
