5
$\begingroup$

I have been tasked with writing a 25 page paper on computational complexity. The first 10 pages of this should be background an introduction to the field (which I have largely done already) and the following 15 pages should discuss some specific area or application of computational complexity (such as cryptography).

Ideally, because it is an area that interests me, I would like to find a way to use this as an excuse to research computation and its importance in finance. I am now trying to find an area of mathematical/theoretical finance which allows me to do this (any suggestions to this end would be greatly appreciated).

According to Wikipedia,

"[The pricing of options has] a high degree of computational complexity and are slow to converge to a solution on classical computers."

To what end is this true, and how much detail could I go into on this subject?

Addendum: Also, is anyone aware of whether option pricing models such as the Black-Scholes model, would be classed as NP, NP-Complete, etc?

$\endgroup$
1
$\begingroup$

You want to stay away from this as a student for a project, even if you are a doctoral student. If you want to tackle this a doctoral student, then I would love to completely consume every moment of your time working on this because I do have a problem that I want to reduce to deterministic polynomial time. Trust me, you don't want to talk to me because there will never be an end to your headaches.

The Black-Scholes option pricing model has never had a successful validation study. Indeed, there are 3800 articles on just one anomaly that I have looked at. Part of a paper I am submitting for publication contains an argument that if the assumptions of Black-Scholes were strictly true, then there cannot exist an estimator that can converge to the population parameter, even with an infinitely large data set. No one ever actually formally looked at the properties of Black-Scholes as an estimator. Everyone just assumed the formula, if valid under the assumptions, would also be a valid estimator of the parameter. That turns out not to be the case, hence all of the anomalies.

If you want to stay in computational finance, go to bankruptcy estimation. It is a large and rich area with a nearly infinite tool set. The toolset is overly vast because of the combined pressures of publish or perish and the need to show that "I am smart, hire me, I could do something crazy fancy."

I tested 78 models of bankruptcy over a period of nearly 90 years. Using Bayesian methods, one model had approximately a 46% chance of being the true model, one model had a roughly 54% chance of being the true model and the remaining 76 models had a combined posterior probability that one of them was true of 1/10000th of one percent. All were statistically significant. Of the two, fortunately, neither shared the same variables so I was able to do a weighted average and that was far better than either separately.

It is easy to verify the qualities of a model, after it is built and you run it through the data. That is a linear problem. Testing multiple models is a combinatoric problem. This is even more so if no one knows the form of the function such as "even though the assumptions are violated, can you use logistic regression?" You will find random forests, logistic regression, Hopfield nets, and just about any technique that could classify or estimate failure. It is so difficult because firms across industries are not alike and the nature of those industries change as technology and preferences change. No model could be strictly stationary.

You will want to go back until at least the 1960's as paths started diverging then and the most recent stuff isn't really better than the foundational work. Much of the foundational work isn't really that good either.

If you think about bankruptcy as being akin to dying, then you are getting it wrong unless you read the children's books "Animorphs." Berkshire Hathaway was, for most of its history, a textiles firm. Now it sells ice cream through its Dairy Queen subsidiary, insurance through its Geico subsidiary and dozens of other things from carpeting to shoes. Firms change from turtles to cows to half-bears, quarter-dogs and quarter-fish. They survive by becoming something else. If you are writing software and assuming stability, then you are solving the wrong problem. That is complicated and that is complex. Look at bankruptcy.

$\endgroup$
  • $\begingroup$ Hi, thank you for your response. Are there any particular papers, books, or articles that you'd recommend reading to get more of a background on the computational complexity of bankruptcy estimation? $\endgroup$ – M Smith Feb 3 '18 at 12:28
  • $\begingroup$ Bankruptcy estimation is only complex if you believe that you do not know the model. Its complexity comes from the combinatoric nature of Bayesian hypothesis testing. In my office, and I am not there, I do have a book on combinatoric optimization, but I do not remember if it includes content on computational complexity. All model selection is Bayesian because the only tools outside direct Bayesian methods are things such as the AIC or BIC. They are just point estimates of Bayesian tools. There are ways to evade it such as stepwise regression, but that is a weak heuristic to escape it. $\endgroup$ – Dave Harris Feb 3 '18 at 23:15
3
$\begingroup$

Caveat - I am a finance person only recently exposed to theory of computation and complexity so this will be more finance and less CS.

The computational difficulty of option pricing is relatively well understood: If you buy the assumptions of the Black, Scholes, and Merton model, then we have a closed form expression for the European option price which has negligible computational requirements. Plug values into this formula and you are done

\begin{equation} \mathrm C(\mathrm S,\mathrm t)= \mathrm N(\mathrm d_1)\mathrm S - \mathrm N(\mathrm d_2) \mathrm K \mathrm e^{-rt} \label{eq:2} \end{equation}

The pricing of American options needs a different approach since the opportunity to exercise early complicates the problem. The key issue is path dependence, it matters not only where we end up, but how we got there. This is more computationally complex you need to value the option of early exercise so you have an optimal stopping problem. Cox, Ross, and Rubinstein show us how to do this on a Binomial tree and Longstaff and Schwarz showed us how to do this using simulations. I would argue that these are not slow to converge, but it depends on the intended meaning of classical computers!

We can then move on to more complicated options, that depend on many stocks or many states of nature to ramp up the computational complexity of this problem, in which case we may have slow convergence, since the dimension of the model is so large.

The BSM model makes very strict assumptions about the price process and we simplify greatly our model of price formation. We have to write down some prices process for any model but in reality the data generating process for stock prices is unknown and we feel intuitively that securities valuation is a complex problem.

We can make this intuition more formal by thinking of the problem in terms of the theory of computational complexity. If the problem of valuation is a certain level of complexity (NP-hard) then the investor may never be able to find the true value to act and get it into the price by trading.

This contrasts starkly with our information economics based view of price formation where agents process all relevant information and then trade on the (correct) conditional expected payoff of the stock price.

These papers should get you started: The computational hardness of pricing compound options. Braverman & Pasricha

Markets are Efficient if and only if P=NP. P Maymin

The Efficient Markets Hypothesis Does Not Hold When Securities Valuation Is Computationally Hard. Tang et. al.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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