AFTD Auto-Formalizing Theoretical Domains

efx_pareto_lock_sanity

theoremverified

All values are positive. The partial allocation (1,0,0,0,1,2,4,3), where 4 means unallocated, is EFX and meets the baseline utilities; the unallocated good 6 is worth no more than each baseline. The complete allocation (0,0,0,1,1,2,2,3) is EFX.

Statement

theorem efx_pareto_lock_sanity :
  (∀ i g, 0 < efx_pareto_lock_values i g) ∧
  efx_pareto_lock_feasible ![(1 : Fin 5),0,0,0,1,2,4,3] ∧
  (∀ i : Fin 4, efx_pareto_lock_values i 6 ≤ efx_pareto_lock_baseline i) ∧
  is_efx_goods (fun i g => (efx_pareto_lock_values i g : ℝ))
    ![(0 : Fin 4),0,0,1,1,2,2,3]
Source
Four-agent locked-good lift of the partial EFX Pareto barrier in arXiv:2002.05119, Section 5; experiments 11454–11457.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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.
  • efx_pareto_lock_utilityAgent i’s natural utility when owner 4 denotes unallocated goods.
  • efx_pareto_lock_feasibleA partial allocation is EFX for the natural values and gives each agent at least her original utility; owner 4 means unallocated.
  • 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.

The proof, explained

The theorem verifies four sanity checks for an explicit 4-agent, 8-good fair division instance: all item valuations are strictly positive, a specified partial allocation meets each agent's baseline utility while remaining EFX, the remaining unallocated item (good 6) does not exceed any agent's baseline, and an alternative complete allocation is EFX. The proof splits the goal into these four parts. For the first three, direct finite computation via `decide` suffices; for the fourth, `is_efx_goods_nat_cast_iff` converts the real-valued EFX condition into a decidable integer inequality that `decide` then evaluates exhaustively.

  1. The proof reduces to establishing four independent claims: positivity of all valuations, feasibility of the partial allocation, an upper bound on the unallocated good, and EFX of the complete allocation.

    The constructor splits the four-part conjunction into four separate goals, one for each sanity condition.

    line 7

      refine ⟨?_, ?_, ?_, ?_⟩
  2. All entries in the valuation matrix are strictly positive. automation

    The valuation table `efx_pareto_lock_values` is an explicit 4×8 matrix of natural numbers. Lean checks by finite evaluation that all 32 entries are strictly greater than zero.

    line 8

      · decide
  3. The partial allocation (1,0,0,0,1,2,4,3) is feasible: each agent achieves at least their baseline utility, and the allocation satisfies the EFX property. automation

    Unfolding the definitions of `efx_pareto_lock_feasible` and `efx_pareto_lock_utility` expands the goal into checking baseline inequalities and the EFX condition across all agents and goods for this partial allocation. Because all sets of agents and goods are finite and all values are concrete natural numbers, `decide` verifies this by direct computation.

    lines 9–10

      · unfold efx_pareto_lock_feasible efx_pareto_lock_utility
        decide
  4. For each agent, the valuation of the unallocated good (good 6) does not exceed the agent's baseline utility. automation

    The values of good 6 for the four agents are 11, 31, 21, and 1, while the baseline utilities are 163, 152, 101, and 8, respectively. The decision procedure verifies these four inequalities by direct computation.

    line 11

      · decide
  5. The complete allocation (0,0,0,1,1,2,2,3) is envy-free up to any good (EFX). automation

    Rewriting with `is_efx_goods_nat_cast_iff` translates the real-valued EFX property into an equivalent statement over natural numbers comparing bundle sums. Lean then verifies all bundle valuations and the EFX inequalities exhaustively via `decide`.

    lines 12–13

    uses is_efx_goods_nat_cast_iff

      · rw [is_efx_goods_nat_cast_iff]
        decide
is_efx_goods_nat_cast_iff
An allocation of goods is EFX (envy-free up to any good) with respect to natural-number valuations embedded in ℝ if and only if for every pair of distinct agents i and j, and every good g assigned to j, the total value agent i assigns to j's bundle is at most i's value for their own bundle plus i's value for g.

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_sanity :  (∀ i g, 0 < efx_pareto_lock_values i g) ∧  efx_pareto_lock_feasible ![(1 : Fin 5),0,0,0,1,2,4,3] ∧  (∀ i : Fin 4, efx_pareto_lock_values i 6 ≤ efx_pareto_lock_baseline i) ∧  is_efx_goods (fun i g => (efx_pareto_lock_values i g : ℝ))    ![(0 : Fin 4),0,0,1,1,2,2,3] := by  refine ⟨?_, ?_, ?_, ?_⟩  · decide  · unfold efx_pareto_lock_feasible efx_pareto_lock_utility    decide  · decide  · rw [is_efx_goods_nat_cast_iff]    decide
See it in the graphDiscuss this resultChallenge it