# Overview and Problem Description

Suppose I have a set of N discrete time-series (represented as a map from time-interval-index to value/utility), and I would like to identify a sequence of actions in a particular time interval that would yield the highest profit at the end of the interval (assuming there is a transaction cost T associated with selling your holdings in a given time series). Problem Inputs include (i) transaction cost (volume-independent fixed cost) , (ii) price tables of alternatives (indexed by time step), and the (iii) time interval in question. Problem Output is a sequence of tuples (timestep, decision type) that maximizes returns at the end of the interval. Valid decisions include buying and selling ones funds from one alternative to another at discrete time steps.

# Trivial Example

You have USD 1 in year 1 [Problem Input]. Given Stocks A and B prices in years 1, 2, and 3, determine the sequence of actions that will maximize your profit at the end of the interval [1, 3]. The transaction cost, independently of volume, is USD1 [Problem Input]. You can sell and buy into any time series by paying the transaction cost for the trade at any discrete time step.

Stock A [Problem Input]:
Year 1: USD 1
Year 2: USD 1.1
Year 3: USD 1.2

Stock B [Problem Input]:
Year 1: USD 1
Year 2: USD 1.2
Year 3: USD 0.9

Answer [Problem Output]: Buy Stock A in year 1.

Buying Stock B for the first year would result in a higher return from the stock itself. However, given the USD 1 transaction cost, it's better to hold Stock A.

# Question

I have a feeling this problem is well-studied. I can see how it would have a lot of applications, even though one usually does not have perfect information.

If I'm correct about my hunch, what is this problem called?

Of course you could just formulate this as an integer program, but I'm looking for a solution approach that's less 'naive' (if that even exists).

• Can you describe your problem in full? – Yuval Filmus Apr 29 '18 at 18:33
• Thanks for the suggestion, I'll add an example. – Wuschelbeutel Kartoffelhuhn Apr 29 '18 at 19:11
• Example is not the same as full problem description. It will help, but may be not enough. – Evil Apr 29 '18 at 19:15

## 1 Answer

This can be solved using dynamic programming. Note that the optimal solution never requires holding more than one type of stock at a time; if you sell a stock, then you might as well sell all of it, and before buying a stock you should sell all existing stock. This enables a nice solution using dynamic programming.

Here are the details. Let $A[i,s]$ denote the maximum value of your assets that can be achieved by the end of year $i$, denominated in dollars, if you are holding stock $s$ at the end of year. Then there is a simple recursive expression for $A[i,s]$ in terms of the values of the form $A[i-1,t]$, based on the idea that either you sell or buy at the start of year $i$:

\begin{align*} A[i,s] = \max(&A[i-1,s] V[i,s]/V[i-1,s],\\ &\max \{(A[i-1,t]/V[i-1,t] - C) V[i,s] : t \ne s\}), \end{align*}

where $V[i,s]$ denotes the price/value of stock $s$ at the end of year $i$ and $C$ denotes the fixed transaction cost. Now you can compute these values iteratively, by first computing $A[1,\cdot]$, then $A[2,\cdot]$, and so on. You can also keep track of which choice was optimal at each step and thereby reconstruct the sequence of transactions as well if you like.