Lemma 2 — eliminating an envy cycle preserves EFX and raises welfare
ProvedLittleCharity.EFX.lemma_2efxenvy-graphfair-divisionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be an allocation and let be a cycle of distinct agents in the envy graph , i.e. for every (indices modulo ). Let be the allocation with for and for agents off the cycle. Then
- is again an allocation (pairwise disjoint bundles) with the same pool, ;
- if is EFX, then is EFX;
- the social welfare strictly increases:
This decycling step lets the algorithm keep the envy graph acyclic while preserving EFX and making strict progress in welfare.
Formalization Note The cycle is a nonempty duplicate-free list of agents, and the edge condition says each agent of envies her successor under Mathlib's cyclic permutation List.formPerm c; then formPerm. Item 1 is the well-formedness Algorithm 1 relies on and is added to the page's statement; it needs the input to be an allocation, which the page presupposes.
Preamble
import Mathlib import Definitions.Def_LittleCharity_EFX_Setting
Formal statement
namespace LittleCharity.EFX
theorem lemma_2 {n m : ℕ} (v : Fin n → Finset (Fin m) → ℝ)
(X : Fin n → Finset (Fin m)) (hX : IsPartialAllocation X)
(c : List (Fin n)) (hc : c.Nodup) (hne : c ≠ [])
(hcycle : ∀ a ∈ c, Envies v X a (c.formPerm a)) :
IsPartialAllocation (X ∘ c.formPerm) ∧
pool (X ∘ c.formPerm) = pool X ∧
(IsEFX v X → IsEFX v (X ∘ c.formPerm)) ∧
welfare v X < welfare v (X ∘ c.formPerm) := by sorry
end LittleCharity.EFX
Source
Chaudhury, Kavitha, Mehlhorn & Sgouritsa, A Little Charity Guarantees Almost Envy-Freeness, arXiv:1907.04596v3, p. 8, Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.