Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1, p. 16 — the value loss under Pareto-efficient provider guarantees is at most max{δ, (n−1)/(n+(1−δ)(n−1))}

Proved
ProviderGuarantee.Bound.theorem_1

by mikedeng1 · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)

allocationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-fairnessprovider-guaranteesworst-case-bound

Let DDD be a finite set of jobs with real values v:D→Rv : D \to \mathbb Rv:D→R, v(S)=∑d∈Sv(d)v(S) = \sum_{d \in S} v(d)v(S)=∑d∈S​v(d), let nnn providers have heterogeneity profile γ∈[γmin⁡,γmax⁡]n\gamma \in [\gamma_{\min}, \gamma_{\max}]^nγ∈[γmin​,γmax​]n with 0<γmin⁡≤γmax⁡0 < \gamma_{\min} \le \gamma_{\max}0<γmin​≤γmax​, and let δ=(γmax⁡−γmin⁡)/γmax⁡\delta = (\gamma_{\max} - \gamma_{\min})/\gamma_{\max}δ=(γmax​−γmin​)/γmax​. Let F\mathcal FF be a set of allocations satisfying Assumption 1 (indivisibility, symmetry, monotonicity, provider independence) and let FG⊆F\mathcal F_G \subseteq \mathcal FFG​⊆F be a non-empty set of allocations with guarantees satisfying Assumption 2 (Pareto efficiency). Then the value loss (1) satisfies

Lγ(F,FG)=max⁡A∈F∑i=1nγiv(Ai)−max⁡B∈FG∑i=1nγiv(Bi)max⁡A∈F∑i=1nγiv(Ai)≤max⁡{δ,n−1n+(1−δ)(n−1)}.\mathbf L_\gamma(\mathcal F, \mathcal F_G) = \frac{\max_{A \in \mathcal F} \sum_{i=1}^n \gamma_i v(A_i) - \max_{B \in \mathcal F_G} \sum_{i=1}^n \gamma_i v(B_i)}{\max_{A \in \mathcal F} \sum_{i=1}^n \gamma_i v(A_i)} \le \max\left\{\delta, \frac{n-1}{n + (1-\delta)(n-1)}\right\}.Lγ​(F,FG​)=maxA∈F​∑i=1n​γi​v(Ai​)maxA∈F​∑i=1n​γi​v(Ai​)−maxB∈FG​​∑i=1n​γi​v(Bi​)​≤max{δ,n+(1−δ)(n−1)n−1​}.

Equivalently, sup⁡F,FG,γLγ(F,FG)\sup_{\mathcal F, \mathcal F_G, \gamma} \mathbf L_\gamma(\mathcal F, \mathcal F_G)supF,FG​,γ​Lγ​(F,FG​) over all γ∈[γmin⁡,γmax⁡]n\gamma \in [\gamma_{\min}, \gamma_{\max}]^nγ∈[γmin​,γmax​]n and all F,FG\mathcal F, \mathcal F_GF,FG​ satisfying Assumptions 1 and 2 is at most this bound (5).

The bound depends only on the number of providers and the degree of heterogeneity. With homogeneous providers (δ=0\delta = 0δ=0) the loss never exceeds n−12n−1<12\frac{n-1}{2n-1} < \frac122n−1n−1​<21​, so imposing any Pareto-efficient guarantee (income guarantees, max-min fairness, α-fairness, §2.3) costs at most half of the optimal value.

Formalization Note Allocations are functions Fin n → Finset D. Maxima over F\mathcal FF and FG\mathcal F_GFG​ are real suprema of finite non-empty sets. When the optimal value over F\mathcal FF is 000, the page's ratio is 0/00/00/0 and Lean's quotient is 000. The statement quantifies over DDD, vvv, nnn, γmin⁡\gamma_{\min}γmin​, γmax⁡\gamma_{\max}γmax​ as well as over γ\gammaγ, F\mathcal FF, FG\mathcal F_GFG​.

Differences from the source:

  • encoding: sup_{F, F_G, γ} L_γ(F, F_G) ≤ bound → L_γ(F, F_G) ≤ bound for every γ, F, F_G satisfying the assumptions; reason: a supremum is at most a number iff every value is
  • encoding: L_γ(F, F_G) is the ratio (1), which is 0/0 when max_F Σγ_i v(A_i) = 0 → valueLoss uses Lean's division, so the loss is 0 in that case; reason: only the instances where the page's ratio is undefined are affected; no hypothesis 0 < max_F is added
  • reading: a set of jobs D (never said to be finite; v(S) is a finite sum and maxima over F are taken) → D a finite type; reason: the page writes v(S) = Σ_{d∈S} v(d) and max over F, which presuppose finitely many jobs; the paper calls D a discrete set of jobs
  • encoding: providers N = {1, …, n} → indices i : Fin n (0, …, n−1); reason: Lean convention; a relabelling, same instances
Preamble
import Mathlib
import Definitions.Def_ProviderGuarantee_Bound_Model
Formal statement
namespace ProviderGuarantee.Bound

theorem theorem_1 {D : Type*} [Fintype D] [DecidableEq D] (n : ℕ) (v : D → ℝ)
    (γmin γmax : ℝ) (hγmin : 0 < γmin) (hγ : γmin ≤ γmax)
    (γ : Fin n → ℝ) (hγmem : ∀ i, γ i ∈ Set.Icc γmin γmax)
    (F FG : Set (Fin n → Finset D)) (h1 : Assumption1 F) (h2 : Assumption2 v F FG)
    (hFG : FG.Nonempty) :
    valueLoss γ v F FG ≤ 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. 16, Theorem 1, (5)
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 24, 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