Home Rong Ge, Princeton CS
Computational Complexity and Information Asymmetry in Financial Products

with Sanjeev Arora, Boaz Barak and Markus Brunnermeier. In ICS 2010

A short version appeared in Communications of the ACM, 2011 Issue 5.
Full text PDF

See some blog comments on this paper: Intractability Center, Freedom to Tinker, Boing Boing, Daily Kos, In Theory, Healthy Algorithms, Lipton's blog

We put forward the issue of Computational Complexity in the analysis of Financial Derivatives, and show that there is a fundamental difficulty in pricing financial derivatives even in very simple settings.

This is still a working paper. The latest version (updated Jan. 2012) can be found here:
Computational Complexity and Information Asymmetry in
Financial Products

FAQ for Computational Complexity and Information Asymmetry in Financial Products
  1. Why do you use a simple model? In real life people use more complex models while thinking about CDO pricing.

    This paper concerns a hardness result, not a pricing algorithm. As noted in the paper, our simple model can be embedded in the industry standard models like Gaussian copula, and the hardness result therefore extends to these complex models. In general, when proving a hardness result one should use as simple a model as possible. When exhibiting a pricing algorithm, on the other hand, one should use as complex a model as possible.

  2. Does the paper rely upon the P vs NP conjecture?

    The paper relies upon a stronger form of "P not equals NP", namely, that the planted dense subgraph problem does not have an efficient algorithm. (In fact it is conjectured that there is no algorithm to even compute any approximate solutions to this problem. There is also believed to be no short certificate that a dense subgraph of the specified size does not exist in the graph.) For more details on computational complexity see the first few chapters of this book.

  3. The hardness result applies in an asymptotic sense. How should one interpret this?

    The planted dense subgraph problem (with parameters as discussed in the paper) appears to have no efficient algorithm for even moderate graph sizes. So the hardness result should apply even with reasonable parameter choices. For example, say the number of asset classes is 1000, and each contains 20 mortgages. The seller group these into 200 CDOs, each with 100 mortgages. The threshold for senior tranche is set to 35%. Then in a binary CDO the buyer's loss (= lemon cost) is as high as 12.5%, and in a tranched CDO the buyer's loss is as high as 1.875%.

    Strictly speaking we only need to assume that the specific pricing algorithm used by the buyers and rating agencies does not detect dense subgraphs. In real life (at least before the current crisis hit) many buyers simply trusted the rating agencies, which usually use monte carlo simulations. Those would certainly not detect dense subgraphs for the above parameter choices.

  4. Are you suggesting that the phenomenon described in this paper was a major cause of the current global crisis?

    The current crisis had many causes, including poor modeling, regulatory failures, etc. This paper is focusing on an aspect (difficulty of pricing and how it worsens in presence of asymmetric information) that will remain even relevant after the above causes will be fixed.

    In general, financial experts suspect that the sheer volume of derivative transactions probably allows many kinds of manipulations to go undetected. We are highlighting one particular kind of manipulation where this undetectability as well as its financial cost can be made precise.

  5. Does your paper imply that CDOs and related products should be banned?

    For now, that would be a hasty conclusion. One can imagine some free market solutions to the issues raised in the paper such as (a) turn over design of CDOs to a neutral 3rd party to avoid cherry-picking. (But, keep in mind the experience with rating agencies in recent years.) (b) use CDOs with parameters where the planted densest subgraph problem is easy. (But, keep in mind that the market currently lacks full transparency, so it is unclear how to even obtain the graph on which to solve densest-subgraph!)

    Of course, one must then investigate if these new fixes allow other kinds of manipulation.  Our paper is only a first cut at establishing a role for computational complexity in thinking about derivatives. Hitherto this aspect has been ignored.