Online Trading as a Secretary Problem Variant

Xujin Chen, Xiaodong Hu, Changjun Wang, Yuchun Xiong, Qingjie YearXiv 2026 · arXiv

TL;DR

This paper provides a complete characterization of Secretary Problem Variant Trading (SPVT), an online market-making problem where an intermediary must sequentially buy an item from a seller and sell it to a buyer. The authors close a long-standing theoretical gap by establishing a tight "strong" competitive ratio of $\approx 3.523$ and introduce novel threshold-based algorithms that significantly improve performance against a more realistic "weak" offline benchmark.

What Problem Does This Paper Address?

Imagine you are a middleman in an online asset market. A single seller and $n$ buyers arrive one by one in a completely random, unpredictable order. Each agent reveals their price valuation only upon arrival, and you must make an immediate, irrevocable decision: do you buy from the seller (if you don't have the item yet) or sell to a buyer (if you do)? Your goal is to maximize social welfare—ensuring the item ends up in the hands of the agent who values it most.

This setup is known as Secretary Problem Variant Trading (SPVT). It extends the classic secretary problem (where you just want to pick the single best candidate from a random sequence) to a two-sided trading environment.

The authors evaluate their algorithms using two types of offline benchmarks:

  1. Strong Offline Optimum: A powerful benchmark that assumes the offline player can always pick the absolute highest price among all $n+1$ agents, completely ignoring arrival order constraints.
  2. Weak Offline Optimum: A more realistic benchmark where the offline player knows all prices and the arrival order in advance but cannot change the order. They must still trade sequentially based on who arrives first.

Prior work left a significant gap between the upper and lower bounds for the strong competitive ratio, and the weak competitive ratio remained largely unexplored.

Methods

The authors employ a mix of continuous-time probability modeling, linear programming (LP) duality, and Ramsey theory to design and analyze three distinct online algorithms:

  • Algorithm 1 (Random Transaction for SPVT): Designed for the strong benchmark. It assigns independent random arrival times $T_i \in [0, 1]$ to agents. If the seller arrives after a critical threshold $(e-1)/e \approx 0.632$ and offers the highest price seen so far, the algorithm stops (leaving the item with the seller). Otherwise, it buys from the seller and uses a standard $1/e$ secretary threshold to find the best buyer.
  • Algorithm 2 (Simple Random Transaction): A straightforward randomized strategy for the weak benchmark. It buys from the seller with a 50% probability if the seller is the highest bidder so far, and subsequently sells to the highest-offering buyer.
  • Algorithm 3 (Double-Threshold Transaction): Tailored for the special case where the seller's price is zero. It introduces a secondary acceptance criterion: if a buyer arrives late in the game (after a second threshold $t_2$), the algorithm will accept them even if they are only the second-best-so-far.

To prove their lower bounds, the authors formulate the problem as a linear program. They use Ramsey’s theorem on infinite hypergraphs to mathematically justify restricting their search to "value-independent" strategies (algorithms that only care about relative ranks, not the absolute dollar values).

Datasets

Not discussed in the paper. This is a purely theoretical paper; the results are validated using analytical mathematical proofs and exact numerical calculations for asymptotic limits ($n \to \infty$).

Key Insights and Ideas

  • The Seller is Not Just a Fictitious Buyer: Previous literature often treated the seller as just another buyer to simplify the math. This paper points out a crucial asymmetry: the intermediary has full control over keeping the item with the seller (by refusing to buy), but lacks full control over selling it to the highest buyer. Exploiting this distinction was the key to unlocking the tight bounds.
  • The Value of the "Second Best": Under the weak offline benchmark, aiming strictly for the absolute best buyer can cause you to fail to sell entirely if that buyer happens to arrive too early. Algorithm 3 demonstrates that accepting the second-best candidate late in the process acts as an essential insurance policy, maximizing expected welfare.

Key Results

The paper successfully maps out the competitive landscape for SPVT, closing the gap for the strong competitive ratio and setting new baselines for the weak ratio.

Table 1: Summary of competitive ratios on the SPVT
  • Strong Benchmark Solved: The authors prove that Algorithm 1 achieves a strong competitive ratio of $\frac{4e^2}{e^2+1} \approx 3.523$, and prove via LP duality that no online algorithm can do better. This completely closes the previous gap of $[3.258, 4.189]$.
  • Weak Benchmark Progress: For general seller prices, Algorithm 2 achieves a weak competitive ratio of $2$. For a zero-price seller, the double-threshold approach (Algorithm 3) pushes the upper bound down to $1.83683$, coming remarkably close to the established lower bound of $1.76239$.

Limitations and Future Work

While this paper resolves the strong competitive ratio, a small gap remains for the weak competitive ratio (between $1.76239$ and $1.83683$ for the zero-price seller case, and a larger gap for general prices). The authors suggest that analyzing multi-threshold frameworks (e.g., using three or more time thresholds) could fully resolve the weak ratio, though the mathematical complexity increases drastically.

Additionally, the current model assumes a single seller with a single item. Real-world market-making involves inventory management across multiple items and multiple sellers, which represents an exciting open direction for future research.

Summary updated

Abstract

This paper studies an online trading variant of the classical secretary problem, called secretary problem variant trading (SPVT), from the perspective of an intermediary who facilitates trade between a seller and $n$ buyers (collectively referred to as agents). The seller has an item, and each buyer demands the item. These agents arrive sequentially in a uniformly random order to meet the intermediary, each revealing their valuation of the item upon arrival. After each arrival, the intermediary must make an immediate and irrevocable decision before the next agent appears. The intermediary's objective is to maximize the price of the agent who ultimately holds the item at the end of the process. We evaluate the performance of online algorithms for SPVT using two notions of competitive ratio: strong and weak. The strong notion benchmarks the online algorithm against a powerful offline optimum: the highest price among the $n+1$ agents. We propose an online algorithm for SPVT achieving a strong competitive ratio of $\frac{4e^2}{e^2+1} \approx 3.523$, which is the best possible even when the seller's price may be zero. This tight ratio closes the gap between the previous best upper bound of $4.189$ and lower bound of $3.258$. In contrast, the weak notion restricts the offline optimal algorithm to the given arrival order. The offline algorithm can no longer alter the predetermined arrival order to always place the item in the hands of the agent offering the highest price. Against this weaker benchmark, we design a simple online algorithm for SPVT, achieving a weak competitive ratio of $2$. We further investigate the special case in which the seller's price is zero. For this special SPVT, we develop a double-threshold algorithm achieving a weak competitive ratio of at most $1.83683$ and establish a lower bound of $1.76239$.
BibTeX
@misc{chen2026online,
  author = {Xujin Chen and Xiaodong Hu and Changjun Wang and Yuchun Xiong and Qingjie Ye},
  title = {{Online Trading as a Secretary Problem Variant}},
  year = {2026},
  eprint = {2604.15933},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2604.15933},
}

Loading related content...

Figure