# Computational complexity in quantitative finance

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:

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?

• 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
• Regarding Maymin's paper: Maymin reduces between a decision problem that he claims is a form of the Efficient Market Hypothesis and a special case of KNAPSACK. This problem isn't obviously NP-hard: the values of the parameters $B$, $K$, and $k$ are fixed, which would allow a dynamic programming solution to work. Maymin's basic argument seems to be that $k$ keeps increasing as more data becomes available. This might be reasonable, but the computational complexity part of the paper needs more work. (These comments are based on the ArXiV version; I haven't read more recent versions.) – András Salamon Aug 27 '11 at 11:29

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.

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)

• 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

From SSRN, two papers related to the complexity of portfolio optimization:

From arXiv:

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

If stocks are modeled as random variables like geometric Brownian motions then prediction becomes a concern of statisticians, I suppose.

But there is also market psychology. The field known as technical analysis is all about trying to extrapolate from past prices. How hard might that be --- how hard is it to recognize the relevant patterns, if there are any?

The Complexity Option Game invites you to test your mettle at recognizing patterns in stock movements and cashing in when one appears, with a payoff of up to \$11 imaginary Internet dollars and a public high score table. And there is an accompanying paper with some tentative results.

• There are some relevant patterns in probability sense, but operating according to these patterns may take fat-tailed risk. And some of them are not very hard, or I'd say some are easy, Sometimes I suspect why people think stocks and derivatives are modeled as random variables. – XL _At_Here_There Jul 23 '17 at 19:53
• I have asked a question about why the stock process is modeled as martingale,since so many people think there are relevant patterns, they downvote my post! – XL _At_Here_There Jul 23 '17 at 20:07