I am new to the world of investing, so please excuse the clumsy wording of the question... there is probably a better term for what I am looking for or maybe this is even a known/classic problem. If so, please kindly point me in the right direction ;-)


Investment strategies are compared against "the market", which is usually some weighted index of some / all securities in a given universe. However, the choice of market portfolio is somewhat arbitrary when it can be defined by the investor. A comparison of the alpha / performance of two investors' strategies could be quite difficult when one investor benchmarks her strategy against market portfolio A, while another benchmarks it against market portfolio B.

Thinking about this problem I ended up with the following idea: Why not compare every strategy against the hypothetical optimal return that could be achieved within the relevant universe and time frame if one had a crystal ball, i.e. by magically buying / selling the combination of securities that would lead to maximum return?

For each set of investment constraints, there is (usually) only one such optimal strategy and thus the "Crystal Ball Return" would be the ideal reference for objective comparisons of investment strategies.

The Problem

For the sake of simplicity let's assume we have a universe that consists of n stocks (with end-of-day prices) and are looking at an investment time frame of d trading days. We're investing a pre-defined amount of money m (enough to buy at least one of each stock) and there is small but non-negligible fee f for every transaction. We can change the portfolio (buy/sell stocks) once a day, but we don't have to. All returns are compounded. UPDATE: To keep it simple (and the returns bounded), short selling is not allowed.

My question is:

How does one efficiently calculate the sequence of buy/sell actions that leads to the maximum possible return?

To me this smells like dynamic programming, however, maybe I am missing something. The problem formulation seems so commonplace that I'm hoping there is a seminal paper / solution you can point me to.

If you provide a solution, please try to give some indication of its time / space complexity. Thank you.

Note: On first thoughts, fees seem to be a necessary constraint, since without them the optimal strategy would simply be to move all the money on a daily basis into the stock that's growing the most.

  • 2
    $\begingroup$ I think you are right in the fact that adding fees makes the solution non-trivial. But nonthless I don't think that it will be useful for comparisions. First of all, I guess that the portfolio will still consist of one asset at the time. The algorithm will allocate all money to the 'optimal' asset for some time period. Why should the money ever be splitted? Secondly the resulting performance will be many times better than any realistic portfolio. If you allow for short selling the possible returns are not bound at all. $\endgroup$
    – Ami44
    Commented Sep 12, 2016 at 21:53
  • $\begingroup$ This is a standard problem and easily solved using DP in O(n) time and space. Also user22686's remarks are correct, it's easy to prove that the optimal strategy is a all-or-nothing strategy, there will never be more than one instrument in the portfolio. $\endgroup$
    – hroptatyr
    Commented Sep 13, 2016 at 8:56
  • $\begingroup$ @user22686 Thanks! You are absolutely right - the portfolio will always consist of one instrument at a time. This didn't occur to me before. That should make the solution a whole lot easier. Regarding the usefulness: IMHO the fact that any real-life strategy will only ever capture a fraction of the theoretically attainable return is fine. You can still objectively compare a strategy that yields 16% of the hypothetically possible return to one that yields 14%. $\endgroup$ Commented Sep 13, 2016 at 11:47
  • 1
    $\begingroup$ @KlaasNotFound you need to have one more constraint, namely that you want to be flat at the end of the data. Then you go from there calculate which was the best position to hold prior to that, and so on ... It's a bit much to explain it here in detail, just read up on it, e.g. cs.rpi.edu/~magdon/courses/cf/notes/optimal.pdf $\endgroup$
    – hroptatyr
    Commented Sep 13, 2016 at 13:37
  • 1
    $\begingroup$ Actually the optimal strategy should be one stock short (maximum amount possible) and use proceeds of that short stock to get the long stock. This strategy would actually yield infinite return given no investment needed. $\endgroup$
    – phdstudent
    Commented Sep 14, 2016 at 1:04

1 Answer 1


This answer seems to be wrong. Please read the edit and the comments.

To me, that smelled like dynamic programming too. After implementing a dynamic programming solution according to http://www.cs.rpi.edu/~magdon/courses/cf/notes/optimal.pdf and other sources from the same author, it dawned on me that dynamic programming might not really be necessary at all.

In the end, what you want is to put all your value into the single one asset $a_t $ whose price $r(a) $ will grow the most in the next time step among all assets $A $.

$$ a_t = \max_{x \in A}\Big(~\frac{r_{t+1}(x)}{r_t(x)}~\Big) $$

The "investment path" (series of target assets for each point in time) $[~a_0, a_1, ..., a_T ~] $ that results from the greedy solution above is identical to the one generated by the dynamic programming approach. In hindsight that also makes sense, really.

Things get a little more intricate when you have to consider fees, but not too much. To get the target asset at $t + 1 $ while considering fees, just take the $max $ like before but multiply the rate of growth of every asset different from the one you're holding at $t - 1 $ with $1. - fee $. (In case of constant fees, you'd have to multiply the ratio with the current value of your portfolio and subtract the fee from that for every $x \in A $.)

$$ a_t = \max_{x \in A}\Big(~\frac{r_{t+1}(x)}{r_t(x)} * \big(1. ~\text{if}~ x == a_{t-1} ~\text{else}~ (1. - fee) \big) ~\Big) $$

Dynamic programming still has a value here in case you have restrictions like maximum number of trades. If you don't however, I don't really see why to bother with it.

Edit: As mentioned in the comments, the simple greedy approach turned out not to be a replacement for the dynamic programming solution after all and it is not optimal.

Imagine two assets, the one you're holding is staying at the same valuation (continually growing by a factor of $ 1.0$), the other one continually growing by a factor of $ 1.1$, and the fees being 10% or $ 0.1$. Switching would require picking an immediate growth factor of $ \frac{1.1}{1} * (1 - 0.1) = 0.99 $ over a factor of $ 1.0$ for a constant growth by 10% in contrast to no growth at all. The method above, however, would never switch in such a scenario.

  • 1
    $\begingroup$ Perfect, thank you! $\endgroup$ Commented Apr 25, 2020 at 18:14
  • $\begingroup$ What if another asset outperforms the one you hold by 0.9 * fee every day? Your algorithm will never buy it. $\endgroup$ Commented Apr 8, 2023 at 18:49
  • $\begingroup$ i don't see why it wouldn't. max always chooses the one asset with the largest growth, discounted by fee, if it's another asset than the one you're holding 🤷 $\endgroup$ Commented Apr 8, 2023 at 19:54
  • $\begingroup$ Because it wouldn't recoup the fee on the very first day. Your don't check if the small profit, accumulated over several days, would pay off. $\endgroup$ Commented Apr 9, 2023 at 3:23
  • $\begingroup$ i see now what you mean. yes, i think you have a point. so there's an argument to be made for the dynamic programming approach after all. thanks for the hint! $\endgroup$ Commented Apr 9, 2023 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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