bivalued_two_agent_efx_family_feasible_of_envy_free_sides
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— 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.
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`).
uses
le_totalunfold bivalued_two_agent_efx_family_feasible rcases le_total a1 a0 with ha | ha
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`).
· 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⟩
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`).
uses
le_refl,Or.inr,Nat.sub_self,Nat.cast_zero,Nat.cast_add,Nat.cast_one,zero_add,add_zeroby_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
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.
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
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`).
· 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
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`).
· 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⟩
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.
uses
le_refl,Or.inr,Or.inl,Nat.sub_self,Nat.cast_zero,Nat.cast_add,Nat.cast_one,zero_add,add_zeroby_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
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.
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
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`).
· 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
- In the parity subcases (lines 31–41 and 55–65), verifying that the candidate allocations satisfy the EFX and feasibility inequalities is handled by `split_ifs` expanding the piecewise definitions of L0 and L1 followed by `nlinarith`.
- In the general cases (lines 42–51 and 66–75), the fact that the unweighted sum inequality scales to the weighted inequality relies on one margin being non-negative ($U_0 - U_1 \ge 0$ or $V_1 - V_0 \ge 0$), which allows shifting weight between the two terms using $a_1 \le a_0$ or $a_0 \le a_1$.
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 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