PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Prophet Inequalities for Gain from Trade

Xujin Chen, Xiaodong Hu, Changjun Wang, Qingjie Ye

arXiv:2609.30742v1math.OCcs.DS

TL;DR

With known common i.i.d. prices and random arrivals, prophet trading requires online purchasing and selling under inventory constraints. The paper analyzes threshold algorithms through an exact inventory characterization, proving a best-possible general ratio of 2 and sharper guarantees in structured cases.

  • Problem

    Online trading must manage purchases, sales, and inventory while competing with a prophet who knows the realized order and prices.

    Source: §1 · pp. 1–2

  • Method

    A threshold algorithm is analyzed through an exact characterization expressing expected GFT using cumulative holding probability at buyer arrivals.

    Source: §1 · p. 2

  • Results

    2 is the best-possible general competitive ratio; balanced trading improves below 2, while adaptive single-seller thresholds approach e/(e −1) ≈1.58.

    Source: §1 · p. 2, §5 · p. 14

  • Takeaways & Limitations

    The inventory characterization supports sharper guarantees for balanced and single-sided trading settings.

    Source: §1 · p. 2, §5 · p. 14

    The results assume known common i.i.d. prices; sample-driven and non-i.i.d. extensions remain open directions.

    Source: §1 · p. 2, §5 · p. 14

Abstract

from arXiv · show

We initiate the study of prophet trading, an online trading model in which a trader interacts with sellers and buyers who arrive in a uniformly random order and whose prices are drawn independently from a common known distribution. The trader aims to maximize the expected gain from trade (GFT), with performance measured against an omniscient prophet that knows the realized arrival order and all prices in advance. Unlike the classical prophet inequality problem, the trader must make both purchasing and selling decisions while managing the inventory, which makes both the prophet benchmark and the analysis of online algorithms substantially more intricate. For arbitrary numbers of buyers and sellers, we propose a simple threshold-based algorithm and prove a distribution-free competitive ratio of~2, which is the best possible. Our main technical contribution is an exact characterization of the inventory process induced by threshold trading. By expressing the algorithm's expected GFT in terms of the cumulative holding probability at buyer arrivals, we derive an exact formula for this inventory term, which serves as the foundation of our analysis and yields sharper guarantees in several important special cases. For balanced trading (with $n$ sellers and $n$ buyers), we improve the competitive ratio to $(2n^2-n)/((n+4^{-n}-1)(n+1))$, which is strictly less than 2 for every $n>1$. For the single-seller case, we sharpen the analysis of the fixed-threshold algorithm to obtain an asymptotic competitive ratio of $2e^2/(e^2+1)\approx1.76$. Furthermore, by exploiting the additional structure of this setting, we design an adaptive-threshold algorithm whose competitive ratio approaches $e/(e-1)\approx 1.58$. Due to a symmetry property of our general algorithmic idea, the same $1.76$-competitive guarantee also holds for the single-buyer case.

1 Introduction

Prophet trading adds online purchasing and inventory management to the classical sell-once setting. The paper analyzes threshold algorithms and establishes optimal general guarantees, with sharper results for balanced and single-sided markets.

1 Introduction

  • Unlike classical prophet inequalities, trading requires purchases as well as sales, so inventory choices affect future opportunities and the prophet benchmark.The model has buyers and sellers arriving in uniformly random order, with prices drawn independently from a common known distribution.Source: §1 · pp. 1–2
  • A threshold algorithm achieves a distribution-free competitive ratio of 2 for arbitrary buyer and seller counts, which is best possible in general.The analysis uses a characterization of inventory through cumulative holding probability at buyer arrivals.Source: §1 · p. 2
  • Balanced trading has a competitive ratio strictly below 2 for every n > 1; fixed-threshold ratios for single-seller and single-buyer settings converge to about 1.76.The single-buyer guarantee follows from a symmetry property of the general bound.Source: §1 · p. 2
  • For a single seller, an adaptive threshold remains 2-competitive in the worst case and approaches e/(e −1) ≈1.58 as the number of buyers grows.The threshold depends on the seller’s arrival position.Source: §1 · p. 2
  • Earlier trading-prophet work established an optimal ratio of 2 for i.i.d. known prices, while secretary trading used a social-welfare benchmark that may exceed feasible welfare.In the present model, buyers and sellers are distinct, changing which trades are feasible and complicating inventory analysis.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the random-order trading market, the online decisions, and the prophet benchmark. They also specify the common known-distribution assumption, address ties at a threshold, and state a lower bound for the one-buyer, one-seller case.

2 Preliminaries

  • The market has n buyers and m sellers arriving in uniformly random order; their prices are independent draws from a common known nonnegative distribution with finite first moment.Price draws are independent of the arrival order.Source: §2 · p. 4
  • Each arriving agent reveals a price and receives an immediate, irrevocable trade decision; the trader can sell to a buyer only while holding an item.Sellers initially own one item, while buyers and the trader initially own none; each buyer demands one item.Source: §2 · p. 4
  • The prophet knows the realized order and prices before trading, while online and prophet performance are compared through their expected GFT.Expectations include arrival order, i.i.d. prices, and any algorithmic randomness.Source: §2 · p. 4
  • The common known-distribution assumption matters: unknown prices or distinct known buyer and seller distributions preclude a bounded competitive ratio in the cited settings.A one-buyer, one-seller example illustrates the difficulty when the distributions differ.Source: §2 · p. 5
  • For distributions with atoms, randomized tie-breaking classifies threshold-equal prices to attain an exact target quantile without changing actual prices or payoffs.A price equal to the threshold is classified below it with probability γ, chosen to achieve the target quantile p.Source: §2 · p. 5
  • With n = m = 1, any online algorithm can be forced to achieve at most E[OPT]/(2 −2ϵ) for some instance, for every ϵ ∈(0, 1/2).This carries over the ratio-2 lower bound from the related trading-prophet problem.Source: §2 · p. 5

3 General trading

The general analysis upper-bounds the prophet’s GFT using a relaxed charity model, then analyzes a threshold trader through its inventory process. The resulting algorithm is 2-competitive, matching the stated lower bound.

3.2 The threshold algorithm

  • Algorithm 1 is 2-competitive for arbitrary n and m, matching the lower bound of 2.Its threshold is chosen using P(X1 < T) = (n + 1)/(n + m + 2).Source: §3 · p. 5, §3.2 · pp. 6, 8

3.1 The prophet

  • The prophet’s GFT is upper-bounded by relaxing trades through an unlimited-supply charity, where eligible sellers below T and buyers above T can trade independently.Replacing a direct seller-to-buyer trade with two charity trades preserves its GFT contribution.Source: §3.1 · p. 6
  • The prophet benchmark is upper-bounded by counting charity trades available to eligible sellers and buyers in the arrival order.A seller is eligible when followed by a buyer, and a buyer when preceded by a seller.Source: §3.1 · p. 6

3.2 The threshold algorithm

  • The threshold trader buys below T only when holding no item, sells above T when holding one, and sells any remaining item to the last buyer.The purchase restriction is an algorithmic choice, not part of the problem definition.Source: §3.2 · pp. 6–7
  • Lemma 3.2 expresses the algorithm’s expected GFT using the cumulative probability of holding an item at buyer arrivals.This inventory characterization provides the key term used in the competitive-ratio analysis and later special-case refinements.Source: §3.2 · p. 7

4 Special cases

The special cases sharpen the general threshold analysis or use a specialized threshold rule. The balanced and fixed-threshold single-seller bounds are quantified, while the adaptive rule conditions its threshold on the seller’s position.

4 Special cases

  • The special cases considered are balanced trading and single-seller or single-buyer trading, where the general 2-competitive analysis can be sharpened or a specialized rule used.The paper identifies refined analysis and specialized threshold design as routes to stronger results in these settings.Source: §4 · p. 8

4.1 Balanced trading

  • The balanced-trading bound is (2n^2 - n)/((n + 4^-n - 1)(n + 1)).Figure 1 plots the refined competitive-ratio bound for balanced trading.Source: §4.1 · pp. 8–9, Figure 1 · p. 9

4.2.1 Fixed threshold

  • The fixed-threshold single-seller bound converges to 2e^2/(e^2 + 1), approximately 1.76, as n grows.For one seller, Algorithm 1 uses threshold quantile (n + 1)/(n + 3).Source: §4.2.1 · p. 10

4.2.2 Adaptive threshold

  • The adaptive single-seller threshold depends on how many buyers arrive before the seller.The rule sets its threshold quantile using that count; buyers arriving before the seller cannot trade and do not affect the offline optimum.Source: §4.2.2 · pp. 10–11

13 else

The adaptive-threshold algorithm is 2-competitive for single-seller trading, with a bound that improves as more buyers remain after the seller. The single-buyer case inherits the fixed-threshold result, but not the adaptive guarantee.

13 else

  • Conditional on seller arrival position k, the analysis reduces trading to one seller and q remaining buyers, using threshold T with P(Xi ≤T) = q/(q + 1).The q + 1 prices are symmetric random variables, but the objective remains GFT rather than selecting the maximum value.Source: §13 · pp. 11–12
  • Algorithm 2 is 2-competitive for the single-seller prophet trading problem; as q increases, the upper bound on the ratio decreases monotonically from 2 to e/(e −1) ≈1.58.Source: §13 · pp. 11–12

4.3 Single-buyer trading

  • The fixed-threshold result extends symmetrically to the single-buyer case, but the adaptive 1.58-competitive guarantee does not extend directly because its threshold depends on the seller’s arrival position.The paper attributes this boundary to the inherent asymmetry between seller and buyer roles.Source: §4.3 · p. 13

5 Conclusion

The paper gives a distribution-free 2-competitive threshold algorithm for arbitrary buyer and seller counts, then sharpens guarantees in balanced and single-sided markets. It identifies adaptive algorithms, sample-driven prices, and non-i.i.d. settings as open directions.

5 Conclusion

  • For arbitrary n buyers and m sellers, a threshold algorithm has competitive ratio at most 2 under i.i.d. known prices.Its threshold upper-bounds a price with probability (n + 1)/(n + m + 2).Source: §5 · p. 13
  • For balanced trading, the exact inventory term improves the competitive ratio to (2n2−n)/((n+4−n−1)(n+1)); an adaptive single-seller rule remains 2-competitive worst-case and reaches e/(e −1) asymptotically.The fixed-threshold single-seller and single-buyer ratios converge to 2e2/(e2 + 1).Source: §5 · p. 14
  • Open directions include history-adaptive decisions, sample-driven i.i.d. prices, non-i.i.d. settings under specified conditions, and matching lower bounds for special cases.The sample-driven setting gives the trader historical samples rather than the common distribution itself.Source: §5 · p. 14

A Lower bound proof

The lower-bound construction restricts the market to one buyer and one seller. In that setting, the prophet’s expected gain from trade exceeds the optimal online algorithm’s by a factor determined by ε.

A Lower bound proof

  • The construction considers exactly one buyer and one seller, with a probability 1/2 that the seller arrives before the buyer.The prophet’s expected GFT is ε − ε2.Source: A Lower bound proof · p. 17
  • In this construction, E[OPT] = (2 −2ϵ)E[ALG].The relation follows from the stated expected GFTs for the prophet and online algorithm.Source: A Lower bound proof · p. 17
  • The optimal online algorithm achieves expected GFT ε/2, since trade is possible only when the seller arrives first and the buyer second.At seller price 0 it buys; at price 2 it does not; at price 1 either choice yields zero expected GFT.Source: A Lower bound proof · p. 17

B Proof of Lemma 3.2

The appendix derives holding probabilities from the algorithm’s transitions, then uses an inventory conservation identity to prove the expected-GFT expression in Lemma 3.2. The proof proceeds by induction over buyer arrivals.

B Proof of Lemma 3.2

  • Algorithm 1 updates holding probability according to whether an arrival is a seller, an intermediate buyer, or the last buyer.A seller can be purchased from when inventory is empty; an intermediate buyer sale occurs above T, while the last buyer clears any held item regardless of price.Source: B Proof of Lemma 3.2 · p. 17
  • For a fixed arrival order, the proof establishes a conservation identity equating expected sales behavior with expected purchase behavior through the holding probabilities.The proof defines Sσ as sellers arriving before the last buyer and proceeds by induction on the number of buyers processed.Source: B Proof of Lemma 3.2 · p. 18
  • The induction step matches the buyer-side term with the sum over intervening sellers using the recurrence and a geometric sequence.The base case is n = 1, and the two sides match after the factor ρ cancels with 1 −¯ρ.Source: B Proof of Lemma 3.2 · pp. 18–19
  • Lemma 3.2 uses the conditional independence of inventory status and the current price, together with the conservation identity, to obtain the expected-GFT expression.Zi indicates whether the trader holds an item immediately before agent i is processed.Source: B Proof of Lemma 3.2 · p. 19

C Proof of Lemma 3.3

The proof reduces the buyer-side sum to an exact inventory and arrival-order expression, then bounds its integral to obtain a lower bound on the aggregate term.

C Proof of Lemma 3.3

  • The expected deficit is rewritten as a sum over buyer-index gaps, whose seller counts have the same distribution as J_r by exchangeability of the arrival gaps.For each fixed gap length r, there are n−r buyer-index pairs; the proof uses the exchangeable seller counts in the n+1 gaps.Source: C Proof of Lemma 3.3 · p. 20
  • The proof computes E[ρ̄^J_i] by conditioning on the i-th buyer's arrival time, since J_i is binomial conditional on that time.It then averages over the order statistic's density to obtain the claimed integral formula.Source: C Proof of Lemma 3.3 · pp. 20–21
  • A binomial-theorem identity and integration by parts reduce the remaining sum to a boundary term of 1 and the integral −K_n,m.The boundary values are G(1)=0 and G(0)=−1.Source: C Proof of Lemma 3.3 · p. 21
  • The summed buyer-side quantity is at least nm/[2(m+1)], using a lower bound on K_n,m.The proof obtains the bound by applying a power inequality to the factors in the integral and substituting the definitions of ρ and ρ̄.Source: C Proof of Lemma 3.3 · p. 22
Loading 2609.30742v1…