Lemma 17(a) — each bad good is worth at most one's own bundle
ProvedLittleCharity.GMMS.lemma_17_aefxfair-divisiongmmsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a partial EFX allocation for nonnegative additive valuations. Suppose every agent values its pool no more than its own bundle, and is an unenvied agent. Form by giving the pool to . For any observer , a bad good lies in a two-good bundle with and . Then
This bounds the aggregate value of bad goods in the proof of the guarantee.
Formalization Note The page calls the donor “agent 1”; Lean uses a named source . A bad good is encoded through its containing bundle, following the classification immediately before Lemma 17.
Preamble
import Mathlib import Definitions.Def_LittleCharity_GMMS_Setting
Formal statement
namespace LittleCharity.GMMS
/-- Lemma 17(a), p. 16: each bad good is worth at most the observing agent's own bundle. -/
theorem lemma_17_a {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 → j ≠ i → (donate X s j).card = 2 →
∀ g ∈ donate X s j, v i {g} ≤ 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, p. 16, classification and Lemma 17(a)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.