Theorem 8 — existence of an EFX allocation with bounded charity
ProvedLittleCharity.EFX.theorem_8Let there be agents with normalized and monotone valuations over a set of indivisible goods. Then there is an allocation of pairwise disjoint bundles, with pool of unallocated goods, such that
- is EFX: for any agents and ;
- no agent envies the pool: for all ;
- the pool is smaller than the number of sources of the envy graph, and in particular smaller than :
Giving the pool away to charity therefore costs fewer than goods, none of which any agent prefers to her own bundle. The strong form is the one used to derive the paper's maximin-share and groupwise-maximin-share guarantees.
Formalization Note The hypothesis is added: with no agents the bound fails as soon as , and the paper always has agents. Valuations are real-valued; nonnegativity follows from normalized plus monotone. The theorem's last sentence ("Algorithm 1 determines such an allocation in at most iterations") is not posed: it requires a model of the algorithm's runs, and the count printed just before the theorem (at most applications of / and at most successive applications of between them) gives with , which can exceed .
import Mathlib import Definitions.Def_LittleCharity_EFX_Setting
namespace LittleCharity.EFX
theorem theorem_8 {n m : ℕ} (hn : 0 < n)
(v : Fin n → Finset (Fin m) → ℝ)
(hnorm : IsNormalized v) (hmono : IsMonotoneVal v) :
∃ X : Fin n → Finset (Fin m),
IsPartialAllocation X ∧ IsEFX v X ∧
(∀ i, v i (pool X) ≤ v i (X i)) ∧
(pool X).card < (sources v X).card ∧
(pool X).card < n := by sorry
end LittleCharity.EFX
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.