Trading Prophets: How to Trade Multiple Stocks Optimally

In the single stock trading prophet problem formulated by Correa et al.\ (2023), an online algorithm observes a sequence of prices of a stock. At each step, the algorithm can either buy the stock by paying the current price if it doesn't already hold the stock, or it can sell the currently held stock and collect the current price as a reward. The goal of the algorithm is to maximize its overall profit. In this work, we generalize the model and the results of Correa et al.\ by allowing the algorithm to trade multiple stocks. First, we formulate the $(k,\ell,\ell')$-Trading Prophet Problem, wherein there are $k$ stocks in the market, and the online algorithm can hold up to $\ell$ stocks at any time, where $\ell\leq k$. The online algorithm competes against an offline algorithm that can hold at most $\ell'\leq\ell$ stocks at any time. Under the assumption that prices of different stocks are independent, we show that, for any $\ell$, $\ell'$, and $k$, the optimal competitive ratio of $(k,\ell,\ell')$-Trading Prophet Problem is $\min(1/2,\ell/k)$. We further introduce the more general $\cal{M}$-Trading Prophet Problem over a matroid $\cal{M}$ on the set of $k$ stocks, wherein the stock prices at any given time are possibly correlated (but are independent across time). The algorithm is allowed to hold only a feasible subset of stocks at any time. We prove a tight bound of $1/(1+d)$ on the competitive ratio of the $\cal{M}$-Trading Prophet Problem, where $d$ is the density of the matroid. We then consider the non-i.i.d.\ random order setting over a matroid, wherein stock prices drawn independently from $n$ potentially different distributions are presented in a uniformly random order. In this setting, we achieve a competitive ratio of at least $1/(1+d)-\cal{O}(1/n)$, where $d$ is the density of the matroid, matching the hardness result for i.i.d.\ instances as $n$ approaches $\infty$.