And the question now is: how will Washington respond?
The title may not make sense - how can scientists (computer scientists, in this case) prove that it's impossible to detect bad assets or regulate them? I'll get to that in a moment.
But first, the bad news: scientists have proved that it is possible to create complex financial bundles (you know - bundles of mortgages that have "a few lemons" that are supposed to average out and make the whole bundle a great investment) that hide bad assets in such a way that no computer or human can detect the bad assets.
Even worse? Even after a buyer loses their shirt on the investment, it is impossible for the buyer to prove that they were sold junk, which makes it impossible to regulate.
Maybe it's time to eliminate this stuff for good?
This groundbreaking result was the work of several complexity theorists - Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge in their new paper Computational Complexity and Information Asymmetry in Financial Products.
So what do they prove? They prove that even for very simple CDOs (collateralized debt obligations), which is debt turned into securities, that there is no computer or set of computers powerful enough in the world to determine whether the CDOs contain a high proportion of lemons - bad asset classes that are worthless. This is a strong result: these sorts of computational intractability results are what we rest modern cryptography upon.
Freedom to Tinker has a summary:
Trading in derivatives brought down Lehman Brothers, AIG, and many other buyers, based on mistaken assumptions about the independence of the underlying asset prices; they underestimated the danger that many mortgages would all default at the same time. But the new paper shows that in addition to that kind of danger, risks can arise because a seller can deliberately construct a derivative with a booby trap hiding in plain sight.
The paper shows the example of a high-volume seller who builds 1000 CDOs from 1000 asset-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.
The paper itself contains a great introduction to the study of the topic. To quote them:
One of our main results suggests that it may be computationally intractable to price derivatives even when buyers know almost all of the relevant information, and furthermore this is true even in very simple models of asset yields.
The primary focus is on how the asymmetry of information between the buyer and the seller - the fact that the seller knows what among the debts being sold is bad and what's good, whereas the buyer may not - that is known. The paper proves that detecting the lemons among the bundles is computationally equivalent to a known hard problem (that is, one that is essentially impossible to solve). In other words, let's say you're a buyer and you devise a way to detect lemons in the CDO bundles you're sold - this paper proves that your solution also can be used to solve a problem that no computer scientist today can solve. So...it's unlikely you'll be able to detect the lemons. As they say:
It is well-recognized that since a seller is more knowledgeable about the assets he is selling, he may design the derivative advantageously for himself by suitable cherry-picking. However since securitization with derivatives usually involves tranching, and the seller retains the junior tranche which takes the first losses, it was felt that this is sufficient deterrence against cherry-picking (ignoring for now the issue of how the seller can be restrained from later selling the junior tranche). We will show below that this assumption is incorrect in our setting, and even tranching is no safeguard against cherry-picking.
It gets even worse, though, and this is the bad news for those who want to tinker around the edges with reform:
Would a lemons law for derivatives (or an equivalent in terms of a standard clauses in CDO contracts) remove the problems identified in this paper? The paper suggests a surprising answer: in many models, even the problem of detecting the tampering ex post may be intractable.
That is, even after losing your shirt, you can't prove that you were sold junk. Which means an agency tasked with regulating the securitized garbage wouldn't be able to prove it either.
So, what are we going to do about it?
Update: I wanted to point out this interesting observation made by NCrissieB (emphasis mine):
The "what to do about it" question is as counter-intuitive as the math. The problem isn't how to stop the trading of complex CDOs/CDSs. The problem is that if this paper is supported by other complexity theorists, no buyer should ever buy another complex CDO/CDS, at any price ...
... because not even the most sophisticated buyer with the NSA's computing capacity could calculate the risk of a single complex CDO/CDS within the lifetime of the instrument. That means there's no way to know if you're paying a fair price for that risk, nor even to know whether an instrument failed through bad luck or the seller's cheating.
If this paper is correct, no one should buy any but the most transparently simple CDOs/CDOs. The rest are value-less - they can't be sold at any price - and the government won't need to do anything to stop them from being traded. No buyer will touch them.
The problem isn't how to stop the trading of complex CDOs/CDSs; if this paper is right, that will stop. The problem is the capital already invested in complex CDOs/CDSs totals several times the world's annual GDP, according to this paper, and all of that capital will be inextricably frozen for the lifetime of these instruments. That is a giant, indissoluble clot in the world's financial arteries.