Asymmetric Trading Prophets
Abstract
The ``Trading Prophet'' problem challenges an online trader to maximize its profit by buying and selling assets under storage constraints and stochastic prices, competing against an offline prophet with full foresight. In previous work, each arriving asset was assumed to have a single price $p_t$, and the trader was allowed to either buy a copy at this price (subject to having the capacity), or sell a copy if it already held at least one copy in hand. However, this abstraction fails to capture the structural asymmetry of decentralized dealer-based markets, where buying and selling opportunities could be distinct, and driven by individual preferences. To address this, we introduce the \emph{Asymmetric Trading Prophets} problem, where at each timestep the trader observes a price tuple $(b_t, s_t)$---representing the cost to buy and revenue from selling at this timestep---where the $(b_t,s_t)$ tuple could be potentially arbitrarily correlated.
We provide the first competitive analysis for this asymmetric trading prophets problem, characterizing the achievable profit based on the trader's capacity $B$ and initial inventory $B_0$. For the unit-capacity case of $B=1$, we design online algorithms that achieve constant competitive ratios for both the i.i.d.\ and non-i.i.d.\ request distributions, when the trader has one initial copy ($B_0=1$). For the general capacity case where $B$ can be large, we construct algorithms for i.i.d.\ distributions that achieve a competitive ratio of $1 - \widetilde\Theta(1/\sqrt{B_0})$. Finally, for the symmetric case (where the price tuple satisfies $b_t=s_t$), we improve this to get a tight competitive ratio of $1 - \widetilde\Theta(1/\sqrt{B})$, demonstrating that the performance approaches optimality as the capacity increases. We show that both ratios are tight up to a polylogarithmic factor.
We provide the first competitive analysis for this asymmetric trading prophets problem, characterizing the achievable profit based on the trader's capacity $B$ and initial inventory $B_0$. For the unit-capacity case of $B=1$, we design online algorithms that achieve constant competitive ratios for both the i.i.d.\ and non-i.i.d.\ request distributions, when the trader has one initial copy ($B_0=1$). For the general capacity case where $B$ can be large, we construct algorithms for i.i.d.\ distributions that achieve a competitive ratio of $1 - \widetilde\Theta(1/\sqrt{B_0})$. Finally, for the symmetric case (where the price tuple satisfies $b_t=s_t$), we improve this to get a tight competitive ratio of $1 - \widetilde\Theta(1/\sqrt{B})$, demonstrating that the performance approaches optimality as the capacity increases. We show that both ratios are tight up to a polylogarithmic factor.
