Lemma 4(b) — failure of U0 yields a small envied subset
ProvedLittleCharity.EFX.lemma_4_bLet be an EFX allocation under monotone valuations, and suppose Rule is not applicable: for no pool good and no agent is the allocation obtained by giving to EFX. Then for every source of and every good :
- some agent envies the enlarged bundle, ;
- every inclusion-wise minimal envied subset of satisfies
This guarantees that the sets used by Rules and are envied and that a minimal envied subset leaves at least one good of it unassigned.
Formalization Note The hypothesis that is EFX is Algorithm 1's invariant (p. 8), in force wherever the lemma is applied; it is added because without it could fail for reasons unrelated to . Non-applicability of follows Algorithm 2's precondition (any agent ), whereas the prose before Lemma 4 speaks of adding the good to a source; the Lean hypothesis is the precondition's version.
import Mathlib import Definitions.Def_LittleCharity_EFX_Setting
namespace LittleCharity.EFX
theorem lemma_4_b {n m : ℕ} (v : Fin n → Finset (Fin m) → ℝ)
(hmono : IsMonotoneVal v) (X : Fin n → Finset (Fin m))
(hX : IsPartialAllocation X) (hEFX : IsEFX v X)
(hU0 : ¬ U0Applicable v X) :
∀ s, IsSource v X s → ∀ g ∈ pool X,
(∃ j, j ≠ s ∧ v j (X j) < v j (insert g (X s))) ∧
(∀ Z, IsMinimalEnviedSubset v X (insert g (X s)) Z →
Z.card ≤ (X s).card) := by sorry
end LittleCharity.EFX
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.