Lemma 5 — Rule U1 increases welfare and preserves EFX
ProvedLittleCharity.EFX.lemma_5efxenvy-graphfair-divisionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an EFX allocation under monotone valuations, and suppose some agent values the pool above her own bundle, (Rule 's precondition). Let be an inclusion-wise minimal envied subset of and an agent with . Let be obtained by setting and for . Then is an allocation, it is EFX, welfare strictly increases, and the new pool is the one of Algorithm 2, line 8:
Rule is thus a strict welfare step whenever the pool itself is envied.
Formalization Note The EFX hypothesis on is Algorithm 1's invariant. "The most envious agent of " is encoded by taking any minimal envied subset of the pool and any agent who envies it, as Definition 3 and line 6 specify.
Preamble
import Mathlib import Definitions.Def_LittleCharity_EFX_Setting
Formal statement
namespace LittleCharity.EFX
theorem lemma_5 {n m : ℕ} (v : Fin n → Finset (Fin m) → ℝ)
(hmono : IsMonotoneVal v) (X : Fin n → Finset (Fin m))
(hX : IsPartialAllocation X) (hEFX : IsEFX v X)
(hU1 : ∃ k, v k (X k) < v k (pool X))
(i : Fin n) (Z : Finset (Fin m))
(hZ : IsMinimalEnviedSubset v X (pool X) Z)
(hi : v i (X i) < v i Z) :
let X' := Function.update X i Z
IsPartialAllocation X' ∧ IsEFX v X' ∧
welfare v X < welfare v X' ∧
pool X' = X i ∪ (pool X \ Z) := by sorry
end LittleCharity.EFX
Source
Chaudhury, Kavitha, Mehlhorn & Sgouritsa, A Little Charity Guarantees Almost Envy-Freeness, arXiv:1907.04596v3, p. 10, Algorithm 2 Rule U1 and Lemma 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.