Lemma 4(a) — Rule U0 preserves EFX and shrinks the pool
ProvedLittleCharity.EFX.lemma_4_aefxenvy-graphfair-divisionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an allocation under monotone valuations, let be a pool good and an agent such that giving to produces an EFX allocation (Rule : , for ). Then
So an application of never lowers social welfare and shrinks the pool by exactly one good.
Formalization Note "Rule returns an EFX allocation" is the rule's precondition, which the Lean statement takes as a hypothesis and repeats in the conclusion, as the page's proof says ("follows directly from the precondition"). The pool decrease is written to avoid truncated natural-number subtraction.
Preamble
import Mathlib import Definitions.Def_LittleCharity_EFX_Setting
Formal statement
namespace LittleCharity.EFX
theorem lemma_4_a {n m : ℕ} (v : Fin n → Finset (Fin m) → ℝ)
(hmono : IsMonotoneVal v) (X : Fin n → Finset (Fin m))
(hX : IsPartialAllocation X) (g : Fin m) (hg : g ∈ pool X) (i : Fin n)
(hEFX' : IsEFX v (Function.update X i (insert g (X i)))) :
let X' := Function.update X i (insert g (X i))
IsPartialAllocation X' ∧ IsEFX v X' ∧
welfare v X ≤ welfare v X' ∧
(pool X').card + 1 = (pool X).card := by sorry
end LittleCharity.EFX
Source
Chaudhury, Kavitha, Mehlhorn & Sgouritsa, A Little Charity Guarantees Almost Envy-Freeness, arXiv:1907.04596v3, pp. 9–10, Algorithm 2 Rule U0 and Lemma 4(a)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.