Lemma 17(c) — a good bundle is worth at most three halves of one's own
ProvedLittleCharity.GMMS.lemma_17_cefxfair-divisiongmmsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a partial EFX allocation for nonnegative additive valuations. Suppose every agent values the pool no more than its own bundle, and is an unenvied agent. Give the pool to , obtaining . Fix an observing agent . If and either or contains at least three goods, then
These are exactly the good bundles other than the donor's bundle in the classification before Lemma 17. Their value bound is used in the final count of Theorem 16.
Formalization Note The page's “agent 1” is . The disjunction also covers , whose own bundle is classified as good at any size.
Preamble
import Mathlib import Definitions.Def_LittleCharity_GMMS_Setting
Formal statement
namespace LittleCharity.GMMS
/-- Lemma 17(c), p. 16: a good bundle other than the source's has value at most three halves of one's own. -/
theorem lemma_17_c {n m : ℕ} (v : Fin n → Finset (Fin m) → ℝ) (hadd : LittleCharity.MMS.IsAdditive v)
(X : Fin n → Finset (Fin m)) (hX : LittleCharity.EFX.IsPartialAllocation X) (hEFX : LittleCharity.MMS.IsEFX v X)
(hpool : ∀ i, v i (LittleCharity.EFX.pool X) ≤ v i (X i))
(s : Fin n) (hs : LittleCharity.EFX.IsSource v X s) (i : Fin n) :
∀ j, j ≠ s → (3 ≤ (donate X s j).card ∨ j = i) →
v i (donate X s j) ≤ (3 / 2 : ℝ) * v i (donate X s i) := by sorry
end LittleCharity.GMMS
Source
Chaudhury, Kavitha, Mehlhorn & Sgouritsa, A Little Charity Guarantees Almost Envy-Freeness, arXiv:1907.04596v3, pp. 16–17, classification and Lemma 17(c)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.