Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Predicting the stock market is hard! Can TCS make this sentiment more formal?

Recently I have started thinking a little bit about finance, and was wondering how knowledge of TCS could help. Hedge funds and investment firms seems to use algorithmic trading, machine learning, and AI all the time, but TCS results seem to be few. In particular, I only know two papers:

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge [2009] "Computational Complexity and Information Asymmetry in Financial Producs"

Philip Z. Maymin [2011] "Markets are Efficient If and Only If P = NP"

The first paper shows that derivatives can amplify the cost of informational asymmetry (instead of the desired goal of reducing it) for computationally-bounded agents. The second paper challenges the popular belief of efficient markets by showing that market efficiency can be used to solve NP-hard problems.

Are there any books/surveys or seminal papers on related ideas? Especially things related to the difficulty of predicting or approximating markets or trading optimally (or close to optimally) in such markets?

A slightly more meta question: why does there seem to be an abscence of papers on this? Is there no interest, or is that all the interested parties become quants that are hiden behind no-publication agreements?

Related question

Algorithmic lens in the social sciences

What is the Complexity Classification of Portfolio Theory in Financial Economics?

share|cite|improve this question
I always feel like I am hitting the boundary of off-topic with questions like this. If this question is off-topic, then we could migrate it to quant.SE; however, I really hope I can get the answers of TCSers on this. – Artem Kaznatcheev Aug 24 '11 at 18:09
I don't at all think this is off topic. – Suresh Venkat Aug 24 '11 at 21:10
There are some links on this Wikipedia article. I just remembered that Fields institute have had a number of programs on related topics recently that you may want to check, like this and this and this but there are more. – Kaveh Aug 25 '11 at 8:14
@Kaveh thanks for the links to the Fields institute! I really should come up to Toronto more often to attend their events. – Artem Kaznatcheev Aug 25 '11 at 8:17
@Artem, yes, it is not that far from Montreal. :) – Kaveh Aug 25 '11 at 8:21
up vote 7 down vote accepted

The question you begin with relates to predicting the stock market, but you seem to have broader concerns. I'll attempt to tackle your meta-question; apologies in advance for my sweeping generalizations.

As far as I can tell, academic computer science is far removed from the actual concerns of hedge funds and people who try to model and predict markets.

The current focus areas in algorithmic game theory are not obviously relevant to finance practitioners. In particular, worst case results are not seen as useful at all, and average case analysis based on artificial distributions seems largely irrelevant also. Yet the only way to obtain information about real distributions seems to be to actually engage in the market, updating one's information using a variety of learning techniques. This creates messy models that change dynamically and are not amenable to most types of analysis.

As an example, there has been a focus in finance on understanding the microstructure of trades. Market microstructure is an emergent property of the specific low-level market mechanisms that are in place, such as how frequently pending trades are matched, what information traders believe exists in the order book, techniques used to obfuscate that information, the roll-back mechanisms in place, contractual arrangements relating to settling trades, network latency in receiving updates about the current state of the order book, and many other factors. Market microstructure is a highly reflexive system, so the clean models typical of TCS seem beyond reach.

The market design community is trying to tackle questions like this (for instance see Huang and Stoll and the recent Kirilenko et al. paper on the flash crash), but they do not seem to have much interaction with TCS.

Finance has become increasingly complex as IT has pervaded markets. This means that most markets now consist of multiple interlocking systems which it may not be possible to meaningfully model separately. In addition, as markets move closer to continuous trading, I am not sure the TCS lens of computation is currently all that useful in finance; control theory, graphical models, fluid dynamics, and many other areas of applied mathematics seem more directly useful.

TCS methods could well be useful, but one needs to expend effort to understand what happens in finance, to find a place to apply the lever, and to acquire an appropriate mathematical toolkit. Personally I would like to see more work along the lines of Arora/Barak/Brunnermeier/Ge, which engage with deep questions. For instance, does adding more degrees of freedom to financial systems lead to good outcomes for the users of these systems? Or does adding complexity mainly serve to help intermediaries set up asymmetric zero-sum games against the users? There is probably a neat complexity-based argument waiting to be discovered...

So in a nutshell: you haven't seen much TCS/finance research because it is hard to apply TCS to finance.

share|cite|improve this answer
There is a lot of practical algorithm design, though -- as well as trying to discover and analyze the algorithms of others. An intriguing 15-minute TED talk along these lines is: – Aaron Sterling Aug 26 '11 at 20:53
@Aaron: thanks for the pointer. There is also a nice popular account from last year that is worth reading:… – András Salamon Aug 27 '11 at 11:02

I think the subfield of Algorithmic Game Theory is what you are looking for. Have a look at the online version of a recent book on this topic by N. Nisan (who is visiting here!), T. Roughgarden, E. Tardos, and V. Vazirani. Of particular interest might be the following chapters:

[5] Combinatorial Algorithms for Market Equilibria (by Vijay V. Vazirani)

[6] Computation of Market Equilibria by Convex Programming (by Bruno Codenotti and Kasturi Varadarajan)

[17] Introduction to the Inefficiency of Equilibria (by Tim Roughgarden and Eva Tardos)

[26] Computational Aspects of Prediction Markets (by David M. Pennock and Rahul Sami)

share|cite|improve this answer
I am aware of Algorithmic Game Theory. I was really hoping for more specific answers that relate specifically to things people in quantitative finance would care about. This feels more like a comment than an answer... – Artem Kaznatcheev Aug 25 '11 at 7:50
If you know about but don't ask about AGT, then state it and rule it out. One of your examples is on the hardness of market equilibria, which is a major topic in AGT. That's why I pointed to it. The other one is on the hardness of pricing derivatives, an even more specific subtopic. If you're exclusively interested in questions about pricing financial derivatives, and not market equilibria then remove the example on market equilibria or statet that you don't care about these. – Martin Schwarz Aug 25 '11 at 7:56
@Artem, I think this is a reasonable answer for the question: "Are there any books ... on related ideas?" :) – Kaveh Aug 25 '11 at 7:57
@Kaveh: The question is specifically asking "Are there any books/surveys or seminal papers on related ideas?" – Martin Schwarz Aug 25 '11 at 8:00
@Martin, I am confused, I expressed my agreement with you. – Kaveh Aug 25 '11 at 8:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.