Computational complexity and information asymmetry in financial products

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge

Research output: Contribution to journalArticlepeer-review

45 Scopus citations


Computational complexity studies intractable problems like NP-complete problems, which are conjectured to require more computational resources than can be provided by the fastest computers. The intractability of this problem leads to a concrete realization of information asymmetry. 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 if the unemployment rate next January, when rounded to the nearest integer, is the last digit of a factor of n. Computational complexity can be related to the bounded rationality concept in economics. 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.

Original languageEnglish (US)
Pages (from-to)101-107
Number of pages7
JournalCommunications of the ACM
Issue number5
StatePublished - May 2011

All Science Journal Classification (ASJC) codes

  • General Computer Science


Dive into the research topics of 'Computational complexity and information asymmetry in financial products'. Together they form a unique fingerprint.

Cite this