efx_pareto_lock_padded_sanity
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
- 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.
- efx_partial_scaled_tailScale each natural base value by K and append arbitrary natural-valued tail goods.
- efx_pareto_lock_padded_valuesScale the locked-good example by 2k+1 and append 2k goods worth 1 to each agent.
- efx_pareto_lock_padded_ownerUse the original partial allocation, assigning the first k added goods to source 0 and the other k to source 1.
- efx_pareto_lock_padded_baselineScaled original utilities plus k for each of sources 0 and 1.
- efx_pareto_lock_strict_marginsIn the locked example every EFX inequality has natural slack at least 6, and every other agent values either source bundle at least 5…
- efx_pareto_lock_valuesThe explicit positive natural valuation rows (81,21,121,21,1,171,11,428), (51,1,91,41,101,1,31,318), (1,1,1,1,91,101,21,218), and…
- efx_pareto_lock_baselineThe original partial-allocation utilities.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - efx_pareto_lock_utilityAgent i’s natural utility when owner 4 denotes unallocated goods.
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.
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.
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_consthave 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]
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`).
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
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.
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_consthave 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]
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.
uses
Fin.forall_fin_addconstructor · intro i j hij rw [Fin.forall_fin_add] constructor
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.
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
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.
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
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.
· 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.
- The base 8-item allocation and its baseline utilities and strict margins (margins of 6 and 5) are verified computationally by exhaustively checking cases with `decide`.
- The padding construction works because the base valuations are scaled by 2k + 1, scaling the strict margins up to at least 5(2k + 1), which comfortably absorbs the at most k extra utility from the tail goods.
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 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