AFTD Auto-Formalizing Theoretical Domains

bivalued_two_agent_efx_family_feasible_of_envy_free_sides

theoremverified

For real r > 1, positive scales a0, a1 and natural numbers n1, n2, n3, n4: if (hA) unless n1 = n3 = n4 = 0 with n2 odd there is a weight-tie family allocation with U1 ≤ U0, V0 ≤ V1 + L1 and 0 ≤ (U0 − U1) + (V1 − V0) (the conclusion of bivalued_two_agent_efx_envy_free_zero_side, for these n1..n4 and r), and (hB) unless n1 = n2 = n4 = 0 with n3 odd there is one with U1 ≤ U0 + L0, V0 ≤ V1 and 0 ≤ (U0 − U1) + (V1 − V0) (the conclusion of bivalued_two_agent_efx_envy_free_one_side), then bivalued_two_agent_efx_family_feasible n1 n2 n3 n4 r a0 a1 holds.

Statement

theorem bivalued_two_agent_efx_family_feasible_of_envy_free_sides (r a0 a1 : ℝ) (hr : 1 < r)
    (h0 : 0 < a0) (h1 : 0 < a1) (n1 n2 n3 n4 : ℕ)
    (hA : ¬ (n1 = 0 ∧ n3 = 0 ∧ n4 = 0 ∧ n2 % 2 = 1) →
    ∃ a b c d : ℕ, a ≤ n1 ∧ b ≤ n2 ∧ c ≤ n3 ∧ d ≤ n4 ∧
      ((b = 0 ∧ c = n3) ∨ (a = 0 ∧ b = 0 ∧ d = 0) ∨ (a = n1 ∧ c = n3 ∧ d = n4)) ∧
      (let U0 : ℝ := (a : ℝ) + (b : ℝ) + r * (c : ℝ) + r * (d : ℝ)
       let U1 : ℝ := ((n1 - a : ℕ) : ℝ) + ((n2 - b : ℕ) : ℝ) + r * ((n3 - c : ℕ) : ℝ)
         + r * ((n4 - d : ℕ) : ℝ)
       let V0 : ℝ := (a : ℝ) + r * (b : ℝ) + (c : ℝ) + r * (d : ℝ)
       let V1 : ℝ := ((n1 - a : ℕ) : ℝ) + r * ((n2 - b : ℕ) : ℝ) + ((n3 - c : ℕ) : ℝ)
         + r * ((n4 - d : ℕ) : ℝ)
       let L1 : ℝ := if a + c ≥ 1 then 1 else if b + d ≥ 1 then r else 0
       U1 ≤ U0 ∧ V0 ≤ V1 + L1 ∧ 0 ≤ (U0 - U1) + (V1 - V0)))
    (hB : ¬ (n1 = 0 ∧ n2 = 0 ∧ n4 = 0 ∧ n3 % 2 = 1) →
    ∃ a b c d : ℕ, a ≤ n1 ∧ b ≤ n2 ∧ c ≤ n3 ∧ d ≤ n4 ∧
      ((b = 0 ∧ c = n3) ∨ (a = 0 ∧ b = 0 ∧ d = 0) ∨ (a = n1 ∧ c = n3 ∧ d = n4)) ∧
      (let U0 : ℝ := (a : ℝ) + (b : ℝ) + r * (c : ℝ) + r * (d : ℝ)
       let U1 : ℝ := ((n1 - a : ℕ) : ℝ) + ((n2 - b : ℕ) : ℝ) + r * ((n3 - c : ℕ) : ℝ)
         + r * ((n4 - d : ℕ) : ℝ)
       let V0 : ℝ := (a : ℝ) + r * (b : ℝ) + (c : ℝ) + r * (d : ℝ)
       let V1 : ℝ := ((n1 - a : ℕ) : ℝ) + r * ((n2 - b : ℕ) : ℝ) + ((n3 - c : ℕ) : ℝ)
         + r * ((n4 - d : ℕ) : ℝ)
       let L0 : ℝ := if (n1 - a) + (n2 - b) ≥ 1 then 1 else if (n3 - c) + (n4 - d) ≥ 1 then r else 0
       U1 ≤ U0 + L0 ∧ V0 ≤ V1 ∧ 0 ≤ (U0 - U1) + (V1 - V0))) :
    bivalued_two_agent_efx_family_feasible n1 n2 n3 n4 r a0 a1
Source
arXiv:2610.14994 (Section 4.2, Theorem 4.1), reduction step for bivalued_two_agent_efx_family_feasible_all
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • bivalued_two_agent_efx_family_feasibleEFX version of the two-agent common-ratio bivalued arithmetic. Goods are of four types LL, LH, HL, HH (worth (1,1), (1,r), (r,1), (r,r) to…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

The proof, explained

The proof establishes the existence of an EFX family allocation satisfying a positive weighted-tie condition a0 * (U0 - U1) + a1 * (V1 - V0) ≥ 0 by comparing the scale factors a0 and a1. If a1 ≤ a0, hypothesis hA guarantees an allocation where agent 0 is envy-free (U0 - U1 ≥ 0), allowing the unweighted tie condition to scale to the weighted one; symmetrically, if a0 ≤ a1, hypothesis hB is used where agent 1 is envy-free. The single exceptional parity case in each branch—where only items of type 2 (respectively, type 3) exist in an odd quantity 2m + 1—is handled by an explicit near-equitable split of m + 1 versus m items, thresholded against the valuation ratio r.

  1. It suffices to prove feasibility in the two cases a1 ≤ a0 and a0 ≤ a1.

    We unfold the definition of `bivalued_two_agent_efx_family_feasible` and case-split on whether a1 ≤ a0 or a0 ≤ a1 using the totality of the order on ℝ (`le_total`).

    lines 26–27

    uses le_total

      unfold bivalued_two_agent_efx_family_feasible
      rcases le_total a1 a0 with ha | ha
  2. When a1 ≤ a0, either n1 = n3 = n4 = 0 with n2 = 2m + 1 odd, or hypothesis hA applies.

    We check whether the item counts match the exception of hypothesis hA. When they do, n1 = n3 = n4 = 0 and n2 is odd, so n2 can be expressed as 2m + 1 with m = n2 / 2 by integer arithmetic (`omega`).

    lines 28–30

      · by_cases hs : n1 = 0 ∧ n3 = 0 ∧ n4 = 0 ∧ n2 % 2 = 1
        · obtain ⟨rfl, rfl, rfl, hodd⟩ := hs
          obtain ⟨m, rfl⟩ : ∃ m, n2 = 2 * m + 1 := ⟨n2 / 2, by omega⟩
  3. When a1 ≤ a0, n2 = 2m + 1, and a1 * r ≤ a0, allocating m + 1 items of type 2 to agent 0 is feasible. automation

    We test whether a1 * r ≤ a0. In that case, we select the candidate allocation (a, b, c, d) = (0, m + 1, 0, 0), leaving m items of type 2 to agent 1. This candidate satisfies the third branch of the family condition (a = n1, c = n3, d = n4). After simplifying integer arithmetic and coercions (`Nat.sub_self`, `Nat.cast_zero`, `Nat.cast_add`, `Nat.cast_one`, `zero_add`, `add_zero`, `le_refl`), the EFX bounds and the weighted tie inequality are closed by non-linear arithmetic (`nlinarith`).

    lines 31–36

    uses le_refl, Or.inr, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero

          by_cases hc : a1 * r ≤ a0
          · refine ⟨0, m + 1, 0, 0, le_refl _, by omega, le_refl _, le_refl _,
              Or.inr (Or.inr ⟨rfl, rfl, rfl⟩), ?_⟩
            have e : 2 * m + 1 - (m + 1) = m := by omega
            simp only [e, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero]
            refine ⟨?_, ?_, ?_⟩ <;> (try split_ifs) <;> nlinarith
  4. When a1 ≤ a0, n2 = 2m + 1, and a0 < a1 * r, allocating m items of type 2 to agent 0 is feasible. automation

    In the complementary case a0 < a1 * r, we choose the candidate allocation (a, b, c, d) = (0, m, 0, 0), which gives m + 1 items of type 2 to agent 1. This satisfies the third family branch via `Or.inr`. After algebraic simplification of expressions with `Nat.sub_self`, `Nat.cast_zero`, `Nat.cast_add`, `Nat.cast_one`, `zero_add`, `add_zero`, and `le_refl`, non-linear arithmetic (`nlinarith`) confirms the EFX conditions and the weighted tie inequality.

    lines 37–41

    uses le_refl, Or.inr, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero

          · refine ⟨0, m, 0, 0, le_refl _, by omega, le_refl _, le_refl _,
              Or.inr (Or.inr ⟨rfl, rfl, rfl⟩), ?_⟩
            have e : 2 * m + 1 - m = m + 1 := by omega
            simp only [e, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero]
            refine ⟨?_, ?_, ?_⟩ <;> (try split_ifs) <;> nlinarith
  5. When a1 ≤ a0 and the exceptional condition fails, the allocation provided by hypothesis hA is feasible. automation

    Applying hypothesis hA yields an allocation (a, b, c, d) satisfying U1 ≤ U0, V0 ≤ V1 + L1, and 0 ≤ (U0 - U1) + (V1 - V0). Since L0 ≥ 0, U1 ≤ U0 implies U1 ≤ U0 + L0. Furthermore, because agent 0 is envy-free (U0 - U1 ≥ 0) and a0 ≥ a1 > 0, weighting U0 - U1 by a0 rather than a1 gives a0 * (U0 - U1) + a1 * (V1 - V0) ≥ a1 * ((U0 - U1) + (V1 - V0)) ≥ 0, which is closed by linear arithmetic (`linarith`, `nlinarith`).

    lines 42–51

        · obtain ⟨a, b, c, d, ha', hb, hc, hd, hfam, h⟩ :=
            hA hs
          refine ⟨a, b, c, d, ha', hb, hc, hd, hfam, ?_⟩
          intro U0 U1 V0 V1 L0 L1
          obtain ⟨hX, hY, hXY⟩ := h
          have hL0 : 0 ≤ L0 := by
            simp only [L0]; split_ifs <;> linarith
          refine ⟨by linarith, hY, ?_⟩
          have hX' : 0 ≤ U0 - U1 := by linarith
          nlinarith
  6. When a0 ≤ a1, either n1 = n2 = n4 = 0 with n3 = 2m + 1 odd, or hypothesis hB applies.

    We check whether the item counts match the exception of hypothesis hB. If they do, n1 = n2 = n4 = 0 and n3 is odd, so n3 = 2m + 1 with m = n3 / 2 by integer arithmetic (`omega`).

    lines 52–54

      · by_cases hs : n1 = 0 ∧ n2 = 0 ∧ n4 = 0 ∧ n3 % 2 = 1
        · obtain ⟨rfl, rfl, rfl, hodd⟩ := hs
          obtain ⟨m, rfl⟩ : ∃ m, n3 = 2 * m + 1 := ⟨n3 / 2, by omega⟩
  7. When a0 ≤ a1, n3 = 2m + 1, and a1 ≤ a0 * r, allocating m + 1 items of type 3 to agent 0 is feasible. automation

    We test whether a1 ≤ a0 * r. If so, allocating (a, b, c, d) = (0, 0, m + 1, 0) leaves m items of type 3 for agent 1. This satisfies the second branch of the family condition (a = 0, b = 0, d = 0) via `Or.inr` and `Or.inl`. After simplifying arithmetic and coercions (`Nat.sub_self`, `Nat.cast_zero`, `Nat.cast_add`, `Nat.cast_one`, `zero_add`, `add_zero`, `le_refl`), `nlinarith` verifies the feasibility bounds.

    lines 55–60

    uses le_refl, Or.inr, Or.inl, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero

          by_cases hc : a1 ≤ a0 * r
          · refine ⟨0, 0, m + 1, 0, le_refl _, le_refl _, by omega, le_refl _,
              Or.inr (Or.inl ⟨rfl, rfl, rfl⟩), ?_⟩
            have e : 2 * m + 1 - (m + 1) = m := by omega
            simp only [e, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero]
            refine ⟨?_, ?_, ?_⟩ <;> (try split_ifs) <;> nlinarith
  8. When a0 ≤ a1, n3 = 2m + 1, and a0 * r < a1, allocating m items of type 3 to agent 0 is feasible. automation

    In the complementary subcase a0 * r < a1, we allocate (a, b, c, d) = (0, 0, m, 0), leaving m + 1 items of type 3 for agent 1. The middle family condition is satisfied via `Or.inr` and `Or.inl`. After simplification using `Nat.sub_self`, `Nat.cast_zero`, `Nat.cast_add`, `Nat.cast_one`, `zero_add`, `add_zero`, and `le_refl`, `nlinarith` completes the verification.

    lines 61–65

    uses le_refl, Or.inr, Or.inl, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero

          · refine ⟨0, 0, m, 0, le_refl _, le_refl _, by omega, le_refl _,
              Or.inr (Or.inl ⟨rfl, rfl, rfl⟩), ?_⟩
            have e : 2 * m + 1 - m = m + 1 := by omega
            simp only [e, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero]
            refine ⟨?_, ?_, ?_⟩ <;> (try split_ifs) <;> nlinarith
  9. When a0 ≤ a1 and the exceptional condition fails, the allocation provided by hypothesis hB is feasible. automation

    Applying hypothesis hB yields an allocation with U1 ≤ U0 + L0, V0 ≤ V1, and 0 ≤ (U0 - U1) + (V1 - V0). Since L1 ≥ 0, V0 ≤ V1 implies V0 ≤ V1 + L1. Because agent 1 is envy-free (V1 - V0 ≥ 0) and a1 ≥ a0 > 0, weighting V1 - V0 by a1 gives a0 * (U0 - U1) + a1 * (V1 - V0) ≥ a0 * ((U0 - U1) + (V1 - V0)) ≥ 0, which is closed by linear arithmetic (`linarith`, `nlinarith`).

    lines 66–75

        · obtain ⟨a, b, c, d, ha', hb, hc, hd, hfam, h⟩ :=
            hB hs
          refine ⟨a, b, c, d, ha', hb, hc, hd, hfam, ?_⟩
          intro U0 U1 V0 V1 L0 L1
          obtain ⟨hX, hY, hXY⟩ := h
          have hL1 : 0 ≤ L1 := by
            simp only [L1]; split_ifs <;> linarith
          refine ⟨hX, by linarith, ?_⟩
          have hY' : 0 ≤ V1 - V0 := by linarith
          nlinarith
le_total
for any elements a and b in a linear order, a ≤ b or b ≤ a
le_refl
in any preorder, every element is less than or equal to itself: a ≤ a
Or.inr
given a proof of B, concludes the disjunction A ∨ B
Or.inl
given a proof of A, concludes the disjunction A ∨ B
Nat.sub_self
for any natural number n, n - n = 0
Nat.cast_zero
the coercion of the natural number 0 into an additive monoid with one is 0
Nat.cast_add
the coercion of m + n equals the sum of the coercions of m and n
Nat.cast_one
the coercion of the natural number 1 into an additive monoid with one is 1
zero_add
adding zero on the left leaves an element unchanged: 0 + a = a
add_zero
adding zero on the right leaves an element unchanged: a + 0 = a

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 bivalued_two_agent_efx_family_feasible_of_envy_free_sides (r a0 a1 : ℝ) (hr : 1 < r)    (h0 : 0 < a0) (h1 : 0 < a1) (n1 n2 n3 n4 : ℕ)    (hA : ¬ (n1 = 0 ∧ n3 = 0 ∧ n4 = 0 ∧ n2 % 2 = 1) →    ∃ a b c d : ℕ, a ≤ n1 ∧ b ≤ n2 ∧ c ≤ n3 ∧ d ≤ n4 ∧      ((b = 0 ∧ c = n3) ∨ (a = 0 ∧ b = 0 ∧ d = 0) ∨ (a = n1 ∧ c = n3 ∧ d = n4)) ∧      (let U0 : ℝ := (a : ℝ) + (b : ℝ) + r * (c : ℝ) + r * (d : ℝ)       let U1 : ℝ := ((n1 - a : ℕ) : ℝ) + ((n2 - b : ℕ) : ℝ) + r * ((n3 - c : ℕ) : ℝ)         + r * ((n4 - d : ℕ) : ℝ)       let V0 : ℝ := (a : ℝ) + r * (b : ℝ) + (c : ℝ) + r * (d : ℝ)       let V1 : ℝ := ((n1 - a : ℕ) : ℝ) + r * ((n2 - b : ℕ) : ℝ) + ((n3 - c : ℕ) : ℝ)         + r * ((n4 - d : ℕ) : ℝ)       let L1 : ℝ := if a + c ≥ 1 then 1 else if b + d ≥ 1 then r else 0       U1 ≤ U0 ∧ V0 ≤ V1 + L1 ∧ 0 ≤ (U0 - U1) + (V1 - V0)))    (hB : ¬ (n1 = 0 ∧ n2 = 0 ∧ n4 = 0 ∧ n3 % 2 = 1) →    ∃ a b c d : ℕ, a ≤ n1 ∧ b ≤ n2 ∧ c ≤ n3 ∧ d ≤ n4 ∧      ((b = 0 ∧ c = n3) ∨ (a = 0 ∧ b = 0 ∧ d = 0) ∨ (a = n1 ∧ c = n3 ∧ d = n4)) ∧      (let U0 : ℝ := (a : ℝ) + (b : ℝ) + r * (c : ℝ) + r * (d : ℝ)       let U1 : ℝ := ((n1 - a : ℕ) : ℝ) + ((n2 - b : ℕ) : ℝ) + r * ((n3 - c : ℕ) : ℝ)         + r * ((n4 - d : ℕ) : ℝ)       let V0 : ℝ := (a : ℝ) + r * (b : ℝ) + (c : ℝ) + r * (d : ℝ)       let V1 : ℝ := ((n1 - a : ℕ) : ℝ) + r * ((n2 - b : ℕ) : ℝ) + ((n3 - c : ℕ) : ℝ)         + r * ((n4 - d : ℕ) : ℝ)       let L0 : ℝ := if (n1 - a) + (n2 - b) ≥ 1 then 1 else if (n3 - c) + (n4 - d) ≥ 1 then r else 0       U1 ≤ U0 + L0 ∧ V0 ≤ V1 ∧ 0 ≤ (U0 - U1) + (V1 - V0))) :    bivalued_two_agent_efx_family_feasible n1 n2 n3 n4 r a0 a1 := by  unfold bivalued_two_agent_efx_family_feasible  rcases le_total a1 a0 with ha | ha  · by_cases hs : n1 = 0 ∧ n3 = 0 ∧ n4 = 0 ∧ n2 % 2 = 1    · obtain ⟨rfl, rfl, rfl, hodd⟩ := hs      obtain ⟨m, rfl⟩ : ∃ m, n2 = 2 * m + 1 := ⟨n2 / 2, by omega⟩      by_cases hc : a1 * r ≤ a0      · refine ⟨0, m + 1, 0, 0, le_refl _, by omega, le_refl _, le_refl _,          Or.inr (Or.inr ⟨rfl, rfl, rfl⟩), ?_⟩        have e : 2 * m + 1 - (m + 1) = m := by omega        simp only [e, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero]        refine ⟨?_, ?_, ?_⟩ <;> (try split_ifs) <;> nlinarith      · refine ⟨0, m, 0, 0, le_refl _, by omega, le_refl _, le_refl _,          Or.inr (Or.inr ⟨rfl, rfl, rfl⟩), ?_⟩        have e : 2 * m + 1 - m = m + 1 := by omega        simp only [e, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero]        refine ⟨?_, ?_, ?_⟩ <;> (try split_ifs) <;> nlinarith    · obtain ⟨a, b, c, d, ha', hb, hc, hd, hfam, h⟩ :=        hA hs      refine ⟨a, b, c, d, ha', hb, hc, hd, hfam, ?_⟩      intro U0 U1 V0 V1 L0 L1      obtain ⟨hX, hY, hXY⟩ := h      have hL0 : 0 ≤ L0 := by        simp only [L0]; split_ifs <;> linarith      refine ⟨by linarith, hY, ?_⟩      have hX' : 0 ≤ U0 - U1 := by linarith      nlinarith  · by_cases hs : n1 = 0 ∧ n2 = 0 ∧ n4 = 0 ∧ n3 % 2 = 1    · obtain ⟨rfl, rfl, rfl, hodd⟩ := hs      obtain ⟨m, rfl⟩ : ∃ m, n3 = 2 * m + 1 := ⟨n3 / 2, by omega⟩      by_cases hc : a1 ≤ a0 * r      · refine ⟨0, 0, m + 1, 0, le_refl _, le_refl _, by omega, le_refl _,          Or.inr (Or.inl ⟨rfl, rfl, rfl⟩), ?_⟩        have e : 2 * m + 1 - (m + 1) = m := by omega        simp only [e, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero]        refine ⟨?_, ?_, ?_⟩ <;> (try split_ifs) <;> nlinarith      · refine ⟨0, 0, m, 0, le_refl _, le_refl _, by omega, le_refl _,          Or.inr (Or.inl ⟨rfl, rfl, rfl⟩), ?_⟩        have e : 2 * m + 1 - m = m + 1 := by omega        simp only [e, Nat.sub_self, Nat.cast_zero, Nat.cast_add, Nat.cast_one, zero_add, add_zero]        refine ⟨?_, ?_, ?_⟩ <;> (try split_ifs) <;> nlinarith    · obtain ⟨a, b, c, d, ha', hb, hc, hd, hfam, h⟩ :=        hB hs      refine ⟨a, b, c, d, ha', hb, hc, hd, hfam, ?_⟩      intro U0 U1 V0 V1 L0 L1      obtain ⟨hX, hY, hXY⟩ := h      have hL1 : 0 ≤ L1 := by        simp only [L1]; split_ifs <;> linarith      refine ⟨hX, by linarith, ?_⟩      have hY' : 0 ≤ V1 - V0 := by linarith      nlinarith
See it in the graphDiscuss this resultChallenge it