AFTD Auto-Formalizing Theoretical Domains

is_alpha_ef1_one_iff

theoremverified

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

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.

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

    line 5

    uses is_alpha_ef1, SocialChoice.FairDivision.Indivisible.IsEF1

      simp [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).

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

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