TL;DR
This paper introduces and analyzes the Asymmetric Trading Prophet (ATP) problem, generalizing classic online trading models to decentralized markets where buying and selling prices are distinct and arbitrarily correlated. The authors prove that while trading with zero initial inventory yields a competitive ratio of zero, introducing initial inventory allows online algorithms to achieve constant competitive ratios that approach absolute optimality as market capacity grows.
What Problem Does This Paper Address?
Imagine a used car dealer acting as a market maker. The price at which they buy a car from a motivated seller is often completely decoupled from the price a collector is willing to pay for it later that day.
Traditional "Trading Prophet" models assume a symmetric market with a single exogenous price $p_t$ at any time step $t$, where a trader can either buy or sell at that exact price. While this abstraction fits centralized stock exchanges perfectly, it fails to capture the structural asymmetry of dealer-based or decentralized markets.
To bridge this gap, the authors introduce the ATP problem. At each time step, the trader observes a price tuple $(b_t, s_t)$ representing distinct, potentially highly correlated costs to buy and revenues from selling. This asymmetry introduces a major mathematical challenge: a trader's optimal decision today depends heavily on the entire remaining suffix of future arrivals (e.g., "Should I sell my inventory now, or will I be able to replenish it cheaply later?").
Methods
To overcome the long-range dependencies caused by price asymmetry, the authors move away from localized threshold strategies and leverage linear programming relaxations:
- Linear Programming (LP) Relaxation: The authors construct an LP framework that interprets the optimal offline prophet's decisions as a collection of fractional trades (buying at request $i$ and selling at request $j$).
- Uncrossing Technique: To make the fractional solution manageable, they apply an "uncrossing" algorithm. This refines the LP solution into a structured "first buy, first sell" policy without reducing the overall objective value.
- Interval Decomposition & OCRS: For the unit-capacity case ($B=1$), the refined LP solution is decomposed into disjoint time intervals containing a bounded number of fractional trades. They then deploy an Online Contention Resolution Scheme (OCRS) to round these fractional blocks into valid, real-time trading actions.
- Randomized Rounding with Inventory Clearing: For large capacities ($B > 1$), they utilize a time-independent LP relaxation combined with an independent rounding scheme. Crucially, they augment this with a "sell-only" strategy near the end of the trading horizon to clear remaining inventory and capture latent profit.
Datasets
Not discussed in the paper. As a purely theoretical computer science paper, the algorithms and bounds are evaluated and validated using rigorous mathematical proofs and competitive analysis rather than empirical datasets.
Key Insights and Ideas
- The Zero-Inventory Trap: In symmetric trading environments, constant competitive ratios are achievable even if you start with nothing. In asymmetric markets, starting with zero inventory ($B_0 = 0$) drops the achievable competitive ratio to zero. Without an initial buffer, an online trader cannot risk buying an asset because they cannot guarantee a viable selling opportunity will ever arrive.
- Breaking Locality: Price asymmetry fundamentally breaks the "locality" of online trading decisions. Online algorithms must account for global future possibilities, which justifies the use of global LP relaxations over simple greedy thresholds.
- Asymptotic Optimality: For large capacities, the trading process behaves like a stabilized random walk. As capacity ($B$) and initial inventory ($B_0$) scale up, the fraction of "blocked" trades (buys blocked by full capacity or sales blocked by empty inventory) becomes negligible, allowing the online algorithm to approach the performance of an omniscient offline prophet.
Key Results
The paper maps out the first comprehensive competitive landscape for asymmetric trading prophets, summarized in the table below:
- Unit-Capacity ($B=1, B_0=1$): The authors design a 22-competitive algorithm for non-I.I.D. general distributions and improve this to a 4-competitive algorithm when price distributions are identical (I.I.D.).
- Large Capacity ($B > 1, B_0 \ge 1$): For general I.I.D. distributions, they achieve a competitive ratio of $1 - O(\log B_0/\sqrt{B_0})$. For the symmetric case ($b_t = s_t$), this improves to $1 - O(\log B/\sqrt{B})$, proving that performance converges to optimality as capacity increases. Both bounds are shown to be tight up to a logarithmic factor.
Limitations and Future Work
While this work provides a solid foundation for asymmetric online trading, a few open problems remain:
- Large Capacity Non-I.I.D. Settings: The near-optimal bounds for large capacities are currently restricted to I.I.D. price distributions. Extending these results to non-I.I.D. settings remains a challenging open direction.
- Tightening the Bounds: For the unit-capacity, non-I.I.D. general case, there is still a significant gap between the authors' 22-competitive upper bound and the known lower bound of 3.
Summary updated