efx_three_pair_anchor_sanity
theoremverified
The starting allocation is envy-free with r+2 goods per bundle and one charity good; the lifted complete witness is EFX.
Statement
theorem efx_three_pair_anchor_sanity (r : ℕ) : (∀ i g, 0 < efx_three_pair_anchor_values r i g) ∧ (∀ i j : Fin 4, (∑ g, if efx_three_pair_anchor_start r g = j.castSucc then efx_three_pair_anchor_values r i g else 0) ≤ 100*r+10) ∧ (∀ i : Fin 4, efx_partial_nat_utility (efx_three_pair_anchor_values r) (efx_three_pair_anchor_start r) i = 100*r+10) ∧ efx_partial_nat (efx_three_pair_anchor_values r) (efx_three_pair_anchor_start r) ∧ is_efx_goods (fun i g => (efx_three_pair_anchor_values r i g : ℝ)) (efx_three_pair_anchor_witness r)
- Source
- Common-anchor lift of the OP-7 all-source three-split barrier; experiment 11720 and an unproved anchor-count projection.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 13
- efx_three_pair_anchor_valuesKeep the original nine goods and add 4r common anchors worth 100 each.
- efx_three_pair_anchor_startThe old pairs remain assigned to their owners, charity 8 is unallocated, and each agent receives r common anchors.
- efx_three_pair_anchor_witnessLift the explicit nine-good EFX completion while keeping the anchors round-robin.
- efx_partial_natNatural EFX inequalities for a partial allocation whose last owner label denotes unallocated goods.
- efx_partial_nat_utilityNatural utility in a partial allocation whose last owner label denotes unallocated goods.
- is_efx_goods_nat_cast_iffFor natural-number item values, EFX after casting values to the reals is equivalent to all natural-number inequalities comparing each…
- is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- efx_allsource_three_pair_valuesPositive four-agent values for four original pairs and one charity good.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - efx_allsource_three_pair_sanityThe partial allocation is envy-free; all values are positive and charity is owner-small; the explicit full EFX allocation preserves all…
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.
open Finsetdef efx_three_pair_anchor_sanity_equiv_prod (r : ℕ) : Fin r × Fin 4 ≃ Fin (4 * r) := (finProdFinEquiv (m := r) (n := 4)).trans (finCongr (mul_comm r 4))lemma efx_three_pair_anchor_sanity_equiv_prod_mod (r : ℕ) (x : Fin r × Fin 4) : (⟨(efx_three_pair_anchor_sanity_equiv_prod r x).val % 4, by omega⟩ : Fin 4) = x.2 := by ext dsimp [efx_three_pair_anchor_sanity_equiv_prod, finProdFinEquiv] simplemma efx_three_pair_anchor_sanity_sum_mod_four (r : ℕ) (j : Fin 4) : (∑ g : Fin (4 * r), (if (⟨g.val % 4, by omega⟩ : Fin 4) = j then (100 : ℕ) else 0)) = 100 * r := by rw [← (efx_three_pair_anchor_sanity_equiv_prod r).sum_comp] simp_rw [efx_three_pair_anchor_sanity_equiv_prod_mod] rw [Fintype.sum_prod_type] simp ringlemma efx_three_pair_anchor_sanity_start_natAdd_eq (r : ℕ) (j : Fin 4) (x : Fin (4 * r)) : (efx_three_pair_anchor_start r (Fin.natAdd 9 x) = j.castSucc) ↔ ((⟨x.val % 4, by omega⟩ : Fin 4) = j) := by unfold efx_three_pair_anchor_start have hge : ¬ ((Fin.natAdd 9 x : ℕ) < 9) := by simp rw [dif_neg hge] rw [Fin.ext_iff, Fin.ext_iff] simp [Fin.natAdd]lemma efx_three_pair_anchor_sanity_start_natAdd_val (r : ℕ) (i : Fin 4) (x : Fin (4 * r)) : efx_three_pair_anchor_values r i (Fin.natAdd 9 x) = 100 := by unfold efx_three_pair_anchor_values have hge : ¬ ((Fin.natAdd 9 x : ℕ) < 9) := by simp rw [dif_neg hge]lemma efx_three_pair_anchor_sanity_witness_natAdd_eq (r : ℕ) (j : Fin 4) (x : Fin (4 * r)) : (efx_three_pair_anchor_witness r (Fin.natAdd 9 x) = j) ↔ ((⟨x.val % 4, by omega⟩ : Fin 4) = j) := by unfold efx_three_pair_anchor_witness have hge : ¬ ((Fin.natAdd 9 x : ℕ) < 9) := by simp rw [dif_neg hge] rw [Fin.ext_iff, Fin.ext_iff] simp [Fin.natAdd]lemma efx_three_pair_anchor_sanity_start_castAdd (r : ℕ) (x : Fin 9) : efx_three_pair_anchor_start r (Fin.castAdd (4 * r) x) = (![0, 0, 1, 1, 2, 2, 3, 3, 4] : Fin 9 → Fin 5) x := by unfold efx_three_pair_anchor_start have hlt : (Fin.castAdd (4 * r) x : ℕ) < 9 := x.is_lt rw [dif_pos hlt]; rfllemma efx_three_pair_anchor_sanity_witness_castAdd (r : ℕ) (x : Fin 9) : efx_three_pair_anchor_witness r (Fin.castAdd (4 * r) x) = (![0, 0, 1, 3, 2, 0, 1, 2, 3] : Fin 9 → Fin 4) x := by unfold efx_three_pair_anchor_witness have hlt : (Fin.castAdd (4 * r) x : ℕ) < 9 := x.is_lt rw [dif_pos hlt]; rfllemma efx_three_pair_anchor_sanity_values_castAdd (r : ℕ) (i : Fin 4) (x : Fin 9) : efx_three_pair_anchor_values r i (Fin.castAdd (4 * r) x) = efx_allsource_three_pair_values i x := by unfold efx_three_pair_anchor_values have hlt : (Fin.castAdd (4 * r) x : ℕ) < 9 := x.is_lt rw [dif_pos hlt]; rfllemma efx_three_pair_anchor_sanity_sum_base_start (i j : Fin 4) : (∑ g : Fin 9, if (![0, 0, 1, 1, 2, 2, 3, 3, 4] g : Fin 5) = j.castSucc then efx_allsource_three_pair_values i g else 0) = efx_allsource_three_pair_values i (![0, 2, 4, 6] j) + efx_allsource_three_pair_values i (![1, 3, 5, 7] j) := by revert i j decidelemma efx_three_pair_anchor_sanity_start_bundle_sum (r : ℕ) (i j : Fin 4) : (∑ g : Fin (9 + 4 * r), if efx_three_pair_anchor_start r g = j.castSucc then efx_three_pair_anchor_values r i g else 0) = efx_allsource_three_pair_values i (![0, 2, 4, 6] j) + efx_allsource_three_pair_values i (![1, 3, 5, 7] j) + 100 * r := by rw [Fin.sum_univ_add] simp only [efx_three_pair_anchor_sanity_start_castAdd, efx_three_pair_anchor_sanity_values_castAdd, efx_three_pair_anchor_sanity_start_natAdd_eq, efx_three_pair_anchor_sanity_start_natAdd_val] rw [efx_three_pair_anchor_sanity_sum_base_start, efx_three_pair_anchor_sanity_sum_mod_four]lemma efx_three_pair_anchor_sanity_witness_bundle_sum (r : ℕ) (i k : Fin 4) : (∑ h ∈ bundle_of (efx_three_pair_anchor_witness r) k, efx_three_pair_anchor_values r i h) = (∑ h ∈ bundle_of (![0, 0, 1, 3, 2, 0, 1, 2, 3] : Fin 9 → Fin 4) k, efx_allsource_three_pair_values i h) + 100 * r := by dsimp [bundle_of] rw [sum_filter, sum_filter, Fin.sum_univ_add] simp only [efx_three_pair_anchor_sanity_witness_castAdd, efx_three_pair_anchor_sanity_values_castAdd, efx_three_pair_anchor_sanity_witness_natAdd_eq, efx_three_pair_anchor_sanity_start_natAdd_val] rw [efx_three_pair_anchor_sanity_sum_mod_four]lemma efx_three_pair_anchor_sanity_base_witness_le_plus_100 : ∀ i j : Fin 4, (∑ h ∈ bundle_of (![0, 0, 1, 3, 2, 0, 1, 2, 3] : Fin 9 → Fin 4) j, efx_allsource_three_pair_values i h) ≤ (∑ h ∈ bundle_of (![0, 0, 1, 3, 2, 0, 1, 2, 3] : Fin 9 → Fin 4) i, efx_allsource_three_pair_values i h) + 100 := by decidetheorem efx_three_pair_anchor_sanity (r : ℕ) : (∀ i g, 0 < efx_three_pair_anchor_values r i g) ∧ (∀ i j : Fin 4, (∑ g, if efx_three_pair_anchor_start r g = j.castSucc then efx_three_pair_anchor_values r i g else 0) ≤ 100*r+10) ∧ (∀ i : Fin 4, efx_partial_nat_utility (efx_three_pair_anchor_values r) (efx_three_pair_anchor_start r) i = 100*r+10) ∧ efx_partial_nat (efx_three_pair_anchor_values r) (efx_three_pair_anchor_start r) ∧ is_efx_goods (fun i g => (efx_three_pair_anchor_values r i g : ℝ)) (efx_three_pair_anchor_witness r) := by refine ⟨?_, ?_, ?_, ?_, ?_⟩ · intro i g unfold efx_three_pair_anchor_values split_ifs with h · exact efx_allsource_three_pair_sanity.1 i ⟨g.val, h⟩ · decide · intro i j rw [efx_three_pair_anchor_sanity_start_bundle_sum] have hle := efx_allsource_three_pair_sanity.2.1 i j omega · intro i dsimp [efx_partial_nat_utility] rw [efx_three_pair_anchor_sanity_start_bundle_sum] have heq := efx_allsource_three_pair_sanity.2.2.1 i omega · intro i j hij g hg dsimp [efx_partial_nat_utility] rw [efx_three_pair_anchor_sanity_start_bundle_sum, efx_three_pair_anchor_sanity_start_bundle_sum] have heq := efx_allsource_three_pair_sanity.2.2.1 i have hle := efx_allsource_three_pair_sanity.2.1 i j omega · apply (is_efx_goods_nat_cast_iff _ _).mpr intro i j hij g refine Fin.addCases ?_ ?_ g · intro x hx rw [efx_three_pair_anchor_sanity_witness_bundle_sum, efx_three_pair_anchor_sanity_witness_bundle_sum, efx_three_pair_anchor_sanity_values_castAdd] have hx_bundle : x ∈ bundle_of (![0, 0, 1, 3, 2, 0, 1, 2, 3] : Fin 9 → Fin 4) j := by dsimp [bundle_of] at hx ⊢ simp only [mem_filter, mem_univ, true_and] at hx ⊢ rw [← efx_three_pair_anchor_sanity_witness_castAdd r x] exact hx have hbase := (is_efx_goods_nat_cast_iff _ _).mp efx_allsource_three_pair_sanity.2.2.2.2.2.1 i j hij x hx_bundle linarith · intro y hy rw [efx_three_pair_anchor_sanity_witness_bundle_sum, efx_three_pair_anchor_sanity_witness_bundle_sum, efx_three_pair_anchor_sanity_start_natAdd_val] have hle := efx_three_pair_anchor_sanity_base_witness_le_plus_100 i j linarith