How Much Can You Earn in the Stock Market ? Answers from the Algorithmic Graph Theory

This paper proposes a new method for determining the upper bound of any investment strategy's maximum profit, applied in a given time window [0, T]. This upper bound is defined once all the prices are known at time T and therefore represents the ex-post maximum efficiency of any investment strategy determined during the relevant time interval. This approach allows us to gauge in absolute terms those behaviors defined through atomic "buy" and "sell" actions, and can be extended to more complex strategies. We show that, even in the ex-post framework, establishing this upper bound when transaction costs are implemented is extremely complex. We first describe this problem using a linear programming framework. Thereafter, we propose to embed this question in a graph theory framework and to show that determining the best investment behavior is equivalent to identifying an optimal path in an oriented, weighted, bipartite network or a weighted, directed, acyclic graph. We illustrate this method using real world data and introduce a new theory about absolute optimal behavior in the financial world