Proof of Theorem 1, p. 39 — max{δ, (n−1)/(n+n0+(1−δ)(n−n0)−1)} is non-increasing in n0, and at n0 = 1 it is the bound (5)
ProvedProviderGuarantee.Bound.lemma2Value_antitonep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1provider-guaranteesworst-case-bound
Let , , and for put
Then is non-increasing: whenever . Moreover
the right-hand side of (5).
This is the last step of the proof of Theorem 1: among the vertices of the box, the one with a single provider at gives the largest value, and that value is the bound.
Differences from the source:
- reading: 'this is a decreasing function of n0' → non-increasing: g(n0') ≤ g(n0) for 1 ≤ n0 ≤ n0' ≤ n; reason: for δ = 0, or when δ dominates, g is constant, so strict decrease is false; the page uses only that n0 = 1 maximizes g
Preamble
import Mathlib import Definitions.Def_ProviderGuarantee_Bound_Model
Formal statement
namespace ProviderGuarantee.Bound
theorem lemma2Value_antitone (n : ℕ) (γmin γmax : ℝ) (hγmin : 0 < γmin) (hγ : γmin ≤ γmax)
(n0 n0' : ℕ) (h1 : 1 ≤ n0) (h2 : n0 ≤ n0') (h3 : n0' ≤ n) :
lemma2Value n n0' (heterogeneity γmin γmax) ≤ lemma2Value n n0 (heterogeneity γmin γmax) ∧
lemma2Value n 1 (heterogeneity γmin γmax) = lossBound n (heterogeneity γmin γmax) := by sorry
end ProviderGuarantee.Bound
Source
Gur, Iancu & Warnes, Value Loss in Allocation Systems with Provider Guarantees, SSRN 3351509 (version of March 24, 2020), p. 39, proof of Theorem 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.