example) two parties to exchange information over an open channel in a way that an eavesdropper can extract no information from it—not even distinguish it from a randomly generated sequence of symbols. More generally, in computational complexity we consider a computational task infeasible if the resources needed to solve it grow exponentially in the length of the input, and consider it feasible if these resources only grow polynomially in the input length.

Computational complexity immediately implies the existence of hard-to-price derivatives, albeit unnatural ones. Consider for example a derivative whose contract contains a 10,000 digit integer n and has a nonzero payoff iff the unemployment rate next January, when rounded to the nearest integer, is the last digit of a factor of n. A relatively unsophisticated seller can generate such a derivative together with a fairly accurate estimate of its yield (to the extent that unemployment rate is predictable), yet even a sophisticated investor like Goldman Sachs would have no idea what to pay for it. This example shows both the difficulty of pricing arbitrary derivatives and the possible increase in asymmetry of information via derivatives.

While this “factoring derivative” is obviously far removed from anything used in current markets, in this work we show that similar effects can be obtained in simpler and more popular classes of derivatives that are essentially the ones used in real life in securitization of mortgages and other forms of debt. The person selling the derivative can structure (“rig”) the derivative in a way such that it has low yield, but distinguishing it from a normal (“unrigged”) higher yield derivative is computationally intractable. Thus any efficient pricing mechanism would either overvalue the rigged derivative or undervalue the unrigged one, hence creating an inefficiency in the market.

Densest subgraph problem: Our result relies on the conjecture that there does not exist a tractable algorithm to detect large dense subgraphs in random graphs. This is a more specialized assumption than the familiar P ¹ NP conjecture. We needed this assumption because we needed to exhibit the intractability of “real-life” derivatives, and the setting there naturally leads to random graphs, as will be clear in the description in Section 4.

Computational complexity and “bounded rationality”: Computational complexity can be related to the bounded rationality concept in economics. Simon14 proposed the notion of bounded rationality to recognize that in decision making, real-life agents are limited by their cognitive ability to process information and the finite amount of time they have. Simon postulates that agents use heuristics instead of time-consuming and complex optimizing behavior. Experimental evidence on behavioral biases supports this notion (e.g. Kahneman, 13 etc.). On the other hand, economic experiments also suggest that as the stakes rise and people face similar situations repeatedly, they behave more deliberatively in a way that approaches rationality. In particular this is the case in the setting of finance, where stakes are high and traders have access to cutting edge technology. However, even the most sophisticated traders cannot escape the limitations of computational complexity, since no physically realizable computational device can solve intractable problems.

102 CommunICatIons of the aCm | MAy2011 | vOl. 54 | nO. 5

And we show in this note that pricing certain financial derivatives may require solving problems that are believed to be intractable, hence placing it beyond the reach of any real-life agent.

2. the “Lemons PRoBLem” In eConomICs

To understand the theoretical benefits of financial derivatives it is useful to recall the lemons problem, introduced in Akerlof’s classic 1970 paper. 1 The simplest setting is as follows. You are in the market for a used car. A used car in working condition is worth $1000. However, 20% of the used cars are lemons (i.e., are useless, even though they look fine on the outside) and their true worth is $0. Thus if you could pick a used car at random then its expected worth would be only $800 and not $1000. Now consider the seller’s perspective. Suppose sellers know whether or not they own a lemon. A seller who knows he has a non-lemon would be unwilling to sell for $800, and would therefore withdraw from the market. The market would be left only with lemons, and knowing this, buyers would refuse to buy any car. Thus the market grounds to a halt. Akerlof’s paper goes on to analyze reasons why used cars do sell in real life. We will be interested in one of the reasons, namely, that there could be a difference between what a car is worth to a buyer versus a seller. In the above example, the seller’s value for a working car might be $200 less than the buyer’s—perhaps because the seller is moving across the country and needs the cash—thus allowing trade to occur. In this case we say that the “lemon cost” of this market is $200. Some authors refer to the lemon cost as a wedge. Generally, the higher this cost, the less efficient the market.

The lemons problem can potentially arise in almost every area of the economy, and a large body of work in information economics describes how it can be ameliorated. Akerlof’s original paper already described signaling mechanisms by which a seller can reliably communicate his private information—namely, prove that his car is not a lemon— to the buyer. For example, a used car dealer can show the buyer repair records, or provide a warranty for 6 months, or point out to his stellar reputation and rating from the Better Business Bureau.

3. fInanCIaL DeRIVatIVes anD CDos

The lemons problem also arises in the financial industry and the usual mechanisms for dealing with lemons problems (as identified by Akerlof) have also flowered: borrower FICA ratings (a.k.a. credit scores), ratings of individual securities by agencies such as Moody’s, etc. Financial derivatives provide another mechanism for dealing with the lemons problem. Below we will illustrate this with a common derivative called the collateralized debt obligation or CDO.

It is not commonly known, but the humble home mortgage is actually a very complex instrument that presents great risks for lenders. The payoff structure is complicated; risk of default is fairly high (compared say to a U.S. treasury bond); and there is high risk of prepayment at times of low interest rates, which is precisely when the mortgage’s locked-in higher rate is most valuable to the lender. CDOs are financial devices that allow many mortgages to be aggregated into a security that has a supposedly much more