Abstract
The "Trading Prophet" problem challenges an online trader to maximize its profit by buying and selling assets under stochastic prices and capacity constraints, 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 available capacity), or sell a copy (if it already held at least one copy in hand). However, this abstraction can fail 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 Asymmetric Trading Prophets problem, where at each timestep the trader observes a price tuple $(b_t, s_t)$ — representing the cost to buy and the revenue from selling at this timestep. Importantly, 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 i.i.d. and non-i.i.d. distributions on the price tuples, when the trader has one initial copy ($B_0=1$). For the general capacity case where $B$ can be large, we give algorithms for i.i.d. distributions that achieve a competitive ratio of $1 - \Theta(\log B_0/\sqrt{B_0})$. Finally, for the symmetric case (where the price tuple satisfies $b_t=s_t$), we improve this to get a competitive ratio of $1 - O(\log B/\sqrt{B})$, demonstrating that the performance approaches optimality as the capacity increases. We show that both ratios are tight up to a logarithmic factor.
Blogger's Review: This research provides a new perspective in the field of online trading, particularly by introducing price tuples to reflect the true dynamics of the market, breaking through the limitations of traditional models. The competitive ratio analysis of the algorithms demonstrates the close relationship between theory and practical application, holding significant academic and practical value.