Lemma 2, p. 39 (corrected: n0 < n or δ ≤ (n−1)/(2n−1)) — the value of (14) at the vertex with n0 entries γmax is max{δ, (n−1)/(n+n0+(1−δ)(n−n0)−1)}
ProvedProviderGuarantee.Bound.lemma_2Let , , and . Let be the vertex of with for and for . If , or if , then the optimal value of the linear program (14) at is
Lemma 2 evaluates the dual value at every vertex of the box up to relabelling; combined with the quasiconvexity of it gives the bound of Theorem 1.
The printed lemma claims the formula for every . At all entries equal , the program's value is , and the printed formula is wrong whenever . The condition added here excludes exactly those cases; it covers in particular (). Theorem 1 is unaffected, since .
Formalization Note Providers are indexed by Fin n, so "the first providers" are the indices with (vertexProfile n n0 γmin γmax). The optimal value is lpValue.
Differences from the source:
- correction: the formula holds for all n0 ∈ {1, …, n} → it is claimed for 1 ≤ n0 ≤ n with n0 < n or δ ≤ (n−1)/(2n−1); reason: counterexample n = 2, γmin = 1/2, γmax = 1, n0 = 2: γ = (1, 1), δ = 1/2; the value of (14) is 1/3 (attained by x_1 = 1/3, w_21 = w_22 = 1/3 and all other variables 0, and certified by the dual point s = 1/3, λ_ij = 1/3, feasible for (15)), while the printed formula gives max{1/2, 1/3} = 1/2; the proof's primal point uses w_{1,n0+1}, which does not exist when n0 = n
- encoding: γ_i = γmax for i ∈ {1, …, n0} → vertexProfile: γ_i = γmax for the indices i < n0 of Fin n; reason: Fin n is 0-based; same profile
import Mathlib import Definitions.Def_ProviderGuarantee_Bound_Model
namespace ProviderGuarantee.Bound
theorem lemma_2 (n n0 : ℕ) (γmin γmax : ℝ) (hγmin : 0 < γmin) (hγ : γmin ≤ γmax)
(hn0 : 1 ≤ n0) (hn0n : n0 ≤ n)
(hcorr : n0 < n ∨ heterogeneity γmin γmax ≤ ((n : ℝ) - 1) / (2 * (n : ℝ) - 1)) :
lpValue (vertexProfile n n0 γmin γmax) = lemma2Value n n0 (heterogeneity γmin γmax) := by sorry
end ProviderGuarantee.Bound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.