Theorem 1, p. 16 — the value loss under Pareto-efficient provider guarantees is at most max{δ, (n−1)/(n+(1−δ)(n−1))}
ProvedProviderGuarantee.Bound.theorem_1Let be a finite set of jobs with real values , , let providers have heterogeneity profile with , and let . Let be a set of allocations satisfying Assumption 1 (indivisibility, symmetry, monotonicity, provider independence) and let be a non-empty set of allocations with guarantees satisfying Assumption 2 (Pareto efficiency). Then the value loss (1) satisfies
Equivalently, over all and all 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 () the loss never exceeds , 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 and are real suprema of finite non-empty sets. When the optimal value over is , the page's ratio is and Lean's quotient is . The statement quantifies over , , , , as well as over , , .
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
import Mathlib import Definitions.Def_ProviderGuarantee_Bound_Model
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.