Computational Intractability Applied to Understanding the Risks of Financial Derivatives
In a result that may have implications for financial regulation, PIs Sanjeev Arora and Boaz Barak, grad student Rong Ge and economics colleague Markus Brunnermeier have shown that computational complexity could lead to difficulties with pricing and regulating financial derivatives.
Mispricing of these derivatives by banks is believed to have played a big role in the current financial crisis.
Though many experts thought that the mispricing occurred due to faulty modeling, the new study shows that even if we have correct models, the pricing of derivatives can be computationally intractable. The problem arises because of asymmetric information: sellers who have additional knowledge about the assets they are selling (e.g., they know that some assets are lemons and worth less than others) could create new financial products called Collateralized Debt Obligations (CDOs) that have low yield but hide the lemons so well that they are computationally indistinguishable from high-yield CDOs. Thus buyers (and regulators!) cannot distinguish low-yield products from high-yield products, from which it follows that they must misprice at least one of the two classes.
Such results suggest a revision to received wisdom in economic theory, which holds that derivatives mitigate the effects of asymmetric information —-the new work shows that such mitigation is much less effective once computational complexity is accounted for.
The work, which has been published at the Innovations in Computer Science conference in January 2010, and in an invited contribution to the Communications of the ACM in 2011, has attracted a lot of attention on computer science and economics blogs because of its novel mix of computer science and finance theory.
Links to papers, blog discussions, and answers to some FAQs can be found at
http://www.cs.princeton.edu/~r
Natural Algorithms
This is an area started by coPI Bernard Chazelle, whereby insights from theoretical computer science are used to explain properties of large systems of interacting agents (which have been long studied using continuous tools from dynamical systems).
Using CS theory tools we have helped solve major open problems in multiagent systems: (1) Why Facebook causes people’s opinions to settle, whereas TV and radio cause them to change endlessly in cyclical fashion (crux: two-way vs. one-way communication); (2) Why bird flocking converges; (3) Why symmetric communication causes fireflies to flash in synchrony.
Sample publications:
The Unique Games Conjecture
Much advance in our understanding of approximation algorithms in recent years has been tied to coPI Khot’s unique games conjecture. The work of Khot and others has shown that this conjecture implies the intractability of approximating many other problems. More strikingly, for many problems it even predicts the best polynomial-time approximation algorithm, namely, the one using a simple Semidefinite Program (SDP). For this work Khot received the NSF Waterman Award in 2010.
The center members’ research has clarified the status of the conjecture. Our work has established that the unique games problem is easy on random and random-like instances (Arora, Khot, Kolla, Steurer, Tulsiani, Vishnoi, ACM STOC 2008) and even for semirandom instances (Makarychev, Makarychev, Vijayaraghavan, ACM STOC 2012). Thus hard instances for the problem —which must exist if the UGC is correct— must be quite atypical. Another breakthrough was the discovery of a subexponential algorithm (Arora, Barak, Steurer 2011) for approximating the unique games problem —very surprising for a problem that is conjectured to be NP-hard. In the other direction, Khot and Moshkovitz (IEEE FOCS 2011) have taken the first steps in trying to prove the UGC. Raghavendra and Steurer (ACM STOC 2010) found a close connection between the UGC and the approximability of small-set expansion problem, which for the first time gives an important consequence of falsifying the unique games conjecture.
Thus the problem is very evenly poised and we hope it will be soon resolved.
People involved in this research:
PIs: Sanjeev Arora, Boaz Barak, Moses Charikar, Subhash Khot.
Postdocs: Alexandra Kolla, Madhur Tulsiani.
Students: Konstantin Makarychev, Yury Makarychev, David Steurer, Aravindan Vijayaraghavan
Media:
Approximately Hard: The Unique Games Conjecture. Erica Klarreich. Simons Foundation MPS Featured Article, Oct 2011.
NSF’s press release on Waterman Award for Subhash Khot.
Unique Games: A 3-act play. Richard Lipton’s article on his popular blog.
Pseudo-randomness
We all think we know what randomness is. The stock market is random since, if one was able to predict its fluctuations, the entire system would collapse. But what is randomness really? Can we understand randomness using the tools of theoretical computer science and mathematics? Work done at the center focuses on this question in many different guises. Work done by center PI's, postdocs and students attempts to understand the role of randomness in our lives by studying the way randomness affects computation, communication and constructions of `random looking' objects.
A key notion in this line of work is that of `pseudo-randomness' or 'fake' randomness. Can we design deterministic procedures that imitate the behavior of random ones. This powerful notion is central to understanding randomness since, to succeed in imitating random processes, we must understand them. Pseudo-randomness appears in many areas of TCS and mathematics and is related to many different open problems.
Sample publications:
Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields (Shachar Lovett, Partha Mukhopadhyay and Amir Shpilka.) FOCS 2010.
Pseudorandom Generators for Regular Branching Programs (Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff), FOCS 2010.
Subspace evasive sets. (Zeev Dvir and Shachar Lovett) STOC 2012.
Approximation Algorithms
Approximation algorithms are efficient heuristics with provable guarantees for hard optimization problems. Modifying the problem so it can be solved by a mathematical program (a mathematical relaxation) and using the solution to solve the original problem is an especially powerful paradigm. We highlight two strands of research at the center (amongst several) in this area.
Research by center members developed new insights into the densest subgraph problem that arises in many practical settings (detecting communities, protein complexes, etc) but is also used as a hard problem in two different pieces of work by coPIs – on intractability of pricing financial derivatives and in new public key cryptography schemes. Attempting to bridge the huge gap between algorithmic and hardness results, our work showed that the approximability in the worst case may be linked to the approximability for a natural distribution of instances, proposing a concrete barrier to further progress (Bhaskara, Charikar, Chlamtac, Feige, Vijayaraghavan, STOC 2010).
Center members have studied the power of the sophisticated and somewhat mysterious relaxations obtained by lift-and-project procedures, a promising direction for approximation algorithms. We showed that Laserre relaxations can be exploited to obtain significantly better algorithms for the notoriously hard classical graph coloring problem in interesting cases (Arora, Ge, APPROX 2011). For densest subgraph, we showed that these lift-and-project relaxations do not surmount the natural barrier we identified earlier for the problem (Bhaskara, Charikar, Guruswami, Zhou, SODA 2012).