is_alpha_ef1_one_iff
1-EF1 is EF1.
Statement
theorem is_alpha_ef1_one_iff {N G : Type*} [DecidableEq G] (v : SocialChoice.FairDivision.Indivisible.Valuation N G) (A : SocialChoice.FairDivision.Indivisible.Allocation N G) : is_alpha_ef1 1 v A ↔ SocialChoice.FairDivision.Indivisible.IsEF1 v A
- Source
- Sanity lemma for is_alpha_ef1 (arXiv:2610.23686 Definition 1: when α = 1 the allocation is EF1).
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_alpha_ef1For α in [0,1], an allocation is α-EF1 if for every pair of agents i ≠ j with A_j nonempty there is a good g in A_j with v_i(A_i) ≥ α ·…
- SocialChoice.FairDivision.Indivisible.IsEF1Envy-free up to one good (EF1): for any envied bundle, removing *some* item from it eliminates the envy.…
- SocialChoice.FairDivision.Indivisible.ValuationAn abstract valuation assigns a real value to each agent-bundle pair.
val i Sis the value agentiassigns to bundleS. Lives in… - SocialChoice.FairDivision.Indivisible.AllocationAn allocation assigns each agent
i : Na bundle (a finite subset of goodsG). This is a plain function type alias. The partition…
The proof, explained
The theorem states that 1-EF1 (approximate envy-freeness up to one good with factor α = 1) is equivalent to standard EF1. Unfolding both definitions, the only difference is the factor of 1 multiplying the valuation of the bundle without the removed good. Because 1 * x = x, the two conditions are identical.
An allocation A satisfies 1-EF1 under valuation v if and only if it satisfies standard EF1 under v. automation
Expanding the definitions of `is_alpha_ef1` and `SocialChoice.FairDivision.Indivisible.IsEF1`, the condition for 1-EF1 requires that 1 * v_i(A_j \ {g}) ≤ v_i(A_i). Since 1 * x = x for real numbers, this condition is identical to the standard EF1 requirement that v_i(A_j \ {g}) ≤ v_i(A_i). The simplifier unrolls both definitions, applies the multiplicative identity, and closes the goal.
uses
is_alpha_ef1,SocialChoice.FairDivision.Indivisible.IsEF1simp [is_alpha_ef1, SocialChoice.FairDivision.Indivisible.IsEF1]
is_alpha_ef1- The definition of α-envy-freeness up to one item: for any distinct agents i and j with nonempty A_j, there exists a good g in A_j such that α * v_i(A_j \ {g}) ≤ v_i(A_i).
SocialChoice.FairDivision.Indivisible.IsEF1- The standard definition of envy-freeness up to one item (EF1): for any distinct agents i and j with nonempty A_j, there exists a good g in A_j such that v_i(A_j \ {g}) ≤ v_i(A_i).
- The equivalence follows by unfolding the definitions and the algebraic identity 1 * x = x, which the simplifier executes in a single step.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem is_alpha_ef1_one_iff {N G : Type*} [DecidableEq G] (v : SocialChoice.FairDivision.Indivisible.Valuation N G) (A : SocialChoice.FairDivision.Indivisible.Allocation N G) : is_alpha_ef1 1 v A ↔ SocialChoice.FairDivision.Indivisible.IsEF1 v A := by simp [is_alpha_ef1, SocialChoice.FairDivision.Indivisible.IsEF1]