DoI: 10.1145/1941487.1941511

Computational Complexity
and Information Asymmetry
in Financial Products

1. IntRoDuCtIon

A financial derivative is a contract entered between two parties, in which they agree to exchange payments based on events or on the performance of one or more underlying assets—independently of whether they own or control the underlying assets (e.g., the DOW Jones index falling below 10,000). Securitization of cash flows using derivatives transformed the financial industry over the last three decades. However, mispricing of these derivatives is believed to have contributed to the financial crash of 2008 (see e.g. Brunnermeier8 and Coval et al. 10).

There are also suggestions that derivatives were deliberately misused. In Spring 2010 there was a famous allegation about investment bank Goldman Sachs’s Abacus derivative. The security and exchange commission alleged that Goldman Sachs collaborated with short-seller Paulson to select particularly bad mortgages as the underlying assets for this derivative. Tranches of Abacus were sold to ABN Amro and IKB Deutsche Industriebank, who were unaware of Goldman’s selection methods and lost almost $1 billion within a few months of buying these assets.

Hence, it is not surprising that derivatives have attracted criticism—Warren Buffett famously called them “financial weapons of mass destruction”—accompanied with calls for extensive regulation and even an outright ban. Others point out—with ample justification from economic theory—that derivatives are beneficial because they allow better risk sharing by “completing” markets, and also protect buyers from the effects of asymmetric information, ameliorating the so-called “lemon” problem (which arises whenever one party in the transaction has more information about the asset than the other; cf. Section 2). According to this viewpoint, problems with derivatives would disappear with use of more accurate financial models, more vigilance by buyers and better governmental oversight.

In our paper, 5 which the current write-up is trying to
describe at a simplified level, we injected a new aspect into
this debate. We show that even when the underlying financial
model used by buyers and sellers is correct there is an inherent
obstacle to accurate pricing due to computational complex-
ity. Formally, even in industry-standard models, the pric-
ing problem can be as difficult as solving the planted dense
subgraph problem, which has been proposed as a basis for
cryptosystems. The practical implication is that though
derivatives such as collateralized debt obligations (CDOs)
can theoretically ameliorate the effects of asymmetric
information in the market, in practice these effects will per-
sist—or even get worse—because market participants are not
computationally sophisticated enough to solve cryptographic
problems. This suggests that better regulation and more
informed buyers are not sufficient for derivatives market to
work correctly, or at least that regulators and buyers should
take computational complexity into account. Such issues are
further discussed at the end of the paper in Section 5.
the bite of computational complexity: Computational com-
plexity studies intractable problems, such as NP-complete prob-
lems, which are conjectured to require more computational
resources than can be provided by the fastest computers. (For
an introduction see the text. 4) The key reason it comes naturally
into the study of financial derivatives is that it implies an asym-
metry between the ease of creating problems and solving them.
A simple example is the problem of factoring integers. It is easy
to take two random prime numbers—say 7019 and 5683—and
multiply them—in this case, to obtain 39888977. However, given
39888977, it is not that easy to factor it to get the two numbers
7019 and 5683. Algorithms that search over potential factors
take very long time. This difficulty becomes more pronounced
as the numbers have more and more digits. Computer scien-
tists believe that factoring an n-digit number requires roughly
exp(n1/3) time to solve,a a quantity that becomes astronomical
even for a moderate n like 10,000. The intractability of this prob-
lem leads to a concrete realization of information asymmetry.
Anybody who knows how to multiply can randomly generate
(using a few coin flips and a pen and paper) a large integer by
multiplying two smaller factors. This integer could have say
1000 digits, and hence can fit in a paragraph of text. The per-
son who generated this integer knows its (prime) factors, but
no computational device in the universe can find a nontrivial
factor in any plausible amount of time.b This informational
asymmetry underlies modern cryptosystems, which allow (for
a The precise function is more complicated, but in particular the security of
most electronic commerce depends on the infeasibility of factoring integers
with roughly 800 digits.
b Experts in computational complexity should note that we use factoring
merely as a simple illustrative example. For this reason we ignore the issue
of quantum computers, whose possible existence is relevant to the factor-
ing problem, but does not seem to have any bearing on the computational
problems used in this paper.

A previous version of this paper appeared in The First Symposium on Innovations in Computer Science (ICS 2010). Tsinghua University Press, Beijing, China; 49− 65.