efx_pareto_lock_sanity
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.
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.
refine ⟨?_, ?_, ?_, ?_⟩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.
· decideThe 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.
· unfold efx_pareto_lock_feasible efx_pareto_lock_utility decide
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.
· decideThe 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`.
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.
- The proof relies heavily on the `decide` tactic, which verifies the conditions by exhaustive evaluation of finite sums and comparisons on the explicit 4-agent, 8-good valuation matrix.
- The partial allocation represents unallocated goods by assigning them to index 4 in `Fin 5`.
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_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