Proof of Theorem 3, p. 58 — a ranking whose every rank is 2ϵ/n-approximately best satisfies E[H(π∗)] ≤ 2E[H(π̃)] + 2ϵ
ProvedRankAssort.SimpleLearn.approx_greedy_boundLet types be drawn from with a measurable type map, let be a real number, and let be a ranking of the products that satisfies (23) at every rank: for each , the product is -approximately best among the products not in ,
Then for every ranking ,
This is the deterministic core of Theorem 3: "for any such fixed ranking , we aim to show that , or equivalently, " (p. 58), proved through (25)–(28). With it contains the ½-approximation of the greedy ranking (Theorem 1).
Formalization Note Ranks are 0-based in Lean: the paper's rank is index , a ranking is a duplicate-free list of the products (Fin n), and is the list entry at index . The hypothesis is written with IsApproxBest, i.e. with marginal benefits; by the second part of (6) (milestone eq_6) the two sides of (23), and , are exactly these marginal benefits. The maximum is over the unranked products, as in Algorithm 2; under the coupled law every term of (23) is nonnegative and an already-ranked product's term is , so the two maxima agree. The tolerance is a real division by .
Differences from the source:
- generalization: ϵ > 0 (input of Algorithm 2) → any real eps; reason: the case ϵ > 0 is included
- generalization: π∗ the optimal ranking → every ranking π∗; reason: the optimal ranking is one instance
- reading: (23): max over i ∈ [n] of E[C̄(r − 1, π̃) Cᵢ([π̃]ᵣ₋₁ ∪ i)] → maximum over products i not in [π̃]ᵣ₋₁ (IsApproxBest); reason: [π̃]ᵣ₋₁ ∪ i is not a ranking when i is already ranked, and Algorithm 2 runs ALG on the unranked products U; under the model an already-ranked product's term is 0 and every term is ≥ 0, so the two maxima agree
- encoding: the two sides of (23), E[C̄(r − 1, π̃) C(·)] → marginal benefits margBenefit (difference of expected hooks); reason: equal by part 2 of (6) (milestone eq_6)
- encoding: expectation over the type (p, f, k) ∼ D, a random variable → integral over θ ∼ D of a function of τ θ, with TypeMeasurable τ (every coordinate of the type map measurable); reason: the expectations are undefined otherwise (Lean would return the junk value 0); the integrands lie in [0, 1], so measurability is all that is needed
- encoding: ranks 1..n, a ranking is a permutation π of [n], π⁻¹(j) the product at rank j → 0-based indices, a ranking is a duplicate-free List (Fin n) of length n, π⁻¹(j) is the entry at index j − 1; reason: Lean convention; the same rankings
import Mathlib import Definitions.Def_RankAssort_SimpleLearn_Model import Definitions.Def_RankAssort_SimpleLearn_Algorithm
namespace RankAssort.SimpleLearn
open MeasureTheory
theorem approx_greedy_bound {n : ℕ} {Θ : Type*} [MeasurableSpace Θ] (D : Measure Θ)
[IsProbabilityMeasure D] (τ : Θ → CustomerType n) (hτ : TypeMeasurable τ) (eps : ℝ)
(piT : List (Fin n)) (hT : piT.Nodup) (hTlen : piT.length = n)
(hgood : ∀ r < n, ∃ i, piT[r]? = some i ∧ IsApproxBest D τ (piT.take r) i (2 * eps / n))
(piStar : List (Fin n)) (hs : piStar.Nodup) (hslen : piStar.length = n) :
expHook D τ piStar ≤ 2 * expHook D τ piT + 2 * eps := by sorry
end RankAssort.SimpleLearn
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.