AFTD Auto-Formalizing Theoretical Domains

efx_pareto_lock_strict_margins

theoremverified

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

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.

  1. 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]$.

    line 9

      unfold efx_pareto_lock_utility
  2. The 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.

    line 10

      decide

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_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
See it in the graphDiscuss this resultChallenge it