Online Contract Selection for Continual Coverage
Pith reviewed 2026-05-19 21:06 UTC · model grok-4.3
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.
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
- 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
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.
Referee Report
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)
- [§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.
- [§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)
- [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.
- [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
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
-
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
-
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
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
axioms (2)
- domain assumption Prices are drawn independently from a known distribution
- domain assumption Every time period must be covered by at least one active contract
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We reformulate R*_n as an LP using (4)-(5) by introducing variables d̂_i for d_i and h for F^{-1} … (LP)_DC … duality arguments in quantile spaces.
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
asymptotically ζ* ≈ 2.472 … system of ordinary differential equations (1)-(2)
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
-
[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]
Optimal Guarantees for Online Selection Over Time , author=. 2024 , eprint=
work page 2024
-
[3]
Alan S. Manne , journal=. Linear Programming and Sequential Decisions , year=
-
[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]
ACM Transactions on Economics and Computation , volume=
Prophet inequalities over time , author=. ACM Transactions on Economics and Computation , volume=. 2025 , publisher=
work page 2025
-
[6]
Mathematics of operations research , volume=
Posted price mechanisms and optimal threshold strategies for random arrivals , author=. Mathematics of operations research , volume=. 2021 , publisher=
work page 2021
-
[7]
Automated online mechanism design and prophet inequalities , author=. AAAI , volume=
-
[8]
Mathematics of Operations Research , volume=
Robust online selection with uncertain offer acceptance , author=. Mathematics of Operations Research , volume=. 2025 , publisher=
work page 2025
-
[9]
Selection and ordering policies for hiring pipelines via linear programming , author=. Operations Research , volume=. 2024 , publisher=
work page 2024
-
[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=
work page 2007
-
[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]
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]
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=
work page 2009
-
[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]
Mathematics of Operations Research , volume =
Perez-Salazar, Sebastian and Singh, Mohit and Toriello, Alejandro , title =. Mathematics of Operations Research , volume =. 2026 , publisher=
work page 2026
-
[16]
Gilbert and Frederick Mosteller , journal=
John P. Gilbert and Frederick Mosteller , journal=. Recognizing the Maximum of a Sequence , year=
-
[17]
Mathematics of Operations Research , year=
Splitting Guarantees for Prophet Inequalities via Nonlinear Systems , author=. Mathematics of Operations Research , year=
- [18]
-
[19]
Bulletin of the American Mathematical Society , year=
Semiamarts and finite values , author=. Bulletin of the American Mathematical Society , year=
-
[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]
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 =
work page 2012
-
[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]
The Temp Secretary Problem , author=. Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015.Lecture Notes in Computer Science , volume =. 2015 , organization =
work page 2015
-
[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=
work page 2024
-
[25]
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 =
work page 2010
-
[26]
SIAM Journal on Computing , volume =
Soheil Ehsani and MohammadTaghi Hajiaghayi and Thomas Kesselheim and Sahil Singla , title =. SIAM Journal on Computing , volume =
-
[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 =
work page 2012
-
[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 =
work page 2016
-
[29]
Mathematics of Operations Research , volume =
Qin, Junjie and Vardi, Shai and Wierman, Adam , title =. Mathematics of Operations Research , volume =. 2024 , publisher=
work page 2024
-
[30]
Theodore P. Hill and Robert P. Kertz , title =. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete , volume =
-
[31]
T. P. Hill and Robert P. Kertz , journal =. Comparisons of Stop Rule and Supremum Expectations of I.I.D. Random Variables , volume =
-
[32]
Journal of Multivariate Analysis , pages =
Kertz, Robert P , title =. Journal of Multivariate Analysis , pages =. 1986 , volume =
work page 1986
-
[33]
Operations Research , volume =
Jiang, Jiashuo and Ma, Will and Zhang, Jiawei , title =. Operations Research , volume =. 2025 , publisher=
work page 2025
-
[34]
SIAM Journal on Computing , volume =
Alaei, Saeed , title =. SIAM Journal on Computing , volume =
-
[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 =
work page 2025
-
[36]
Mathematics of Operations Research , volume =
Buchbinder, Niv and Jain, Kamal and Singh, Mohit , title =. Mathematics of Operations Research , volume =. 2014 , publisher =
work page 2014
-
[37]
Information Technology Convergence and Services , year=
Optimal Single-Choice Prophet Inequalities from Samples , author=. Information Technology Convergence and Services , year=
-
[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 =
work page 2024
-
[39]
Correa, Jos\'. Trading Prophets , journal =. 2026 , publisher =
work page 2026
-
[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 =
work page 2019
-
[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 =
work page 2005
-
[42]
Thomas S. Ferguson , journal =. Who Solved the Secretary Problem? , volume =
-
[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]
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 =
work page 2017
-
[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]
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 =
work page 2017
-
[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 =
work page 2022
-
[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 =
work page 2016
-
[49]
Operations Research , volume =
Feng, Yiding and Niazadeh, Rad and Saberi, Amin , title =. Operations Research , volume =. 2024 , publisher =
work page 2024
-
[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 =
work page 2022
-
[51]
Operations Research , volume =
Goyal, Vineet and Udwani, Rajan , title =. Operations Research , volume =. 2023 , publisher =
work page 2023
-
[52]
Mehta, Aranyak and Saberi, Amin and Vazirani, Umesh and Vazirani, Vijay , title =. Journal of the ACM , pages =. 2007 , publisher =
work page 2007
-
[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 =
work page 2015
-
[54]
Prophet Inequality from Samples: Is the More the Merrier? , author=. 2024 , eprint=
work page 2024
-
[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 =
work page 2024
- [56]
-
[57]
A Stochastic Probing Problem with Applications
Gupta, Anupam and Nagarajan, Viswanath. A Stochastic Probing Problem with Applications. Integer Programming and Combinatorial Optimization. 2013
work page 2013
-
[58]
The Competition Complexity of Dynamic Pricing , journal =
Brustle, Johannes and Correa, Jos\'. The Competition Complexity of Dynamic Pricing , journal =. 2024 , publisher =
work page 2024
-
[59]
Gamma: Exploring Euler's Constant , year =
Julian Havil , publisher =. Gamma: Exploring Euler's Constant , year =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.