efx_pareto_lock_strict_margins
In the locked example every EFX inequality has natural slack at least 6, and every other agent values either source bundle at least 5 below her own utility.
Statement
theorem efx_pareto_lock_strict_margins : (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 8, ![(1 : Fin 5),0,0,0,1,2,4,3] g = j.castSucc → (∑ h : Fin 8, if ![(1 : Fin 5),0,0,0,1,2,4,3] h = j.castSucc then efx_pareto_lock_values i h else 0) + 6 ≤ efx_pareto_lock_utility ![(1 : Fin 5),0,0,0,1,2,4,3] i + efx_pareto_lock_values i g) ∧ (∀ i j : Fin 4, i ≠ j → (j = 0 ∨ j = 1) → (∑ h : Fin 8, if ![(1 : Fin 5),0,0,0,1,2,4,3] h = j.castSucc then efx_pareto_lock_values i h else 0) + 5 ≤ efx_pareto_lock_utility ![(1 : Fin 5),0,0,0,1,2,4,3] 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 2
- 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_utilityAgent i’s natural utility when owner 4 denotes unallocated goods.
- Used by 1
- efx_pareto_lock_padded_sanityFor every k the padded starting allocation is partial EFX and has the claimed baseline utilities.
The proof, explained
The theorem establishes strict margins on EFX inequalities and source bundle valuations in a specific 4-agent, 8-item fair division instance under a concrete allocation. The proof unfolds the definition of utility into an explicit sum and then completes the verification via `decide`, which exhaustively evaluates the finite set of arithmetic conditions.
The agent utility function is expressed as an explicit sum over the goods allocated to that agent.
Unfolding the definition `efx_pareto_lock_utility` replaces the utility term with the sum of the valuations of the goods assigned to agent $i$ under the fixed allocation vector $\sigma = [1, 0, 0, 0, 1, 2, 4, 3]$.
unfold efx_pareto_lock_utilityThe strict margin inequalities hold for all agents and all allocated goods. automation
The proposition consists of universal quantifiers over the finite types $\mathrm{Fin}\ 4$ and $\mathrm{Fin}\ 8$ applied to concrete arithmetic inequalities over natural numbers. The `decide` tactic evaluates all possible combinations of agents $i \neq j$ and goods $g$ by direct computation in Lean's kernel, verifying that the slack is at least 6 for every EFX condition and at least 5 for the source bundles.
decide
- The proof relies on Lean's kernel computation (`decide`) to exhaustively verify all finite cases and arithmetic inequalities.
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_strict_margins : (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 8, ![(1 : Fin 5),0,0,0,1,2,4,3] g = j.castSucc → (∑ h : Fin 8, if ![(1 : Fin 5),0,0,0,1,2,4,3] h = j.castSucc then efx_pareto_lock_values i h else 0) + 6 ≤ efx_pareto_lock_utility ![(1 : Fin 5),0,0,0,1,2,4,3] i + efx_pareto_lock_values i g) ∧ (∀ i j : Fin 4, i ≠ j → (j = 0 ∨ j = 1) → (∑ h : Fin 8, if ![(1 : Fin 5),0,0,0,1,2,4,3] h = j.castSucc then efx_pareto_lock_values i h else 0) + 5 ≤ efx_pareto_lock_utility ![(1 : Fin 5),0,0,0,1,2,4,3] i) := by unfold efx_pareto_lock_utility decide