pith. sign in

arxiv: 2604.15933 · v1 · submitted 2026-04-17 · 🧮 math.OC · cs.DS

Online Trading as a Secretary Problem Variant

Xujin Chen , Xiaodong Hu , Changjun Wang , Yuchun Xiong , Qingjie Ye This is my paper

Pith reviewed 2026-05-10 07:54 UTC · model grok-4.3

classification 🧮 math.OC cs.DS
keywords secretary problemonline algorithmscompetitive ratioonline tradingrandom-order modelintermediaryirrevocable decisions
0
0 comments X

The pith

An online algorithm for the secretary problem variant trading secures a tight strong competitive ratio of 4e²/(e²+1) ≈ 3.523.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines how an intermediary can decide immediately and irrevocably whether to assign an item to each arriving buyer or keep it available, as agents with private valuations appear in random order. The aim is to maximize the final price paid by whoever ends up holding the item. The authors construct an algorithm whose expected performance is at least one over 3.523 of the best possible price among all agents including the seller, and they prove no online algorithm can guarantee better than this factor even when the seller's valuation is zero. This closes a longstanding gap between earlier upper and lower bounds on the strong competitive ratio. The result also includes a simple algorithm with weak competitive ratio 2 and improved bounds for the zero-seller-price special case.

Core claim

For the secretary problem variant trading (SPVT) in which an intermediary must assign an indivisible item to one of n+1 randomly arriving agents to maximize the realized price, there exists an online algorithm whose strong competitive ratio against the global maximum valuation is exactly 4e²/(e²+1) ≈ 3.523; this ratio is tight and remains so when the seller's valuation may be zero.

What carries the argument

A threshold-based decision rule that, upon each arrival, compares the revealed valuation against carefully chosen time-dependent thresholds derived from the target ratio to decide whether to transfer the item.

Load-bearing premise

Agents arrive in a uniformly random order.

What would settle it

An explicit online algorithm for SPVT that achieves a strong competitive ratio strictly better than 4e²/(e²+1) on all instances where the seller's price can be zero, or a matching lower-bound instance showing some online algorithm must incur a worse ratio.

read the original 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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper studies secretary problem variant trading (SPVT), an online problem in which an intermediary facilitates trade between one seller and n buyers who arrive in uniformly random order. Each agent reveals a valuation upon arrival, and the intermediary must make an irrevocable decision to assign the item so as to maximize the final price paid by the agent who ends up holding it. The authors distinguish strong competitive ratio (benchmark: maximum valuation among all n+1 agents) from weak competitive ratio (benchmark: offline optimum that respects the given arrival order). They present an online algorithm achieving strong ratio 4e²/(e²+1)≈3.523, claimed to be tight even when the seller’s price may be zero, thereby closing the prior gap between 4.189 and 3.258. They also give a simple algorithm with weak ratio 2 and, for the zero-seller-price special case, a double-threshold algorithm with weak ratio at most 1.83683 together with a matching lower bound of 1.76239.

Significance. If the claimed tight strong competitive ratio holds, the result supplies the first optimal guarantee for this natural online trading model and improves the state of the art by a non-trivial margin. The explicit matching upper and lower bounds, the parameter-free character of the ratio, and the clean separation between strong and weak benchmarks are all strengths that advance the literature on secretary problems and online algorithms. The random-order assumption is standard for the domain and enables the competitive-ratio analysis.

major comments (2)
  1. [Strong competitive ratio section (around the statement of the main theorem)] The abstract asserts that 4e²/(e²+1) is the best possible even when the seller’s price may be zero. The lower-bound construction that establishes this (presumably in the section containing the strong-ratio analysis) must be checked to confirm it does not inadvertently assume a positive seller price; any such assumption would weaken the tightness claim.
  2. [Lower-bound argument for strong ratio] The derivation of the exact constant 4e²/(e²+1) relies on a specific threshold rule whose optimality is asserted. The proof that no online algorithm can beat this ratio (even for zero seller price) should be examined for the precise worst-case instance used; the previous lower bound of 3.258 suggests the new construction is tighter, but the improvement must be explicit.
minor comments (2)
  1. [Abstract] The abstract states numerical approximations (≈3.523, 1.83683, 1.76239) but does not indicate how many decimal places are guaranteed by the analysis; adding a parenthetical remark on rounding would improve precision.
  2. [Introduction / Preliminaries] The distinction between strong and weak competitive ratios is introduced in the abstract but would benefit from an early formal definition (e.g., in the preliminaries) that explicitly writes the ratio as sup (OPT / ALG) over all instances.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and recommendation for minor revision. Below we address the major comments on the strong competitive ratio and its claimed tightness for the zero-seller-price case.

read point-by-point responses

  1. Referee: The abstract asserts that 4e²/(e²+1) is the best possible even when the seller’s price may be zero. The lower-bound construction that establishes this (presumably in the section containing the strong-ratio analysis) must be checked to confirm it does not inadvertently assume a positive seller price; any such assumption would weaken the tightness claim.

    Authors: The lower-bound construction used to establish tightness of 4e²/(e²+1) explicitly sets the seller's valuation to zero. The adversarial instance consists of one seller with value 0 and n buyers whose values are drawn from a continuous distribution chosen so that, under random arrival order, every online algorithm is forced to a ratio of at most 4e²/(e²+1) in the limit. No positive seller price is assumed anywhere in the argument; the same construction was already used to close the gap from the prior lower bound of 3.258. revision: no

  2. Referee: The derivation of the exact constant 4e²/(e²+1) relies on a specific threshold rule whose optimality is asserted. The proof that no online algorithm can beat this ratio (even for zero seller price) should be examined for the precise worst-case instance used; the previous lower bound of 3.258 suggests the new construction is tighter, but the improvement must be explicit.

    Authors: The matching lower bound is obtained from the explicit worst-case instance described above (seller value 0 together with a suitably parameterized buyer-value distribution). This instance is strictly stronger than the one yielding 3.258 because it optimizes the threshold parameters to match the upper bound achieved by our online algorithm, rather than using a coarser discretization. The derivation therefore shows that the threshold rule is optimal even when the seller price may be zero. We are happy to insert a short clarifying paragraph that contrasts the new instance with the earlier 3.258 construction. revision: partial

Circularity Check

0 steps flagged

No significant circularity in competitive ratio derivation

full rationale

The paper's central result is the design of an online algorithm for SPVT together with a matching upper and lower bound on its strong competitive ratio of 4e²/(e²+1) against the offline optimum (maximum valuation among seller and buyers). This ratio is obtained via standard worst-case analysis in the random-order arrival model, using explicit threshold-based decisions and adversarial input constructions that are independent of the algorithm definition itself. No load-bearing step reduces by construction to a fitted parameter, self-referential definition, or self-citation chain; the lower bound holds even for the special case of zero seller price and is established separately from the algorithm's performance guarantee. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard domain assumption of uniform random arrival order from the secretary problem literature and the framework of competitive analysis; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Agents arrive in a uniformly random order
    Invoked to analyze expected performance and derive competitive ratios; standard in secretary problem variants.

pith-pipeline@v0.9.0 · 5651 in / 1300 out tokens · 27133 ms · 2026-05-10T07:54:43.808336+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    Alaei, S.: Bayesian combinatorial auctions: expanding single buyer mechanisms to many buyers. SIAM J. Comput.43(2), 930–972 (2014)

    work page 2014

  2. [2]

    Arnosti, N., Ma, W.: Tight guarantees for static threshold policies in the prophet secretary problem. Oper. Res.71(5), 1777–1788 (2023)

    work page 2023

  3. [3]

    In: APPROX-RANDOM

    Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: APPROX-RANDOM. p. 16–28. Springer-Verlag, Berlin, Heidelberg (2007)

    work page 2007

  4. [4]

    Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Matroid secretary problems. J. ACM65(6), 35 (2018)

    work page 2018

  5. [5]

    In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

    Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mech- anisms. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 434–443. ACM, New York (2007) 17

    work page 2007

  6. [6]

    In: Proceedings of the Fifteenth ACM Conference on Economics and Computation (EC)

    Blumrosen, L., Dobzinski, S.: Reallocation mechanisms. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation (EC). p. 617 (2014)

    work page 2014

  7. [7]

    In: Web and Internet Economics (WINE)

    Blumrosen, L., Mizrahi, Y.: Approximating gains-from-trade in bilateral trading. In: Web and Internet Economics (WINE). pp. 400–413 (2016)

    work page 2016

  8. [8]

    Bruss, F.T.: A unified approach to a class of best choice problems with an unknown number of options. Ann. Probab.12(3), 882–889 (1984)

    work page 1984

  9. [9]

    In: Proceedings of the 24th ACM Conference on Economics and Computation (EC)

    Bubna, A., Chiplunkar, A.: Prophet inequality: Order selection beats random order. In: Proceedings of the 24th ACM Conference on Economics and Computation (EC). pp. 302–

    work page

  10. [10]

    Association for Computing Machinery, New York, NY, USA (2023)

    work page 2023

  11. [11]

    Buchbinder, N., Jain, K., Singh, M.: Secretary problems via linear programming. Math. Oper. Res.39(1), 190–206 (2014)

    work page 2014

  12. [12]

    Discrete Appl

    Chen, X., Hu, X., Wang, C., Wu, X., Zhang, M.: Algorithms for maximum social welfare of online random trading. Discrete Appl. Math.354, 229–240 (2024)

    work page 2024

  13. [13]

    prophet inequality

    Correa, J., Cristi, A., Epstein, B., Soto, J.A.: Sample-driven optimal stopping: From the secretary problem to the i.i.d. prophet inequality. Math. Oper. Res.49(1), 441–475 (2023)

    work page 2023

  14. [14]

    Correa, J., D¨ utting, P., Fischer, F., Schewior, K.: Prophet inequalities for independent and identically distributed random variables from an unknown distribution. Math. Oper. Res. 47(2), 1287–1309 (2022)

    work page 2022

  15. [15]

    In: Proceedings of the 2017 ACM Conference on Economics and Computation (EC)

    Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Posted price mecha- nisms for a random stream of customers. In: Proceedings of the 2017 ACM Conference on Economics and Computation (EC). pp. 169–186 (2017)

    work page 2017

  16. [16]

    Correa, J., Saona, R., Ziliotto, B.: Prophet secretary through blind strategies. Math. Pro- gram.190(1-2, Ser. A), 483–521 (2021)

    work page 2021

  17. [17]

    In: Proceedings of the 24th ACM Conference on Economics and Computation (EC)

    Correa, J.R., Cristi, A., Duetting, P., Hajiaghayi, M., Olkowski, J., Schewior, K.: Trading prophets. In: Proceedings of the 24th ACM Conference on Economics and Computation (EC). pp. 490–510 (2023)

    work page 2023

  18. [18]

    In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Sympo- sium on Discrete Algorithms (SODA)

    Ehsani, S., Hajiaghayi, M., Kesselheim, T., Singla, S.: Prophet secretary for combinatorial auctions and matroids. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Sympo- sium on Discrete Algorithms (SODA). pp. 700–714. SIAM, Philadelphia, PA (2018)

    work page 2018

  19. [19]

    Sci.4(3), 282–296 (1989)

    Ferguson, T.S.: Who solved the secretary problem? Statist. Sci.4(3), 282–296 (1989)

    work page 1989

  20. [20]

    Gilbert, J.P., Mosteller, F.: Recognizing the maximum of a sequence. J. Amer. Statist. Assoc.61, 35–73 (1966)

    work page 1966

  21. [21]

    In: Proceedings of the 22nd National Conference on Artificial Intelli- gence (AAAI)

    Hajiaghayi, M.T., Kleinberg, R., Sandholm, T.: Automated online mechanism design and prophet inequalities. In: Proceedings of the 22nd National Conference on Artificial Intelli- gence (AAAI). pp. 58–65 (2007)

    work page 2007

  22. [22]

    random variables

    Hill, T.P., Kertz, R.P.: Comparisons of stop rule and supremum expectations of i.i.d. random variables. Ann. Probab.10(2), 336–345 (1982)

    work page 1982

  23. [23]

    In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

    Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 630–631. ACM, New York (2005)

    work page 2005

  24. [24]

    In: Proceedings of the 2012 ACM Symposium on Theory of Computing (STOC)

    Kleinberg, R., Weinberg, S.M.: Matroid prophet inequalities. In: Proceedings of the 2012 ACM Symposium on Theory of Computing (STOC). pp. 123–135. ACM, New York (2012)

    work page 2012

  25. [25]

    In: Algorithmic game theory, Lecture Notes in Comput

    Koutsoupias, E., Lazos, P.: Online trading as a secretary problem. In: Algorithmic game theory, Lecture Notes in Comput. Sci., vol. 11059, pp. 201–212. Springer, Cham (2018)

    work page 2018

  26. [26]

    Krengel, U., Sucheston, L.: Semiamarts and finite values. Bull. Amer. Math. Soc.83(4), 745–747 (1977) 18

    work page 1977

  27. [27]

    In: Probability on Banach spaces, Adv

    Krengel, U., Sucheston, L.: On semiamarts, amarts, and processes with finite value. In: Probability on Banach spaces, Adv. Probab. Related Topics, vol. 4, pp. 197–266. Dekker, New York (1978)

    work page 1978

  28. [28]

    ACM Comput

    Li, B., Hoi, S.C.H.: Online portfolio selection: A survey. ACM Comput. Surv.46(3), No. 35 (2014)

    work page 2014

  29. [29]

    Lindley, D.V.: Dynamic programming and decision theory. Appl. Statist.10, 39–51 (1961)

    work page 1961

  30. [30]

    Myerson, R.B., Satterthwaite, M.A.: Efficient mechanisms for bilateral trading. J. Econom. Theory29(2), 265–281 (1983)

    work page 1983

  31. [31]

    In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)

    Peng, B., Tang, Z.G.: Order selection prophet inequality: From threshold optimization to arrival time design. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). pp. 171–178 (2022)

    work page 2022

  32. [32]

    Ramsey, F.P.: On a problem of formal logic. Proc. London Math. Soc.30, 264–285 (1930)

    work page 1930

  33. [33]

    Samuel-Cahn, E.: Comparison of threshold stop rules and maximum for independent non- negative random variables. Ann. Probab.12(4), 1213–1216 (1984) 19 A Proof of Lemma 3.3 The following lemma shows that it suffices to focus on order-oblivious algorithms. Lemma A.1.Given any algorithmALGfor the SPVT, there exists an order-oblivious algorithm ALG′ such that...

    work page 1984

  34. [34]

    , Xi−1 arrive after timet(this ensures thatX i is the current highest bidder)

    All buyersX 1, . . . , Xi−1 arrive after timet(this ensures thatX i is the current highest bidder)

    work page

  35. [35]

    AmongX i+1, . . . , Xn, either: •all arrive after timet, or exactly one buyer among them arrives before max{s, t 1}, or •at least two buyers arrive before timet, with the highest bidder among them arriving before max{s, t1}and the second-highest bidder arriving before max{s, t 2}. (These ensure thatX i is the first best-so-far bidder after timet 1) Case 2...

    work page

  36. [36]

    , Xi−1, exactly one buyer arrives before max{s, t1}, while all remaining ones arrive after timet

    AmongX 1, . . . , Xi−1, exactly one buyer arrives before max{s, t1}, while all remaining ones arrive after timet

    work page

  37. [37]

    , Xn arrive after timet; or there exists at least one buyer among them arriving before timet, with the highest bidder among these early arrivals arriving before max{s, t2}

    All buyersX i+1, . . . , Xn arrive after timet; or there exists at least one buyer among them arriving before timet, with the highest bidder among these early arrivals arriving before max{s, t2}. (These ensure thatX i is the first second-best-so-far bidder after timet 2); 3)t≥t 2. Letp ALG i1 be the probability of obtainingX i under Case 1. Since the rela...

    work page

  38. [38]

    Furthermore, numerical computation shows thatM11(i)≥M 11(9) for alli= 3, . . . ,9. And whenn >⌈ 2 t1 ⌉−1 = 6, we have M11(n−1) = Z t1 0 ds Z t2 t1 t1 t (n−1)n(1−t) n−2 −n(n+ 1)(1−t) n−1 dt > Z t1 0 ds Z t2 t1 2n 1− t1 t (1−t) n−1 dt =M 12(n−1, n). Thus, by settingN 1 = max{10,6}= 10 andI 1 = 3, for alln > N 1 andI 1 ≤i < n, we have M11(i)≥M 11(n−1)> M 12(...

    work page

  39. [39]

    ,9, we find thatM 21(i) actually decreases from 3, which means that for all 3≤i≤n−1,M 21(i)≥M 21(n−1)

    Supplement- ing this with numerical computations fori= 1, . . . ,9, we find thatM 21(i) actually decreases from 3, which means that for all 3≤i≤n−1,M 21(i)≥M 21(n−1). And whenn > maxt∈[s,t2],s∈[t1,t2]⌈ 2 s − 2t s ⌉+ 1 =⌈ 2 t1 ⌉ −1 = 6, we have M21(n−1) = Z t2 t1 ds Z t2 s s t (n−1)n(1−t) n−2 −n(n+ 1)(1−t) n−1 dt > Z t2 t1 ds Z t2 s 2n 1− s t (1−t) n−1 dt ...

    work page