Online Contract Selection for Continual Coverage hits optimal 2.472 ratio

In a new arXiv preprint (2605.16601), researchers Qinge Chi and Sebastian Perez-Salazar tackle a fundamental problem in online decision-making: procuring contracts over time to ensure continual coverage when prices are revealed one by one from a known distribution. The decision-maker can start a contract of any length at the revealed price, paying price × duration, and must cover every time period by at least one active contract. The paper analyzes two natural models: the deferred model (contracts queue back-to-back without overlap) and the concurrent model (contracts become active immediately and can overlap).

For the deferred model with i.i.d. prices, the authors exactly characterize the worst-case optimal competitive ratio (ratio of online cost to offline optimal cost), which asymptotically approaches ζ* ≈ 2.472 as the time horizon grows. For the concurrent model, they prove a lower bound of ζ* and provide an upper bound of 4.179, improving on previous bounds of 2.148 and 6.052. Both algorithms are quantile-based, easily converting to simple threshold policies for any price distribution. The proofs use linear programming and duality in quantile spaces. Moreover, the paper shows a striking negative result: if prices are independent but not identically distributed, no finite competitive ratio exists in either model – a fundamental division between i.i.d. and non-i.i.d. settings.