Intractability of Financial Derivatives
http://www.freedom-to-tinker.com/blog/appel/intractability-financial-derivativesBy Andrew Appel - Posted on October 15th, 2009 at 6:45 am
A new result by Princeton computer scientists and economists shows a striking application of computer science theory to the field of financial derivative design. The paper is Computational Complexity and Information Asymmetry in Financial Products by Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge. Although computation has long been used in the financial industry for program trading and "the thermodynamics of money", this new paper applies an entirely different kind of computer science: Intractability Theory.
A financial derivative is a contract specifying a payoff calculated by some formula based on the yields or prices of a specific collection of underlying assets. Consider the securitization of debt: a CDO (collateralized debt obligation) is a security formed by packaging together hundreds of home mortgages. The CDO is supposedly safer than the individual mortgages, since it spreads the risk (not every mortgage is supposed to default at once). Furthermore, a CDO is usually divided into "senior tranches" which are guaranteed not to drop in value as long as the total defaults in the pool does not exceed some threshhold; and "junior tranches" that are supposed to bear all the risk.
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.
It's like encryption: it's easy to construct an encrypted message (your browser does this all the time), but it's hard to decrypt without knowing the key (we believe even the NSA doesn't have the computational power to do it). Similarly, the new result shows that the seller can construct the CDO with a booby trap, but even Goldman Sachs won't have enough computational power to analyze whether a trap is present.
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.
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 Theory forms the basis for several of the technologies discussed on Freedom-to-Tinker: cryptography, digital-rights management, watermarking, and others. Perhaps now financial policy is now another one.
