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.
As Bucktown points out above, you can write a derivative contract with virtually any terms. You can have derivatives whose payment or value depends on the value of other derivatives, with complicated time dependencies. You can also have contracts (such as credit default swaps) whose value depends on whether another derivative does, or does not, pay. And you can also trade derivatives, so that their ownership changes over time.
Given those capabilities, it sure looks like one could construct a Turing machine with a little effort. If so, the markets could get well beyond mere intractability and into undecidability, so that there literally was no “correct” valuation for the derivatives involved.
I could even imagine, given the sheer number of contracts and the ways in which they are traded, that such situations could arise accidentally. It wouldn’t even need a full Turing emulation; I could easily see a situation where two contracts accidentally become mutually interdependent, say:
Contract A is written to hedge an investment in structured investment vehicle Q. Contract A says that it will pay $10 if Q has a value of $0 on January 1.
Contract A is now a derivative, and is traded a few times. Someone notices it in their portfolio, and considers it worth hedging this bet.
Contract B is accordingly cut, to pay $10 if contract A does not pay out.
More trading ensues. Did I mention that SIV Q is engaged in derivatives trading? It is…
January 1 rolls around, and SIV Q is audited. Its sole asset is contract B.
So what are the values for derivatives A and B? If B’s value is 0, then Q’s value is 0, so A pays $10 and B pays $0, which is consistent. But, if B’s value is $10, then Q’s value is $10, so A pays $0 and B pays $10, which is also consistent. Which of these two equally-valid assignments is correct?
One could also imagine B having been constructed to move in parallel with A, that is, to also pay $10 if A’s value was $10 and zero otherwise. This is a little less likely in practice (it might arise as a kind of index), but would result in a situation where there was no valid assignment of values: If Q’s value is $0, A pays, and so does B, so Q’s value is $10; if Q’s value is $10, A does not pay, so neither does B, so Q’s value is $0.
You know, as I consider this little scenario (in either version), it seems horribly plausible. Are there any safeguards to prevent it? (Can there be safeguards, since there’s an undecidability question lurking?) Or is it just really low-probability for the more normal courses of trading, and simply hasn’t come up?
It doesn’t really matter what the derivative is “really” worth. It just matters what the other participants in the market are willing to pay. (And in this hypothetical that would probably depend on who was in a position to sue whom…)
I actually think that this same-model notion bears a fair amount of responsibility for the boom and bust. People whose models (correctly) predicted that the value of a lot of CDOs was zilch didn’t trade in them; only the people who could hoodwink their software into producing numbers that more-or-less agreed with everyone else’s numbers stayed in the game. (And worse yet, because the market can stay irrational longer than you can stay solvent, people who didn’t stay in the game showed lower short-term returns and lost investors to the people who did stay in.)
What about a CDO exchange where the seller has assets to package and instead of the seller making packages the buyer then buys, and being able to booby-trap some of the packages, the seller lists a menu of assets and the buyer picks which ones to package, or they meet and use a random number generator (which both are free to inspect) to decide which of the seller’s assets to bundle into the CDO for the buyer, or one supplies an RNG and the other a rule for mapping its output to assets?
This is similar to the old you divide the cake, I choose which half solution to a simple but related problem in fair transfer of resources. In particular, all allow a seller to package assets into CDOs, but do not allow a seller precise control over which assets go in which CDOs, without which control the booby-trapping becomes impossible.
For some frequently asked questions about this paper, please visit our FAQ page.
I am glad to see the comment by Kaleberg on “information hiding”. To go a step further, where is the economic value in the creation of these exotic financial “products”?????. Essentially, these so-called financial products turn a concrete asset into an abstraction without any real value. To put this a bit differently, it creates trading “opportunities” that allow the traders to strip the asset of its true concrete value through commissions.
Think of it this way, when you buy a house/sell a house the realtor is paid a commission. That commission can be said to DECREASE the value of your house. (This assumes that the buying/selling house costs are kept with the house and not funded through an external source such as your income.) After so many such transactions, the asset would end up with $0 worth. The creation of financial instruments that do not create/facilitate economic value should be discouraged.
Economic theory tries to explain the “value” of derivatives. See for example the work of DeMarzo which is discussed in our paper. Economic theory is often counterintuitive (e.g., the classic work on benefits of trade).
However, one of the key results in our paper is that this value of derivatives can go away because of computational intractability. See the discussion in Section 1.3 of our paper.
There are ways in which market transactions can generate wealth, if they transfer assets from people who value them less to people who value them more. That having been said, if a market transaction or combination thereof transfers assets from people who value them more to people who value them less, and yet still generates income for one or more of the participants, that money is coming out of someone else’s pocket. IMHO, much of the obscurity in the derivatives market exists to hide whose pocket is being picked.
Suppose Honest Ed runs a private lottery. He sells 10,000 tickets for $100 each, each with a different four-digit number. The person whose number comes up on the following Friday’s afternoon drawing for the Illinois State Lottery Pick-4 wins $750,000. Pretty simple to figure the odds. The expected value of each ticket is $0.75, and Sam has a guaranteed profit of $250,000.
Now suppose Sam Slick sets up a lottery. As above, the winning number will be chosen by the Illinois State Lottery Pick-4, but with two differences: (1) the promised prize is $1,500,000, and (2) Sam’s tickets all bear the number 5473. Assuming nobody compares ticket numbers, what would be Sam’s expected profit, and what would be the expected value of each ticket?
IMHO, many of the people selling derivatives were well aware of the correlated risk; they figured that each day the doomsday scenario didn’t hit, they could pocket nice profits, and when it finally did hit, they could welsh on their bets.
It’s all about information hiding. In the 1920s and 1930s, Ivar Krueger, the matchbox king, took over solvent companies and used them to hide highly speculative, highly leveraged corporations which he would recapitalize. His trick was to start with a good history and good balance sheet and hide the critical elements of his restructuring which generally made the new enterprise worthless. Krueger, of course, was a piker by modern standards, and blew his brains out when the information began to leak out as the market was stressed.
First, a CDO is not actually a derivative. Derivatives are bilateral contracts between an issuer and a buy dictating terms of payment according to reference to an independent condition, including swaps, options, and futures . see wiki. So you and I could contract for payments between each other depending on almost any third referent, exchange rates coffee prices etc. Neither you nor I have to actually own any foreign currency or coffee however.
CDOs are securities that structure the payouts of actual assets, usually debt instruments as in the MBS CDO example above. This is not a bilateral bet which derives its value from a third party information source.
Second, I’ve never heard of a CDO tranching payouts by dividing up its asset pool. In your example you said CDO creators could put all the lemon mortgages (or more likely MBS) in a single tranche, increasing the chances of payout to other senior tranches. That structure would not expose the senior tranche holder to any of the exposure (up or down) from the lemon asset – and it would be effectively a separate CDO from the lemon-holding tranche. CDO tranches are usually structured to expose all tranches to the same pool of assets, but change their payout position along the income stream (hence the term “senior tranche holder” = the first to receive payment from the assets). In fact, the various tranches on an income stream is often called a payments “waterfall.” Imagine the senior guys are first in line up the river and drink their fill, leaving the rest to the last in line.
This leaves the junior tranches, the junk, in a first-loss-position. If the river runs out before everyone gets a drink, they will be the first to go thirsty. They take the first losses on the whole pool of assets, providing a kind of buffer against a percent of losses on the whole asset pool to the senior tranche holders. That’s why they are valuable, because no matter which asset turns out to be the worst performing, the senior guy is protected.
You see how the lemon-stuffing problem is not really applicable to this “waterfall” payment seniority-based structure. No one has to know where the junk is, the junior guy always takes the first hits. That’s why the junior position is cheap but risky to buy.
The real problem with CDOs is that they can hold tranches of MBS or tranches of other CDOs (CDO-squared). These could build a senior tranche of a CDO squared out of many junior positions. When the whole asset class, mortgages, declined all the junior positions of all the underlying assets got wiped out – thereby wiping out even the senior positions of CDO-squared. The only shocker was that these institutional investors and large financial institutions bought these believing them to be safe. To extend our river metaphor, these were new streams created from the very tail waters of other rivers, and their senior tranche holders are first in line, but only for a muddy gulp.
A couple things:
1. As I understood it, the authors weren’t t talking about tranches of the same CDO, but rather lemon-loading individual CDOs out of a portfolio of CDOs, so that even the AAA tranche could get clobbered (deliberately, rather than recklessly).
2. There are, IIRC, “synthetic” CDOs, which are precisely derivatives of the kind you’re talking about: the buyer is exposed, for a price, to the risk of the underlying securityies without there actually being anything underlying except the issuer’s faith and credit. Even more profitable than the regular kind.
Both Keith and rp are right that we didn’t carry out in this paper a thorough study of actual derivatives used in the market. This is definitely something that can shed more light on this issue.
In our defense, when the main result is an impossibility result in a simple model, you’d expect the more complex scenarios of the real world will only make things harder and not easier (as noted by rp).
I also note that the concrete assumption we make is an average-case hardness assumption, this is stronger than assuming that NP is not equal to P, but if true it’s hard on exactly the instances that arise in this work. (Also, there is no known co-NP type certificate for the non-existence of dense subgraphs, and indeed in the worst-case for certain parameters such certificates are known not to exist assuming NP is not equal to coNP.)
Also note that in practice, people don’t try to run the state-of-the-art algorithms based on semi-definite programs or spectral techniques, but just use Monte Carlo simulation. This will miss planted dense subgraphs and generally the result of such simulation are extremely sensitive to the model used and to the “continuity” of the derivative payoff function. What we show is that you can create a highly discontinuous derivative that can “fall of a cliff” under a change in a relatively small fraction of its asset pool, but is indistinguishable from much safer products.
First off, I want to note that there’s no such thing as “intractability theory”. The theory which is being used, as the paper correctly states is “computational complexity theory”.
But the more important point is to note that this is a purely theoretical result. What it shows is that the amount of computing time which it would take a buyer to figure out the exact value of a CDO grows substantially faster than the amount of computing time it would take a seller to create biased CDOs which benefit them. There are two immediate problems in applying this to the real world. The first is that they don’t actually calculate the time needed for existing CDOs. Obviously some CDOs involve a large number of assets, but just because the time is exponential in the number of assets does not establish that it is so large that the buyer cannot compute it. In practice, there are quite a number of NP complete (and even exponential) problems which are entirely tractable for the concrete instances of them which frequently occur. To establish whether or not this is the case, the authors would need to gather some real industry numbers and then run some simulations to determine the actual wall time involved in solving instances of the problem.
The second issue is that they don’t address whether or not the solution can be approximated in polynomial time. Even if the buyer cannot establish the exact price within polynomial time, that does not imply that the buyer cannot approximate the price within polynomial time. It may be the case that the buyer can find a sufficiently good approximation of the solution to give sufficient information to make good enough purchasing decisions.
They should also consider addressing the question of whether or not the problem is in co-NP. If it is, then the seller could offer a short certificate which could be used to verify that they had not created a biased CDO. The validity of such a certificate could be verified in polynomial time. Mind you, I’m not saying that the problem is in co-NP, just that they should check whether or not it is.
On your last point, if any NP-complete problem were found to be in co-NP, that would be a theoretical earthquake, as it would prove NP=co-NP, which is not widely believed to be true. I can forgive them for not working too hard to prove NP=co-NP. Otherwise, you raise good points.
You’re correct, of course. What went wrong was this: I initially was also going to point out that the paper only proves that the problem they are looking at is in NP. They demonstrate that the problem they are examining can be reduced to an NP complete problem, not the opposite. This is still, strictly speaking, a correct thing to say, but I decided that since I hadn’t read the Bhaskara et al paper which they reference, that I should tone things down a little in case it had something more specific to this problem in it (although this seems unlikely). As a result, lacking that point, the idea that they should also check to see if the problem is co-NP doesn’t really make that much sense when you presume that the problem they’re investigating is NP-complete. Even in light of the fact that they’ve only shown the problem to be in NP, it may not be the best suggestion in the world.
In practice a couple of things might make the situation even worse than this.
1) The CDO builder has imperfect information (ahem) about the quality of the assets being put into the CDOs, so even if they attempt to load all their products evenly by risk there are bound to be some CDOs filled with lemons. (There will also be some CDOs filled with cherries and whipped cream, but better-than-expected default behavior doesn’t necessary give you as much gain as the loss from worse-than-expected behavior.)
2) The lemons Arora et al are talking about are superimposed on the background of lemon-loading that makes CDOs so profitable to the originators. (In short, security ratings, such as they are, are nominally based on default-risk bins: say, 0-5%, 5-10%, 10-20% and so forth. Investors buy as if the typical security is in the middle of its risk bin, but CDO builders can aggregate their asset pools so that each CDO is at the high-risk edge of the bin. They then exploit the information asymmetry for profit.)
1 and 2 simultaneously make CDOs riskier for buyers and provide a level of background noise that makes deliberate lemon-loading more difficult to prove, absent internal memos.