Trading Prophets: How to trade multiple stocks optimally

Speaker: Surbhi Rajput, MSR Student, CSE Dept., IIT Delhi

Abstract:

In the (single stock) \emph{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. Correa et al.\ showed that the
optimal competitive ratio for this problem is $\nicefrac{1}{2}$ when the
stock prices are identically and independently distributed.
In this talk, I will discuss the simplifications and generalizations of
Correa et al.'s analysis, which led us to generalize the model by allowing
the algorithm to trade multiple stocks. First, we generalize the model to
$(k,\ell, \ell')$-\textsc{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')$-\textsc{Trading Prophet Problem} is
$\min\left\{\frac{1}{2},\frac{\ell}{k}\right\}$.
We further generalize it to $\mathcal{M}$-\textsc{Trading Prophet Problem}
over a matroid $\mathcal{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 $\frac{1}{1+d}$ on the competitive ratio
of the $\mathcal{M}$-\textsc{Trading Prophet Problem}, where $d$ is the
\textit{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 $\frac{1}{1+d} - \mathcal{O}
\left(\frac{1}{n} \right)$, where $d$ is the density of the matroid,
matching the hardness result for i.i.d.\ instances as $n$ approaches
$\infty$.
Our analysis of the above problems is based on the following key insights.
First, any algorithm can be simulated by one that, on each time step, sells
\emph{all} its currently held stocks before buying a suitable subset of
stocks. Second, we prove that the general problem reduces to a restriction
where the expected price of every stock is zero.
Third, we reduce the problem in the random order non-i.i.d.\ setting to the
i.i.d. setting by leveraging the fact that the outcome of sampling two
objects without replacement from a large set is almost identically
distributed as the outcome of sampling with replacement.