pith. sign in

arxiv: 2605.16601 · v1 · pith:R3VRS2G4new · submitted 2026-05-15 · 💻 cs.GT

Online Contract Selection for Continual Coverage

Pith reviewed 2026-05-19 21:06 UTC · model grok-4.3

classification 💻 cs.GT
keywords online algorithmscompetitive analysiscontract selectioncontinual coveragei.i.d. pricesquantile thresholdsdeferred modelconcurrent model
0
0 comments X

The pith

For i.i.d. prices, quantile-threshold algorithms achieve an exact asymptotic competitive ratio of 2.472 in the deferred contract model and improve the concurrent-model bounds to 4.179.

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

The paper studies how to keep a system covered at every time step by buying contracts of arbitrary length online, when each period's price is drawn from a known distribution. In the deferred model contracts queue back-to-back without overlap; in the concurrent model they can start immediately and overlap. When prices are i.i.d., the authors give quantile-based threshold rules whose worst-case ratio against the offline optimum is exactly characterized for the deferred case and asymptotically equals roughly 2.472. The same rules yield a matching lower bound and an asymptotic upper bound of 4.179 for the concurrent case, tightening earlier numbers. When prices are merely independent but not identically distributed, no finite ratio is possible at all.

Core claim

For i.i.d. prices the deferred model admits an exact characterization of the optimal competitive ratio, which approaches ζ* ≈ 2.472 as the horizon grows; the concurrent model has a lower bound of ζ* and an asymptotic upper bound of 4.179, both obtained from quantile-based threshold algorithms whose analysis uses linear-programming duality in quantile space. The same setting yields no finite competitive ratio when prices are independent but not identically distributed.

What carries the argument

Quantile-based threshold algorithms that set contract lengths according to the price quantile and are analyzed by LP duality in quantile space.

If this is right

  • The deferred model has a tight asymptotic competitive ratio of ζ* ≈ 2.472.
  • The concurrent model has an asymptotic competitive ratio between ζ* and 4.179.
  • The algorithms translate directly into practical threshold rules that work for any known distribution.
  • No finite competitive ratio exists when prices are independent but not identically distributed.
  • The bounds improve the previous lower bound of 2.148 and upper bound of 6.052.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Procurement systems that know the price distribution can replace ad-hoc rules with simple quantile thresholds that guarantee a constant factor of the hindsight optimum.
  • The sharp separation between i.i.d. and merely independent prices may appear in other continual online resource problems such as repeated energy procurement or cloud-instance leasing.
  • Learning the distribution on the fly would be a natural next question, since the current results collapse without distributional knowledge.

Load-bearing premise

The price distribution is known in advance and successive prices are i.i.d.

What would settle it

For a concrete i.i.d. distribution such as uniform on [0,1], exhibit an online policy whose ratio against the offline optimum stays below 2.472 for arbitrarily long horizons, or show that some non-i.i.d. independent price sequence admits a finite competitive ratio.

Figures

Figures reproduced from arXiv: 2605.16601 by Qinge Chi, Sebastian Perez-Salazar.

Figure 2
Figure 2. Figure 2: LP objective for j = 55, . . . , 65 6 Competitive Ratio Upper Bound for OSCC We now extend the analysis to any CDF F. For this, we consider ALG with the same family of inputs described at the beginning of Section 5.1. We require that a and q to satisfy a/q ≥ 2 so that t0 ≤  a · q 0  , which simplifies the expression of t0 and thus part of the analysis (see details in Lemma 6.6). We then assume n → ∞ and … view at source ↗
read the original abstract

Motivated by applications where a system must remain operational via continual procurement of contracts, we study two online contract selection problems under uncertain prices. At each time step, a price drawn from a known distribution is revealed online, and the decision-maker may initiate a contract of arbitrary duration, incurring a cost equal to the product of the price and the contract length; moreover, every time period must be covered by at least one active contract. We consider two models depending on how contracts cover time: a \emph{deferred model}, in which contracts are queued back-to-back, and a \emph{concurrent model}, in which contracts become active immediately and may overlap. In both settings, we seek online algorithms that minimize their competitive ratio, i.e., the ratio between the expected cost incurred by the online algorithm and the expected offline optimal cost when all prices are known in advance. We first focus on the case where prices are independent and identically distributed (i.i.d.). For the deferred model, we characterize exactly the worst-case optimal competitive ratio, which is asymptotically $\zeta^* \approx 2.472$ as the time horizon grows. For the concurrent model, we prove a lower bound of $\zeta^*$ on the optimal competitive ratio and an asymptotic competitive ratio of at most $4.179$. These bounds improve upon the current lower bound of $2.148$ and upper bound of $6.052$ on the optimal competitive ratio. For both models, our algorithms are quantile-based that can be easily translated into practical threshold-based algorithms for any distribution. Our proofs follow from linear programs and duality arguments in quantile spaces. Lastly, we show that, in both models, no finite competitive ratio exists when the prices are still independent but not necessarily identically distributed, proving a striking division in the two price settings.

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 manuscript studies two online contract selection problems for continual coverage under prices drawn from known distributions: a deferred model where contracts queue back-to-back and a concurrent model allowing overlaps. For i.i.d. prices, it exactly characterizes the optimal competitive ratio for the deferred model (asymptotically ζ* ≈ 2.472) and gives a lower bound of ζ* together with an asymptotic upper bound of 4.179 for the concurrent model, improving prior bounds of 2.148 and 6.052. Both results rely on quantile-based threshold algorithms obtained from LP formulations and duality arguments in quantile space. The paper also proves that no finite competitive ratio exists when prices are independent but not identically distributed.

Significance. If the LP-duality derivations hold, the work supplies the first exact asymptotic characterization for the deferred model and materially tighter bounds for the concurrent model, together with a clean impossibility result that separates the i.i.d. and non-i.i.d. regimes. The quantile-space LP technique is a methodological strength that yields practical threshold algorithms for arbitrary distributions and avoids parameter fitting. These contributions advance competitive analysis for coverage-constrained procurement problems.

major comments (2)
  1. [§4] §4 (deferred-model LP): the exact asymptotic value ζ* ≈ 2.472 is obtained by solving an infinite-horizon LP in quantile space; the manuscript should supply either a closed-form expression for the limit or a rigorous convergence argument showing that the finite-horizon optima approach this value, because the central claim of an 'exact characterization' rests on this limit.
  2. [§5] §5 (concurrent-model upper bound): the algorithm achieving the asymptotic ratio 4.179 is constructed from the dual of a quantile LP; it is unclear whether the same LP can be used to prove a matching upper bound or whether the gap between ζ* and 4.179 is an artifact of the particular dual relaxation chosen.
minor comments (2)
  1. [Model section] The definition of the competitive ratio (expected online cost over expected offline optimum) is stated clearly in the abstract but should be repeated verbatim in the model section to avoid any ambiguity when the horizon is finite versus asymptotic.
  2. [Throughout] Table summarizing the four competitive-ratio results (deferred i.i.d., concurrent i.i.d. lower/upper, non-i.i.d. impossibility) would improve readability; currently the bounds are scattered across the abstract and main theorems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and constructive feedback on our manuscript. We address each of the major comments in detail below. The suggested clarifications can be incorporated with minor revisions.

read point-by-point responses
  1. Referee: [§4] §4 (deferred-model LP): the exact asymptotic value ζ* ≈ 2.472 is obtained by solving an infinite-horizon LP in quantile space; the manuscript should supply either a closed-form expression for the limit or a rigorous convergence argument showing that the finite-horizon optima approach this value, because the central claim of an 'exact characterization' rests on this limit.

    Authors: We agree that a rigorous justification for the asymptotic limit is necessary to support the claim of an exact characterization. In the revised version, we will add a convergence theorem proving that the optimal objective values of the finite-horizon quantile LPs converge to that of the infinite-horizon LP as the horizon length tends to infinity. This is established by showing that the sequence of finite optima is monotone and bounded, hence convergent, and that any limit point satisfies the infinite LP. While we do not have a closed-form expression for ζ*, the convergence argument rigorously justifies the asymptotic value. We will also include numerical evidence of rapid convergence for large horizons. revision: yes

  2. Referee: [§5] §5 (concurrent-model upper bound): the algorithm achieving the asymptotic ratio 4.179 is constructed from the dual of a quantile LP; it is unclear whether the same LP can be used to prove a matching upper bound or whether the gap between ζ* and 4.179 is an artifact of the particular dual relaxation chosen.

    Authors: The 4.179 upper bound is obtained by solving the dual of the quantile LP to derive threshold parameters for an online algorithm, then proving that this algorithm achieves a competitive ratio of at most 4.179 against the offline optimum. The LP relaxation is used to find a good dual solution that yields a feasible algorithm, but it does not directly provide a matching lower bound for the concurrent model. The lower bound of ζ* is shown separately by reducing the concurrent problem to the deferred model. We acknowledge that the gap may be due to the relaxation and do not claim optimality of 4.179; however, it represents a significant improvement over the previous upper bound of 6.052. In the revision, we will explicitly state that the bound is not necessarily tight and discuss the role of the dual relaxation. revision: partial

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The central results follow from explicit LP formulations and duality arguments defined over quantile space for the i.i.d. case, together with a direct adversarial construction for the non-i.i.d. impossibility result. These steps are self-contained, use the stated modeling assumptions (known distribution, coverage requirement) as inputs without redefining the target competitive ratio inside the same equations, and do not rely on self-citations or fitted parameters that are later renamed as predictions. The quantile-based threshold algorithms are derived from the dual solutions rather than presupposed by them.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The analysis rests on standard online-algorithm assumptions rather than new free parameters or invented entities.

axioms (2)
  • domain assumption Prices are drawn independently from a known distribution
    Enables quantile-based threshold design and LP formulation in quantile space.
  • domain assumption Every time period must be covered by at least one active contract
    Defines the feasibility constraint for both deferred and concurrent models.

pith-pipeline@v0.9.0 · 5857 in / 1529 out tokens · 58153 ms · 2026-05-19T21:06:01.862528+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

59 extracted references · 59 canonical work pages

  1. [1]

    Hiring Secretaries over Time: The Benefit of Concurrent Employment , year=

    Yann Disser and John Fearnley and Martin Gairing and Oliver Göbel and Max Klimm and Daniel Schmand and Alexander Skopalik and Andreas Tönnis , journal=. Hiring Secretaries over Time: The Benefit of Concurrent Employment , year=

  2. [2]

    2024 , eprint=

    Optimal Guarantees for Online Selection Over Time , author=. 2024 , eprint=

  3. [3]

    Manne , journal=

    Alan S. Manne , journal=. Linear Programming and Sequential Decisions , year=

  4. [4]

    EC'21: Proceedings of the 22nd ACM Conference on Economics and Computation , publisher =

    Variable Decomposition for Prophet Inequalities and Optimal Ordering , author =. EC'21: Proceedings of the 22nd ACM Conference on Economics and Computation , publisher =

  5. [5]

    ACM Transactions on Economics and Computation , volume=

    Prophet inequalities over time , author=. ACM Transactions on Economics and Computation , volume=. 2025 , publisher=

  6. [6]

    Mathematics of operations research , volume=

    Posted price mechanisms and optimal threshold strategies for random arrivals , author=. Mathematics of operations research , volume=. 2021 , publisher=

  7. [7]

    AAAI , volume=

    Automated online mechanism design and prophet inequalities , author=. AAAI , volume=

  8. [8]

    Mathematics of Operations Research , volume=

    Robust online selection with uncertain offer acceptance , author=. Mathematics of Operations Research , volume=. 2025 , publisher=

  9. [9]

    Operations Research , volume=

    Selection and ordering policies for hiring pipelines via linear programming , author=. Operations Research , volume=. 2024 , publisher=

  10. [10]

    International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=

    A knapsack secretary problem with applications , author=. International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=. 2007 , organization=

  11. [11]

    Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

    Primal beats dual on online packing LPs in the random-order model , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

  12. [12]

    Proceedings of the twenty-second annual ACM symposium on Theory of computing , pages=

    An optimal algorithm for on-line bipartite matching , author=. Proceedings of the twenty-second annual ACM symposium on Theory of computing , pages=

  13. [13]

    2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages=

    Online stochastic matching: Beating 1-1/e , author=. 2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages=. 2009 , organization=

  14. [14]

    Proceedings of the 26th ACM Conference on Economics and Computation , pages=

    Dynamic Rental Games with Stagewise Individual Rationality , author=. Proceedings of the 26th ACM Conference on Economics and Computation , pages=

  15. [15]

    Mathematics of Operations Research , volume =

    Perez-Salazar, Sebastian and Singh, Mohit and Toriello, Alejandro , title =. Mathematics of Operations Research , volume =. 2026 , publisher=

  16. [16]

    Gilbert and Frederick Mosteller , journal=

    John P. Gilbert and Frederick Mosteller , journal=. Recognizing the Maximum of a Sequence , year=

  17. [17]

    Mathematics of Operations Research , year=

    Splitting Guarantees for Prophet Inequalities via Nonlinear Systems , author=. Mathematics of Operations Research , year=

  18. [18]

    1975 , PUBLISHER =

    Introductory Real Analysis , AUTHOR =. 1975 , PUBLISHER =

  19. [19]

    Bulletin of the American Mathematical Society , year=

    Semiamarts and finite values , author=. Bulletin of the American Mathematical Society , year=

  20. [20]

    The Annals of Probability , year=

    Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random Variables , author=. The Annals of Probability , year=

  21. [21]

    Proceedings of the 13th ACM Conference on Electronic Commerce , pages=

    Online prophet-inequality matching with applications to ad allocation , author=. Proceedings of the 13th ACM Conference on Electronic Commerce , pages=. 2012 , publisher =

  22. [22]

    SIAM Journal on Discrete Mathematics , volume =

    Esfandiari, Hossein and Hajiaghayi, MohammadTaghi and Liaghat, Vahid and Monemizadeh, Morteza , title =. SIAM Journal on Discrete Mathematics , volume =

  23. [23]

    Bansal, N., Finocchi, I

    The Temp Secretary Problem , author=. Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015.Lecture Notes in Computer Science , volume =. 2015 , organization =

  24. [24]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Minimization is Harder in the Prophet World , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

  25. [25]

    and Malec, David L

    Chawla, Shuchi and Hartline, Jason D. and Malec, David L. and Sivan, Balasubramanian , title =. Proceedings of the Forty-Second ACM Symposium on Theory of Computing , pages =. 2010 , publisher =

  26. [26]

    SIAM Journal on Computing , volume =

    Soheil Ehsani and MohammadTaghi Hajiaghayi and Thomas Kesselheim and Sahil Singla , title =. SIAM Journal on Computing , volume =

  27. [27]

    Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing , pages =

    Kleinberg, Robert and Weinberg, Seth Matthew , title =. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing , pages =. 2012 , publisher =

  28. [28]

    Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing , pages =

    Rubinstein, Aviad , title =. Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing , pages =. 2016 , publisher =

  29. [29]

    Mathematics of Operations Research , volume =

    Qin, Junjie and Vardi, Shai and Wierman, Adam , title =. Mathematics of Operations Research , volume =. 2024 , publisher=

  30. [30]

    Hill and Robert P

    Theodore P. Hill and Robert P. Kertz , title =. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete , volume =

  31. [31]

    T. P. Hill and Robert P. Kertz , journal =. Comparisons of Stop Rule and Supremum Expectations of I.I.D. Random Variables , volume =

  32. [32]

    Journal of Multivariate Analysis , pages =

    Kertz, Robert P , title =. Journal of Multivariate Analysis , pages =. 1986 , volume =

  33. [33]

    Operations Research , volume =

    Jiang, Jiashuo and Ma, Will and Zhang, Jiawei , title =. Operations Research , volume =. 2025 , publisher=

  34. [34]

    SIAM Journal on Computing , volume =

    Alaei, Saeed , title =. SIAM Journal on Computing , volume =

  35. [35]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

    Mathieu Molina and Nicolas Gast and Patrick Loiseau and Vianney Perchet , title =. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =

  36. [36]

    Mathematics of Operations Research , volume =

    Buchbinder, Niv and Jain, Kamal and Singh, Mohit , title =. Mathematics of Operations Research , volume =. 2014 , publisher =

  37. [37]

    Information Technology Convergence and Services , year=

    Optimal Single-Choice Prophet Inequalities from Samples , author=. Information Technology Convergence and Services , year=

  38. [38]

    Proceedings of the 25th ACM Conference on Economics and Computation , pages =

    Cristi, Andres and Oren, Sigal , title =. Proceedings of the 25th ACM Conference on Economics and Computation , pages =. 2024 , publisher =

  39. [39]

    Trading Prophets , journal =

    Correa, Jos\'. Trading Prophets , journal =. 2026 , publisher =

  40. [40]

    Prophet Inequalities for I.I.D

    Correa, Jos\'. Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution , year =. Proceedings of the 2019 ACM Conference on Economics and Computation , pages =

  41. [41]

    Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

    Kleinberg, Robert , title =. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2005 , publisher =

  42. [42]

    Ferguson , journal =

    Thomas S. Ferguson , journal =. Who Solved the Secretary Problem? , volume =

  43. [43]

    Optimal choice of the stopping moment of a Markov process , volume =

    Eugene Borisovich Dynkin , journal =. Optimal choice of the stopping moment of a Markov process , volume =

  44. [44]

    Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages =

    Abolhassani, Melika and Ehsani, Soheil and Esfandiari, Hossein and HajiAghayi, MohammadTaghi and Kleinberg, Robert and Lucier, Brendan , title =. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2017 , publisher =

  45. [45]

    Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs , journal =

    D\". Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs , journal =

  46. [46]

    Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

    Rubinstein, Aviad and Singla, Sahil , title =. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2017 , publisher =

  47. [47]

    Proceedings of the 23rd ACM Conference on Economics and Computation , pages =

    Alaei, Saeed and Makhdoumi, Ali and Malekian, Azarakhsh and Niazadeh, Rad , title =. Proceedings of the 23rd ACM Conference on Economics and Computation , pages =. 2022 , publisher =

  48. [48]

    Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions , booktitle =

    Kesselheim, Thomas and T\". Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions , booktitle =. 2016 , volume =

  49. [49]

    Operations Research , volume =

    Feng, Yiding and Niazadeh, Rad and Saberi, Amin , title =. Operations Research , volume =. 2024 , publisher =

  50. [50]

    Proceedings of the ACM on Measurement and Analysis of Computing Systems , pages =

    Faw, Matthew and Papadigenopoulos, Orestis and Caramanis, Constantine and Shakkottai, Sanjay , title =. Proceedings of the ACM on Measurement and Analysis of Computing Systems , pages =. 2022 , publisher =

  51. [51]

    Operations Research , volume =

    Goyal, Vineet and Udwani, Rajan , title =. Operations Research , volume =. 2023 , publisher =

  52. [52]

    Journal of the ACM , pages =

    Mehta, Aranyak and Saberi, Amin and Vazirani, Umesh and Vazirani, Vijay , title =. Journal of the ACM , pages =. 2007 , publisher =

  53. [53]

    Hubert and Chen, Fei and Jiang, Shaofeng H.-C

    Chan, T-H. Hubert and Chen, Fei and Jiang, Shaofeng H.-C. , title =. Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2015 , publisher =

  54. [54]

    2024 , eprint=

    Prophet Inequality from Samples: Is the More the Merrier? , author=. 2024 , eprint=

  55. [55]

    Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d

    Correa, Jos\'. Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality , journal =. 2024 , publisher =

  56. [56]

    , title =

    Jain, Kamal and Mahdian, Mohammad and Markakis, Evangelos and Saberi, Amin and Vazirani, Vijay V. , title =. Journal of the ACM , pages =. 2003 , publisher =

  57. [57]

    A Stochastic Probing Problem with Applications

    Gupta, Anupam and Nagarajan, Viswanath. A Stochastic Probing Problem with Applications. Integer Programming and Combinatorial Optimization. 2013

  58. [58]

    The Competition Complexity of Dynamic Pricing , journal =

    Brustle, Johannes and Correa, Jos\'. The Competition Complexity of Dynamic Pricing , journal =. 2024 , publisher =

  59. [59]

    Gamma: Exploring Euler's Constant , year =

    Julian Havil , publisher =. Gamma: Exploring Euler's Constant , year =