Asymmetric Trading Prophets

Gagan Aggarwal, Anupam Gupta, Yifan Wang, Mingfei ZhaoarXiv 2026 · arXiv

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:

  1. 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$).
  2. 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.
  3. 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.
  4. 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:

Achievable competitive ratios for the asymmetric trading prophet problem.
  • 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

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 - Θ(\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.
BibTeX
@misc{aggarwal2026asymmetric,
  author = {Gagan Aggarwal and Anupam Gupta and Yifan Wang and Mingfei Zhao},
  title = {{Asymmetric Trading Prophets}},
  year = {2026},
  eprint = {2607.01516},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.01516},
}

Loading related content...

Figure