Skip to content

CDOs & Computational Intractability

December 29, 2009

Readers with backgrounds in derivatives and theoretical computer science may find amusement in the recent working paper from Arora et al.: Computational Complexity and Information Asymmetry in Financial Products.

The article provides delightful juxtaposition of cross-discipline buzzword bingo: computational complexity (theoretical computer science), asymmetric information / lemon costs (information economics), and densest subgraph problem (graph theory).

In short, the authors posit that detecting fraudulent CDOs/CDSs is essentially computationally intractable (p. 12). Needless to say, the press is already having a field day with the article to blame Goldman (arguably rightfully so, to the demise of their counterparties); despite what I wonder may be limited capacity to fully comprehend the subtle theoretical details of the article.

A few more choice words from the authors (p. 3):

What is surprising is that a computationally limited buyer may not have any way to distinguish such a tampered derivative from untampered derivatives…The paper suggests a surprising answer: in many models, even the problem of detecting the tampering ex post may be intractable.

The article is a pleasing practical application of computational complexity theory, which Arora and Barak cover nicely in their recent text, Computational Complexity: A Modern Approach.

6 Comments leave one →
  1. December 29, 2009 6:08 pm

    I loved this paper. To me, it unveils an ingenious perfect crime. Shows how much damage really smart, well-placed people can and will do if you don’t actively prevent it. I think the probability that some of the folks who developed & evolved these products weren’t aware of their aptness for bald-faced fraud (albeit perhaps less formally than the profs at Princeton) is so close to zero it might actually be a negative number ;^>

    • quantivity permalink
      December 29, 2009 6:31 pm

      @tito: absolutely agree; undoubtedly, the best complexity theory paper ever (can almost visualize the authors’ tongue-in-cheek tone). As you rightly point out, originators do appear as they must either admit ignorance or fraud; neither is particularly enviable (but, will undoubtedly go unpunished).

  2. January 2, 2010 12:13 pm

    I’ll disagree with this post on several grounds. Please don’t take this as being polemic: I agree with so many of quantivity’s post, but considering this the *best* complexity paper ever seems a very tall statement. In brief:

    1. CDOs are priced in a very different way from what the paper suggests. The model is beyond stylized, as to become unrealistic, all in order to reduce the problem to graph-theoretic NP-hard problems.

    2. It is well know that pricing a large class of structured products is NP-hard, e.g., basket options. In this respect, very little is new.

    3. However, one can provably approximate the price of real-world products. In fact, the error resulting from approximations is smaller than errors from parameter estimation and model mis-specification.

    Bloggers and journalists are quoting this article without having the tools necessary to understanding it, but simply projecting their preconceptions (GS is evil, finance is a house of cards etc.); the recent , ill-informed NYT report by Gretchen Morgenson on GS’ synthetic CDOs just adds fuel to the fire. Most importantly, the commenters also lack an overall view of the computer-science-in-economics literature. The latter so often rediscovers known concepts (e.g.: “price of anarchy” ~ “second best”) or focuses on poorly posed problems of no consequence to theory and practice.

    • quantivito permalink
      January 2, 2010 1:11 pm

      @Gappy: thanks for your comments. Allow me to clarify the fitness of my assessment was intended to be pedagogically tongue-in-cheek (as I imagine the authors intended); by no means is it technically the best complexity paper.

      If the authors indeed intended the article in all seriousness, then I absolutely concur with your comment (and further would claim evidence the authors have no exposure to exotics, of any sort, or standard MC pricing methodologies).

      One could be mildly polemic and note wryly the criticism of “focus on poorly posed problems of no consequence to theory and practice” can be leveled against a non-trivial proportion of academia (for which they would happily not disagree).🙂


  1. Bingo game · a Search - Tennis
  2. Online bingo games » The Key to Profitable Soccer Betting

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: