AFTD Auto-Formalizing Theoretical Domains

efx_pareto_lock_padded_sanity

theoremverified

For every k the padded starting allocation is partial EFX and has the claimed baseline utilities.

Statement

theorem efx_pareto_lock_padded_sanity (k : ℕ) :
  efx_partial_nat (efx_pareto_lock_padded_values k) (efx_pareto_lock_padded_owner k) ∧
  ∀ i : Fin 4, efx_partial_nat_utility (efx_pareto_lock_padded_values k) (efx_pareto_lock_padded_owner k) i =
    efx_pareto_lock_padded_baseline k i
Source
Arbitrary source-bundle padding of the OP-7 Pareto-maximal locked-good obstruction, experiments 11497 and 11498.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 12

The proof, explained

The proof shows that the padded allocation is partial EFX and achieves the claimed baseline utilities. Valuations on the original 8 items are scaled by 2k + 1, and 2k tail items of value 1 each are added, allocated equally to agents 0 and 1. Because the base allocation already enjoys strict slack margins of at least 5 and 6, scaling by 2k + 1 amplifies this slack enough to absorb the at most k additional utility introduced by the tail items.

  1. For each agent i ∈ {0, 1, 2, 3}, their utility under the padded allocation is (2k + 1) times their base baseline utility, plus k if i ∈ {0, 1} and 0 otherwise.

    We unfold the definitions of utility, valuations, and owner in the padded instance, and split the sum over all 8 + 2k goods into the first 8 goods and the 2k tail goods using Fin.sum_univ_add. For the first 8 goods, exhaustive evaluation over all four agents verifies the unpadded base utility, and factoring out 2k + 1 gives (2k + 1) * baseline(i). For the 2k tail goods, splitting into two blocks of k items shows that agent 0 receives the first k items and agent 1 receives the next k items, each of value 1, while agents 2 and 3 receive none. Combining these gives the claimed formula.

    lines 5–25

    uses Fin.sum_univ_add, Fin.addCases_left, Fin.addCases_right, Finset.mul_sum, Finset.sum_congr, Fin.val_castAdd, Fin.val_natAdd, Fin.isLt, if_true, if_false, Finset.sum_const

      have hutil : ∀ i : Fin 4, efx_partial_nat_utility (efx_pareto_lock_padded_values k) (efx_pareto_lock_padded_owner k) i
          = (k+k+1) * efx_pareto_lock_baseline i + (if i = 0 ∨ i = 1 then k else 0) := by
        intro i
        unfold efx_partial_nat_utility efx_pareto_lock_padded_values efx_pareto_lock_padded_owner efx_partial_scaled_tail
        rw [Fin.sum_univ_add]
        simp only [Fin.addCases_left, Fin.addCases_right]
        have hbase : (∑ x : Fin 8, if ![1,0,0,0,1,2,4,3] x = i.castSucc then efx_pareto_lock_values i x else 0) = efx_pareto_lock_baseline i := by
          fin_cases i <;> decide
        have hmul : (∑ x : Fin 8, if ![1,0,0,0,1,2,4,3] x = i.castSucc then (k+k+1) * efx_pareto_lock_values i x else 0) = (k+k+1) * efx_pareto_lock_baseline i := by
          rw [← hbase, Finset.mul_sum]
          apply Finset.sum_congr rfl
          intro x _
          by_cases hc : ![1,0,0,0,1,2,4,3] x = i.castSucc <;> simp [hc]
        have htail : (∑ x : Fin (k+k), if (if (x:ℕ) < k then (0:Fin 5) else 1) = i.castSucc then (1:ℕ) else 0)
            = (if i = 0 ∨ i = 1 then k else 0) := by
          rw [Fin.sum_univ_add]
          simp only [Fin.val_castAdd, Fin.val_natAdd]
          have h2 : ∀ x : Fin k, ¬ (k + (x:ℕ) < k) := by intro x; omega
          simp only [Fin.isLt, if_true, h2, if_false]
          fin_cases i <;> simp [Finset.sum_const]
        rw [hmul, htail]
  2. For every agent i ∈ {0, 1, 2, 3}, the utility in the original 8-item instance equals the baseline utility. automation

    The equality between the utility under the base allocation ![1,0,0,0,1,2,4,3] and the baseline vector is verified for each of the four agents by exhaustive computation (`fin_cases i <;> decide`).

    lines 26–27

      have hutil_old : ∀ i : Fin 4, efx_pareto_lock_utility ![1,0,0,0,1,2,4,3] i = efx_pareto_lock_baseline i := by
        intro i; fin_cases i <;> decide
  3. For any agents i and j, agent i's valuation of j's padded bundle equals (2k + 1) times i's valuation of j's base bundle, plus k if j ∈ {0, 1} and 0 otherwise.

    Similarly to the utility calculation, the sum defining agent i's valuation of j's bundle over all 8 + 2k goods is split into the original 8 goods and the 2k tail goods. Factoring out 2k + 1 on the first 8 items gives the scaled base valuation, and evaluating the tail shows that agent j receives k items of value 1 if j ∈ {0, 1} and 0 items otherwise.

    lines 28–45

    uses Fin.sum_univ_add, Fin.addCases_left, Fin.addCases_right, Finset.mul_sum, Finset.sum_congr, Fin.val_castAdd, Fin.val_natAdd, Fin.isLt, if_true, if_false, Finset.sum_const

      have hS : ∀ i j : Fin 4,
          (∑ h : Fin (8+(k+k)), if efx_pareto_lock_padded_owner k h = j.castSucc then efx_pareto_lock_padded_values k i h else 0)
          = (k+k+1) * (∑ x : Fin 8, if ![1,0,0,0,1,2,4,3] x = j.castSucc then efx_pareto_lock_values i x else 0)
            + (if j = 0 ∨ j = 1 then k else 0) := by
        intro i j
        unfold efx_pareto_lock_padded_owner efx_pareto_lock_padded_values efx_partial_scaled_tail
        rw [Fin.sum_univ_add]
        simp only [Fin.addCases_left, Fin.addCases_right]
        congr 1
        · rw [Finset.mul_sum]
          apply Finset.sum_congr rfl
          intro x _
          by_cases hc : ![1,0,0,0,1,2,4,3] x = j.castSucc <;> simp [hc]
        · rw [Fin.sum_univ_add]
          simp only [Fin.val_castAdd, Fin.val_natAdd]
          have h2 : ∀ x : Fin k, ¬ (k + (x:ℕ) < k) := by intro x; omega
          simp only [Fin.isLt, if_true, h2, if_false]
          fin_cases j <;> simp [Finset.sum_const]
  4. To verify that the padded allocation is partial EFX, it suffices to prove the EFX inequality for any distinct agents i ≠ j separately when the removed good g is an original good and when g is a tail good.

    We split the theorem's conjunction into the partial EFX property and the baseline utilities. For partial EFX, we fix distinct agents i and j, and use Fin.forall_fin_add to decompose the universal quantification over all goods g owned by j into two subcases: goods g among the first 8 items, and goods g among the 2k tail items.

    lines 46–49

    uses Fin.forall_fin_add

      constructor
      · intro i j hij
        rw [Fin.forall_fin_add]
        constructor
  5. The EFX inequality holds between any distinct agents i ≠ j when the removed good g' is one of the original 8 goods.

    We rewrite the valuation of j's bundle and agent i's utility using our earlier formulas. The base allocation satisfies a strict EFX margin of 6 (efx_pareto_lock_strict_margins.1). Multiplying this margin by 2k + 1 gives a slack of 6(2k + 1). Since the tail adds at most k to j's bundle and k ≤ 6(2k + 1), this scaled slack absorbs the extra tail items, and linear arithmetic (`omega`) closes the goal.

    lines 50–67

    uses efx_pareto_lock_strict_margins.1, Fin.addCases_left, Nat.mul_le_mul_left, Nat.mul_add

        · intro g' hg
          rw [hS i j, hutil i]
          simp only [efx_pareto_lock_padded_owner, Fin.addCases_left] at hg
          have hm1 := efx_pareto_lock_strict_margins.1 i j hij g' hg
          rw [hutil_old i] at hm1
          have hv : efx_pareto_lock_padded_values k i (Fin.castAdd (k+k) g') = (k+k+1) * efx_pareto_lock_values i g' := by
            unfold efx_pareto_lock_padded_values efx_partial_scaled_tail
            simp only [Fin.addCases_left]
          rw [hv]
          have hTj : (if j = 0 ∨ j = 1 then k else 0) ≤ k := by
            by_cases hj : j = 0 ∨ j = 1 <;> simp [hj]
          have hmul : (k+k+1) * ((∑ x : Fin 8, if ![1,0,0,0,1,2,4,3] x = j.castSucc then efx_pareto_lock_values i x else 0) + 6)
            ≤ (k+k+1) * (efx_pareto_lock_baseline i + efx_pareto_lock_values i g') := by
            apply Nat.mul_le_mul_left
            linarith
          rw [Nat.mul_add, Nat.mul_add] at hmul
          have hk : k ≤ (k+k+1) * 6 := by omega
          omega
  6. The EFX inequality holds between any distinct agents i ≠ j when the removed good g' is one of the 2k tail goods.

    Tail goods are only allocated to agents 0 and 1, so j ∈ {0, 1}. For j ∈ {0, 1}, the base allocation satisfies a strict margin of 5 (efx_pareto_lock_strict_margins.2). Scaling by 2k + 1 yields a slack of 5(2k + 1). Since the removed tail good has value 1 and the tail items contribute k to j's bundle, the slack easily covers k - 1 because k ≤ 5(2k + 1) + 1. Linear arithmetic (`omega`) completes the step.

    lines 68–91

    uses Fin.addCases_right, Fin.castSucc_inj.mp, efx_pareto_lock_strict_margins.2, if_true, Nat.mul_le_mul_left, Nat.mul_add

        · intro g' hg
          rw [hS i j, hutil i]
          simp only [efx_pareto_lock_padded_owner, Fin.addCases_right] at hg
          have hj : j = 0 ∨ j = 1 := by
            by_cases hlt : (g':ℕ) < k
            · left
              simp [hlt] at hg
              exact Fin.castSucc_inj.mp (hg.symm.trans rfl)
            · right
              simp [hlt] at hg
              exact Fin.castSucc_inj.mp (hg.symm.trans rfl)
          have hm2 := efx_pareto_lock_strict_margins.2 i j hij hj
          rw [hutil_old i] at hm2
          have hv : efx_pareto_lock_padded_values k i (Fin.natAdd 8 g') = 1 := by
            unfold efx_pareto_lock_padded_values efx_partial_scaled_tail
            simp only [Fin.addCases_right]
          rw [hv]
          simp only [hj, if_true]
          have hmul : (k+k+1) * ((∑ x : Fin 8, if ![1,0,0,0,1,2,4,3] x = j.castSucc then efx_pareto_lock_values i x else 0) + 5)
            ≤ (k+k+1) * (efx_pareto_lock_baseline i) := by
            apply Nat.mul_le_mul_left
            linarith
          rw [Nat.mul_add] at hmul
          omega
  7. Every agent i's utility under the padded allocation matches the claimed padded baseline.

    Rewriting with the utility formula established in the first step shows that agent i's utility is definitionally equal (`rfl`) to the definition of efx_pareto_lock_padded_baseline k i.

    lines 92–94

      · intro i
        rw [hutil i]
        rfl
Fin.sum_univ_add
A sum over Fin (a + b) can be split into the sum over the first a elements (via castAdd) and the sum over the remaining b elements (via natAdd).
Fin.addCases_left
Evaluating a function defined by cases on Fin (m + n) via Fin.addCases on an element embedded from Fin m returns the value of the left function.
Fin.addCases_right
Evaluating a function defined by cases on Fin (m + n) via Fin.addCases on an element embedded from Fin n returns the value of the right function.
Finset.mul_sum
Multiplication distributes over a finite sum from the left: a * ∑ x ∈ s, f x = ∑ x ∈ s, a * f x.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands are pointwise equal.
Fin.val_castAdd
The underlying natural number of castAdd m i in Fin (n + m) is equal to that of i in Fin n.
Fin.val_natAdd
The underlying natural number of natAdd n i in Fin (n + m) is equal to n plus the underlying value of i in Fin m.
Fin.isLt
The underlying natural number of any element of Fin n is strictly less than n.
if_true
An if-then-else whose condition is True simplifies to the then-branch.
if_false
An if-then-else whose condition is False simplifies to the else-branch.
Finset.sum_const
Summing a constant value over a finite set equals the cardinality of the set multiplied by that constant.
Fin.forall_fin_add
A universal quantification over Fin (m + n) is equivalent to the conjunction of universal quantifications over the first m elements and the remaining n elements.
efx_pareto_lock_strict_margins.1
In the base 8-item allocation, for distinct agents i ≠ j and any good g owned by j, agent i's valuation of j's bundle plus 6 is at most i's utility plus i's valuation of g.
efx_pareto_lock_strict_margins.2
In the base 8-item allocation, for distinct agents i ≠ j where j is agent 0 or agent 1, agent i's valuation of j's bundle plus 5 is at most i's utility.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers by a factor k on the left preserves the inequality.
Nat.mul_add
Multiplication of natural numbers distributes over addition from the left.
Fin.castSucc_inj.mp
The injection castSucc from Fin n to Fin (n + 1) is injective.

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 efx_pareto_lock_padded_sanity (k : ℕ) :  efx_partial_nat (efx_pareto_lock_padded_values k) (efx_pareto_lock_padded_owner k) ∧  ∀ i : Fin 4, efx_partial_nat_utility (efx_pareto_lock_padded_values k) (efx_pareto_lock_padded_owner k) i =    efx_pareto_lock_padded_baseline k i := by  have hutil : ∀ i : Fin 4, efx_partial_nat_utility (efx_pareto_lock_padded_values k) (efx_pareto_lock_padded_owner k) i      = (k+k+1) * efx_pareto_lock_baseline i + (if i = 0 ∨ i = 1 then k else 0) := by    intro i    unfold efx_partial_nat_utility efx_pareto_lock_padded_values efx_pareto_lock_padded_owner efx_partial_scaled_tail    rw [Fin.sum_univ_add]    simp only [Fin.addCases_left, Fin.addCases_right]    have hbase : (∑ x : Fin 8, if ![1,0,0,0,1,2,4,3] x = i.castSucc then efx_pareto_lock_values i x else 0) = efx_pareto_lock_baseline i := by      fin_cases i <;> decide    have hmul : (∑ x : Fin 8, if ![1,0,0,0,1,2,4,3] x = i.castSucc then (k+k+1) * efx_pareto_lock_values i x else 0) = (k+k+1) * efx_pareto_lock_baseline i := by      rw [← hbase, Finset.mul_sum]      apply Finset.sum_congr rfl      intro x _      by_cases hc : ![1,0,0,0,1,2,4,3] x = i.castSucc <;> simp [hc]    have htail : (∑ x : Fin (k+k), if (if (x:ℕ) < k then (0:Fin 5) else 1) = i.castSucc then (1:ℕ) else 0)        = (if i = 0 ∨ i = 1 then k else 0) := by      rw [Fin.sum_univ_add]      simp only [Fin.val_castAdd, Fin.val_natAdd]      have h2 : ∀ x : Fin k, ¬ (k + (x:ℕ) < k) := by intro x; omega      simp only [Fin.isLt, if_true, h2, if_false]      fin_cases i <;> simp [Finset.sum_const]    rw [hmul, htail]  have hutil_old : ∀ i : Fin 4, efx_pareto_lock_utility ![1,0,0,0,1,2,4,3] i = efx_pareto_lock_baseline i := by    intro i; fin_cases i <;> decide  have hS : ∀ i j : Fin 4,      (∑ h : Fin (8+(k+k)), if efx_pareto_lock_padded_owner k h = j.castSucc then efx_pareto_lock_padded_values k i h else 0)      = (k+k+1) * (∑ x : Fin 8, if ![1,0,0,0,1,2,4,3] x = j.castSucc then efx_pareto_lock_values i x else 0)        + (if j = 0 ∨ j = 1 then k else 0) := by    intro i j    unfold efx_pareto_lock_padded_owner efx_pareto_lock_padded_values efx_partial_scaled_tail    rw [Fin.sum_univ_add]    simp only [Fin.addCases_left, Fin.addCases_right]    congr 1    · rw [Finset.mul_sum]      apply Finset.sum_congr rfl      intro x _      by_cases hc : ![1,0,0,0,1,2,4,3] x = j.castSucc <;> simp [hc]    · rw [Fin.sum_univ_add]      simp only [Fin.val_castAdd, Fin.val_natAdd]      have h2 : ∀ x : Fin k, ¬ (k + (x:ℕ) < k) := by intro x; omega      simp only [Fin.isLt, if_true, h2, if_false]      fin_cases j <;> simp [Finset.sum_const]  constructor  · intro i j hij    rw [Fin.forall_fin_add]    constructor    · intro g' hg      rw [hS i j, hutil i]      simp only [efx_pareto_lock_padded_owner, Fin.addCases_left] at hg      have hm1 := efx_pareto_lock_strict_margins.1 i j hij g' hg      rw [hutil_old i] at hm1      have hv : efx_pareto_lock_padded_values k i (Fin.castAdd (k+k) g') = (k+k+1) * efx_pareto_lock_values i g' := by        unfold efx_pareto_lock_padded_values efx_partial_scaled_tail        simp only [Fin.addCases_left]      rw [hv]      have hTj : (if j = 0 ∨ j = 1 then k else 0) ≤ k := by        by_cases hj : j = 0 ∨ j = 1 <;> simp [hj]      have hmul : (k+k+1) * ((∑ x : Fin 8, if ![1,0,0,0,1,2,4,3] x = j.castSucc then efx_pareto_lock_values i x else 0) + 6)        ≤ (k+k+1) * (efx_pareto_lock_baseline i + efx_pareto_lock_values i g') := by        apply Nat.mul_le_mul_left        linarith      rw [Nat.mul_add, Nat.mul_add] at hmul      have hk : k ≤ (k+k+1) * 6 := by omega      omega    · intro g' hg      rw [hS i j, hutil i]      simp only [efx_pareto_lock_padded_owner, Fin.addCases_right] at hg      have hj : j = 0 ∨ j = 1 := by        by_cases hlt : (g':ℕ) < k        · left          simp [hlt] at hg          exact Fin.castSucc_inj.mp (hg.symm.trans rfl)        · right          simp [hlt] at hg          exact Fin.castSucc_inj.mp (hg.symm.trans rfl)      have hm2 := efx_pareto_lock_strict_margins.2 i j hij hj      rw [hutil_old i] at hm2      have hv : efx_pareto_lock_padded_values k i (Fin.natAdd 8 g') = 1 := by        unfold efx_pareto_lock_padded_values efx_partial_scaled_tail        simp only [Fin.addCases_right]      rw [hv]      simp only [hj, if_true]      have hmul : (k+k+1) * ((∑ x : Fin 8, if ![1,0,0,0,1,2,4,3] x = j.castSucc then efx_pareto_lock_values i x else 0) + 5)        ≤ (k+k+1) * (efx_pareto_lock_baseline i) := by        apply Nat.mul_le_mul_left        linarith      rw [Nat.mul_add] at hmul      omega  · intro i    rw [hutil i]    rfl
See it in the graphDiscuss this resultChallenge it