AFTD Auto-Formalizing Theoretical Domains

allocation_is_ef1_of_envy_free

theoremverified

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.

  1. 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.

    line 5

    uses Or.inl

      fun 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)
See it in the graphDiscuss this resultChallenge it