Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Ski-rental online algorithms: deterministic cost and fractional primal-dual variables

Definition
PrimalDualOnline_SkiRentalAlg

by moutei · Sep 16, 2026 · Mathlib 0df444a (Lean v4.33.1)

competitive-analysislinear-programmingonline-algorithmsprimal-dualski-rental

This bundle defines the two online algorithms of Chapter 3 for the ski-rental problem with purchase price BBB and kkk ski days.

Day-index convention. The source numbers ski days 1,…,k1, \dots, k1,…,k; Lean indices start at 000. The translation this development commits to is: xjx_jxj​ is the state after jjj updates, so x0=0x_0 = 0x0​=0 is the state before any ski day. On source day jjj (for 1≤j≤k1 \le j \le k1≤j≤k) the algorithm observes the state xj−1x_{j-1}xj−1​ current before that day's update, sets zj=1−xj−1z_j = 1 - x_{j-1}zj​=1−xj−1​, updates xj−1x_{j-1}xj−1​ to xjx_jxj​, and sets yj=1y_j = 1yj​=1 on an active day. Lean index jjj therefore corresponds to source day j+1j+1j+1: algZ B c j is the source's zj+1z_{j+1}zj+1​ and algY B c j is the source's yj+1y_{j+1}yj+1​, both computed from the pre-update state algX B c j. Consequently ∑j<k\sum_{j<k}∑j<k​ algZ B c j is exactly the source's z1+⋯+zkz_1 + \dots + z_kz1​+⋯+zk​ — one rental variable per ski day — and the source's identity zj=1−xj−1z_j = 1 - x_{j-1}zj​=1−xj−1​ reads here as algZ B c j =1−= 1 -=1− algX B c j on an active day.

The deterministic algorithm rents on each of the first BBB days and buys on day BBB, at the cost the source displays:

detCost(B,k)  =  {k,k<B,2B,k≥B.\mathrm{detCost}(B,k) \;=\; \begin{cases} k, & k < B, \\ 2B, & k \ge B. \end{cases}detCost(B,k)={k,2B,​k<B,k≥B.​

The fractional primal-dual algorithm maintains xxx, initially 000. On each new day, while x<1x < 1x<1 it sets the rent variable to the shortfall, raises xxx, and sets that day's dual variable to 111; once xxx has reached 111 it does nothing further:

x0=0,xj+1={xj(1+1B)+1cB,xj<1,xj,xj≥1,x_0 = 0, \qquad x_{j+1} = \begin{cases} x_j\left(1 + \dfrac{1}{B}\right) + \dfrac{1}{cB}, & x_j < 1, \\[2mm] x_j, & x_j \ge 1, \end{cases}x0​=0,xj+1​=⎩⎨⎧​xj​(1+B1​)+cB1​,xj​,​xj​<1,xj​≥1,​ zj={1−xj,xj<10,xj≥1yj={1,xj<10,xj≥1.z_j = \begin{cases} 1 - x_j, & x_j < 1 \\ 0, & x_j \ge 1 \end{cases} \qquad\qquad y_j = \begin{cases} 1, & x_j < 1 \\ 0, & x_j \ge 1. \end{cases}zj​={1−xj​,0,​xj​<1xj​≥1​yj​={1,0,​xj​<1xj​≥1.​

The rate parameter is c∗(B)=(1+1/B)B−1c^{*}(B) = \left(1 + 1/B\right)^{B} - 1c∗(B)=(1+1/B)B−1. Finally algCost(B,c,k)=Bxk+∑j<kzj\mathrm{algCost}(B,c,k) = B x_k + \sum_{j<k} z_jalgCost(B,c,k)=Bxk​+∑j<k​zj​ is the primal objective after kkk days, and algDualValue(B,c,k)=∑j<kyj\mathrm{algDualValue}(B,c,k) = \sum_{j<k} y_jalgDualValue(B,c,k)=∑j<k​yj​ the dual objective. Note the deliberate index asymmetry: the buy term is read at index kkk, while the sums run over 0,…,k−10, \dots, k-10,…,k−1.

The x<1x < 1x<1 guard is part of the algorithm, not an informal aside: without it the cost would keep growing after day BBB.

Source correspondence.

  • What the thesis states: the deterministic algorithm in prose (p. 18) with its 2B2B2B accounting, and the fractional algorithm as numbered steps 1 and 2(a)–2(c) (p. 18).
  • What this bundle defines: those two algorithms as total functions, with the day-index translation above made explicit.
  • Introduced by the formalization: the names algCost, algDualValue, cOpt; the decision to carry the guard in the definition rather than as a side condition; and the choice of B:NB : \mathbb{N}B:N.

Formalization Note. The purchase price is a natural number, because the source uses BBB as a price, a day index, and the exponent in (1+1/B)B(1+1/B)^B(1+1/B)B; it is coerced into R\mathbb{R}R inside cost expressions. Real division is total, so every reciprocal degenerates to 000 when B=0B = 0B=0 or c=0c = 0c=0, and the constant c∗(0)c^{*}(0)c∗(0) is itself 000; every theorem mentioning these definitions therefore carries the hypothesis 0<B0 < B0<B.

Definition code
import Definitions.Def_PrimalDualOnline_SkiRentalLP
import Mathlib.Tactic

namespace PrimalDualOnline.SkiRental

/-!
The two online algorithms of Chapter 3.

## Day-index convention (stated once, used everywhere)

The source numbers ski days `1, …, k`; Lean indices start at `0`. The translation this
development commits to is:

* `algX B c j` is the state **after `j` updates**. So `algX B c 0 = 0` is the state before any
  ski day has been processed, and `algX B c k` is the state after exactly `k` days.
* On source day `j` (for `1 ≤ j ≤ k`) the algorithm observes the state `x_{j-1}` that is
  current *before* that day's update, sets `z_j := 1 - x_{j-1}`, then updates `x_{j-1}` to
  `x_j`, and sets `y_j := 1` if the day is active.
* Therefore **Lean index `j` corresponds to source day `j+1`**: `algZ B c j` is the source's
  `z_{j+1}` and `algY B c j` is the source's `y_{j+1}`, both computed from the pre-update
  state `algX B c j`.
* Consequently `∑ j : Fin k, algZ B c j` is exactly the source's `z_1 + ⋯ + z_k`: `k` daily
  rental variables, one per ski day, and the source's `z_j = 1 - x_{j-1}` reads here as
  `algZ B c j = 1 - algX B c j` on an active day.

`detCost` is the cost of the deterministic algorithm, under the accounting the source
displays. `algX`, `algZ`, `algY` are the primal and dual variables maintained by the
fractional primal-dual algorithm.
-/

/-- The cost of the deterministic algorithm of Chapter 3 on an instance with purchase
price `B` and `k` ski days, under the `2 * B` accounting the source displays for `k ≥ B`.
See the mission notes on the wording ambiguity in the source's description of this
algorithm. -/
def detCost (B k : ℕ) : ℝ := if k < B then (k : ℝ) else 2 * (B : ℝ)

/-- The value of the primal buy-variable `x` maintained by the fractional primal-dual
algorithm after `j` updates, for purchase price `B` and parameter `c`.  The update
`x ← x * (1 + 1/B) + 1/(c*B)` is applied only while the current value satisfies `x < 1`. -/
noncomputable def algX (B : ℕ) (c : ℝ) : ℕ → ℝ
  | 0 => 0
  | j + 1 =>
      let x := algX B c j
      if x < 1 then x * (1 + 1 / (B : ℝ)) + 1 / (c * (B : ℝ)) else x

/-- The primal rent-variable the fractional algorithm sets on source day `j + 1`, computed
from the pre-update state `algX B c j`: it is `1 - algX B c j` while that state is below `1`,
and `0` afterwards. -/
noncomputable def algZ (B : ℕ) (c : ℝ) (j : ℕ) : ℝ :=
  if algX B c j < 1 then 1 - algX B c j else 0

/-- The dual variable the fractional algorithm sets on source day `j + 1`, computed from the
same pre-update state `algX B c j`: it is `1` while that state is below `1`, and `0`
afterwards. -/
noncomputable def algY (B : ℕ) (c : ℝ) (j : ℕ) : ℝ :=
  if algX B c j < 1 then 1 else 0

/-- The parameter `c = (1 + 1/B)^B - 1` chosen in Chapter 3, for which the fractional
algorithm's buy-variable equals `1` after `B` updates. -/
noncomputable def cOpt (B : ℕ) : ℝ := (1 + 1 / (B : ℝ)) ^ B - 1

/-- The primal cost of the fractional algorithm's solution after `k` ski days: the buy
variable in its state after `k` updates, together with the `k` daily rent variables of
source days `1, …, k`. -/
noncomputable def algCost (B : ℕ) (c : ℝ) (k : ℕ) : ℝ :=
  primalCost (B : ℝ) (algX B c k) (fun j : Fin k => algZ B c (j : ℕ))

/-- The dual objective value the fractional algorithm has accumulated after `k` ski days,
summing the dual variables of source days `1, …, k`. -/
noncomputable def algDualValue (B : ℕ) (c : ℝ) (k : ℕ) : ℝ :=
  dualValue (fun j : Fin k => algY B c (j : ℕ))

end PrimalDualOnline.SkiRental
Source
Niv Buchbinder, "Designing Competitive Online Algorithms via a Primal-Dual Approach", PhD thesis, Tel Aviv University, 2008, https://www.tau.ac.il/~nivb/download/phd-thsis.pdf, Chapter 3, pp. 18-19 (PDF pp. 34-35): the deterministic algorithm described in the second paragraph of p. 18, and the numbered steps 1 and 2(a)-2(c) of the fractional online algorithm on p. 18.
Read-back

What the Lean code literally says, in plain math · claude-opus-5

detCost is a function of two natural-number arguments BBB and kkk, both explicit, returning a real number, defined by the case split

detCost(B,k)={kif k<B,2Botherwise,\mathrm{detCost}(B,k) = \begin{cases} k & \text{if } k < B,\\[2pt] 2B & \text{otherwise,}\end{cases}detCost(B,k)={k2B​if k<B,otherwise,​

where the test is a comparison of natural numbers and both branch values are real images of the naturals kkk and 2B2B2B. The definition mentions none of the other declarations in this bundle, and there is no reference to any algorithm, cost model, or parameter ccc. Degenerate cases: when B=0B = 0B=0 the guard k<0k < 0k<0 is false for every kkk, so the value is 000 for all kkk; when k=0k = 0k=0 and B≥1B \ge 1B≥1 the guard holds and the value is 000; for k≥Bk \ge Bk≥B the value is 2B2B2B regardless of how much larger kkk is.

algX takes a natural BBB and a real ccc and defines a sequence xjx_jxj​ by primitive recursion:

x0=0,xj+1={xj(1+1B)+1c Bif xj<1,xjif xj≥1.x_0 = 0, \qquad x_{j+1} = \begin{cases} x_j\left(1 + \dfrac{1}{B}\right) + \dfrac{1}{c\,B} & \text{if } x_j < 1,\\[8pt] x_j & \text{if } x_j \ge 1.\end{cases}x0​=0,xj+1​=⎩⎨⎧​xj​(1+B1​)+cB1​xj​​if xj​<1,if xj​≥1.​

The guard tests the previous value xjx_jxj​ — it does not test xj+1x_{j+1}xj+1​, nor the index, nor any quantity derived from ccc or BBB alone. Both occurrences of BBB are the real cast. The sequence is frozen from the first index at which the value is ≥1\ge 1≥1. Division is total, with 1/0=01/0 = 01/0=0, which produces the following degenerate behaviour. If B=0B = 0B=0, the recursion reads xj+1=xjx_{j+1} = x_jxj+1​=xj​ whenever xj<1x_j < 1xj​<1, giving xj=0x_j = 0xj​=0 for all jjj. If c=0c = 0c=0 (any BBB), the recursion reads xj+1=xj(1+1/B)x_{j+1} = x_j(1 + 1/B)xj+1​=xj​(1+1/B) on that branch, again giving xj=0x_j = 0xj​=0 for all jjj, so the sequence never leaves the branch xj<1x_j < 1xj​<1. If c<0c < 0c<0 and B≥1B \ge 1B≥1, the additive term is negative, so from x0=0x_0 = 0x0​=0 the terms are strictly decreasing, remain <1< 1<1 forever, and the second branch is never taken. At index 000 the value is 000 unconditionally, with no case split.

algZ takes BBB, ccc, and a natural index jjj, and returns

zj={1−xjif xj<1,0if xj≥1,z_j = \begin{cases} 1 - x_j & \text{if } x_j < 1,\\[2pt] 0 & \text{if } x_j \ge 1,\end{cases}zj​={1−xj​0​if xj​<1,if xj​≥1,​

where xj=algX(B,c,j)x_j = \mathrm{algX}(B,c,j)xj​=algX(B,c,j). Both the guard and the subtracted quantity consult algX at exactly the same index jjj as algZ's own argument — not at j+1j+1j+1 and not at j−1j-1j−1. In particular z0z_0z0​ is determined by x0=0x_0 = 0x0​=0, hence z0=1z_0 = 1z0​=1 for every BBB and ccc. If xjx_jxj​ is negative (as happens when c<0c < 0c<0 and B≥1B \ge 1B≥1) the first branch gives zj=1−xj>1z_j = 1 - x_j > 1zj​=1−xj​>1. If B=0B = 0B=0 or c=0c = 0c=0 then xj=0x_j = 0xj​=0 for all jjj and hence zj=1z_j = 1zj​=1 for all jjj.

algY takes BBB, ccc, jjj, and returns 111 if xj<1x_j < 1xj​<1 and 000 if xj≥1x_j \ge 1xj​≥1. As with algZ, the guard consults algX at the same index jjj, not at j+1j+1j+1. The only possible values are 000 and 111; the value does not depend on how far below 111 the quantity xjx_jxj​ lies. Since x0=0<1x_0 = 0 < 1x0​=0<1, y0=1y_0 = 1y0​=1 for every BBB and ccc. If B=0B = 0B=0, or c=0c = 0c=0, or c<0c < 0c<0 with B≥1B \ge 1B≥1, then xj<1x_j < 1xj​<1 for all jjj and hence yj=1y_j = 1yj​=1 for all jjj.

cOpt takes a natural BBB and returns (1+1B)B−1\left(1 + \frac{1}{B}\right)^{B} - 1(1+B1​)B−1, where BBB inside the parentheses is the real cast and the exponent is the same natural BBB. This is a closed-form expression in BBB alone: it is not defined in terms of algX, algZ, algY, or detCost, no property relating it to them is asserted here, and the name carries no claim of optimality. Degenerate case: with total division, B=0B = 0B=0 gives cOpt(0)=(1+0)0−1=0\mathrm{cOpt}(0) = (1+0)^0 - 1 = 0cOpt(0)=(1+0)0−1=0.

algCost takes BBB, ccc, kkk and applies the previously defined primal cost functional with budget parameter BBB (cast to R\mathbb{R}R), its "xxx" slot filled by algX(B,c,k)\mathrm{algX}(B,c,k)algX(B,c,k) and its vector slot by the family j↦algZ(B,c,j)j \mapsto \mathrm{algZ}(B,c,j)j↦algZ(B,c,j) over the kkk indices 0,…,k−10,\dots,k-10,…,k−1. Unfolding:

algCost(B,c,k)=B⋅xk+∑j=0k−1zj.\mathrm{algCost}(B,c,k) = B \cdot x_k + \sum_{j=0}^{k-1} z_j .algCost(B,c,k)=B⋅xk​+j=0∑k−1​zj​.

There are therefore exactly kkk summands, running over indices 000 through k−1k-1k−1 inclusive (index kkk itself does not contribute a summand), while algX in the first term is evaluated at index kkk — one past the largest index occurring in the sum. Degenerate cases: for k=0k = 0k=0 the sum is empty and the whole expression reduces to B⋅x0=0B \cdot x_0 = 0B⋅x0​=0; for B=0B = 0B=0 the first term is 000 and, since xj=0x_j = 0xj​=0 for all jjj, the total is kkk; for c=0c = 0c=0 likewise the total is kkk; for c<0c < 0c<0 with B≥1B \ge 1B≥1 every summand is 1−xj1 - x_j1−xj​ and the first term is negative.

algDualValue takes BBB, ccc, kkk and applies the dual value functional — the sum of the entries — to the family j↦algY(B,c,j)j \mapsto \mathrm{algY}(B,c,j)j↦algY(B,c,j) over the same kkk indices. Unfolding:

algDualValue(B,c,k)=∑j=0k−1yj=#{ j:0≤j≤k−1 and xj<1 }.\mathrm{algDualValue}(B,c,k) = \sum_{j=0}^{k-1} y_j = \#\{\, j : 0 \le j \le k-1 \text{ and } x_j < 1 \,\}.algDualValue(B,c,k)=j=0∑k−1​yj​=#{j:0≤j≤k−1 and xj​<1}.

There are exactly kkk summands, over indices 000 through k−1k-1k−1 inclusive; the parameter BBB appears only through its role inside algY (hence inside algX) and not as an outside coefficient, and algX is evaluated only at indices 0,…,k−10,\dots,k-10,…,k−1 — the index kkk does not occur anywhere in this expression, in contrast to algCost. For k=0k = 0k=0 the value is 000; if B=0B = 0B=0, or c=0c = 0c=0, or c<0c < 0c<0 with B≥1B \ge 1B≥1, every summand is 111 and the value is kkk. In general the value is a natural number between 000 and kkk viewed in R\mathbb{R}R.

Human review
  • Endorsed by Shuze Chen · Sep 16, 2026

  • Endorsed by moutei · Sep 16, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me