Efficient way to maximise stock profits

Question

I got a message from my future self. Rather than a sports almanac, it contained minute-by-minute data for tomorrow's prices on a few select stocks. I want to use this to earn a bit of money. Is there an efficient way to decide when to sell and buy which stocks in order to maximize profits?

An example: Say I got the following price data: $$ \begin{array}{|c|rr|rr|rr|}\hline \text{Time}& \text{Company 1}&&\text{Company 2}&&\text{Company 3}\\ &\text{Sell}&\text{Buy}&\text{Sell}&\text{Buy}&\text{Sell}&\text{Buy}\\\hline 00:00:00&1.23&1.25&12.48&12.57&7.93&8.01\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\\ 23:59:59&1.03&1.12&15.93&15.97&10.30&10.39\\\hline \end{array} $$ Now, assuming we can actually buy and sell for these exact prices at the given times (which is an approximation), how can one most efficiently navigate these data to end the day with as much money as possible? Are there any known algorithms for these? What computational complexity do you get?

I think for the case of a single company I can do linear in the number of minutes: search forward for first local minimum of buy at $b_0$. Between there and the next time the buy price is lower ($b_1$), if there is ever a sell price higher than $b_0$, then buy at $b_0$, sell as high as you can before $b_1$, and if no sell price in that time interval is higher than $b_0$, then don't buy. Then continue searching for local buy minimums from $b_1$ onward.

But for more than one company I'm not even sure how I would systematically look for the optimal solution, other than full brute force. And that quickly becomes unwieldy and exponential. Is there a more efficient algorithm?

Specifics:

• I don't have to buy whole stocks. I can buy parts of one. Let's say any positive real number is valid, as long as I can afford it.
• No shorting. I can't sell stocks I haven't bought earlier in the day.
• I have to end up with money, not stocks. Sell before the day is over, at the latest using the $23:59:59$ prices.
• I can sell for a given sell price, and then buy for a buy price within the same minute.

Answer 1

This can be done in $O(nT)$ arithmetic operations (division, multiplication, and comparison) where $n$ is the number of companies and $T$ is the number of discrete times using an approach one could describe as dynamic programming. Index the companies by integers $0\leq i < n$ and the time steps as $0\leq t < T$. This answer assumes that we proceed in timesteps, at each of which we first have an opportunity to sell whatever stocks we like, then to buy whatever stocks we like at the given price, allowing all non-negative real numbers as quantities of stocks.

Let's define:

• $b(t,i)$ is the buy price of stock $i$ at time $t$.

• $s(t,i)$ is the sell price of stock $i$ at time $t$.

• $f(t,i)$ is the maximum amount of money we could end with if after time step $t$ we held one stock of company $i$ (and nothing else). Loosely speaking, this is the true value of stock $i$ at time $t$.

• $g(t)$ is the maximum amount of money we could end with if before time step $t$ we had one dollar (and nothing else). Loosely speaking, this is the true value of a dollar at time $t$.

We can then write equations relating these: first, for a stock, either we want to hold on to it for another step or sell it immediately: $$f(t,i)=\max\{f(t+1,i),\,g(t+1)\cdot s(t+1,i)\}.$$ Note that a mixed strategy of "sell some" never makes sense, as it would just average the two extremes in terms of pay-off - so no mixed strategy could be the maximum. Similarly, for $g(t)$, the non-mixed strategies are "buy all of one stock" or hold on to the dollar - so $$g(t)=\max\{g(t+1)\}\cup \left\{\frac{f(t,i)}{b(t,i)}:0\leq i < n\right\}$$ As edge cases, we also note $g(T)=1$ (as a dollar at the end is a dollar) and $f(T - 1,i)=0$ (as a stock at the end is useless).

Note that computing $f(t,i)$ only requires knowing evaluations of $g$ and $f$ at times of $t+1$ and later, and computing $g(t)$ only requires knowing $f(t,i)$ and the values of $g$ at a later time - so we can start from $t=T$ and work backwards until we compute $g(0)$, getting our answer of maximum amount we could earn. This requires $O(nT)$ operations to do - which is as fast as we possibly could get, given that there are $nT$ entries in the table to process.

We can extract the optimal strategy by seeing which branch of the maximum was used in each step - e.g. if the value of $g(0)$ is $\frac{f(0,17)}{b(0,17)}$, we know to buy stock $17$ and then if the value of $f(0,17)$ is $f(1,17)$, we know to hold on to the stock in time step $1$, but if $f(1,17)$ equals $g(2)\cdot s(2,17)$, we know to sell at time step $2$ - and then to look at what $g(2)$ equals for our next move.