allocation_is_ef1_of_envy_free
An envy-free allocation is EF1.
Statement
theorem allocation_is_ef1_of_envy_free {N M : Type*} [Fintype M] [DecidableEq N] [DecidableEq M] (v : N → Finset M → ℝ) (A : M → N) (h : ∀ i j, v i (allocation_bundle A j) ≤ v i (allocation_bundle A i)) : allocation_is_ef1 v A
- Source
- Sanity lemma for EF1, arXiv:2610.14994 (Best-of-both-worlds fair division via subsidies), Sec. 2.
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- allocation_is_ef1An allocation is envy-free up to one good (EF1) if for all agents i, j, either i does not envy j, or removing some good from j's bundle…
- allocation_bundleFor a complete allocation A of the goods M to the agents N (each good to one agent), the bundle of agent i is the set of goods A assigns…
The proof, explained
An allocation is EF1 (envy-free up to one good) if for any pair of agents i and j, agent i either does not envy agent j at all, or envies j by at most a single item. Because the allocation is already assumed to be envy-free, agent i never envies agent j in the first place. The proof simply satisfies the EF1 condition by choosing the first branch of its defining disjunction for every pair of agents.
The allocation A satisfies the EF1 condition
For any agents i and j, the envy-freeness hypothesis h asserts directly that v i (allocation_bundle A j) ≤ v i (allocation_bundle A i). The definition of EF1 requires that either this inequality holds or there is an item in j's bundle whose removal restores the inequality. Providing h i j to the left disjunct via Or.inl satisfies the condition for all i and j.
uses
Or.inlfun i j => Or.inl (h i j)
Or.inl- from a proof of P, concludes the disjunction P ∨ Q
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem allocation_is_ef1_of_envy_free {N M : Type*} [Fintype M] [DecidableEq N] [DecidableEq M] (v : N → Finset M → ℝ) (A : M → N) (h : ∀ i j, v i (allocation_bundle A j) ≤ v i (allocation_bundle A i)) : allocation_is_ef1 v A := fun i j => Or.inl (h i j)