efx_anchor_lock_full_efx
The nondegenerate instance has a complete EFX allocation with owners (3,1,1,1,2,2,1,2,1,0,3,0).
Statement
theorem efx_anchor_lock_full_efx : is_efx_goods (fun i g => (efx_anchor_lock_perturbed_values i g : ℝ)) ![(3 : Fin 4),1,1,1,2,2,1,2,1,0,3,0]
- Source
- Nondegenerate no-singleton four-agent Pareto-maximal partial EFX obstruction, experiments 11500–11507; locked-good lift of arXiv:2002.05119 Section 5.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- efx_anchor_lock_perturbed_valuesThe nondegenerate integer perturbation of the anchor-and-lock instance.
- 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 asserts that the specified assignment of 12 goods among 4 agents satisfies envy-freeness up to any good (EFX) under the perturbed valuation functions. The proof rewrites the real-valued EFX definition into an equivalent arithmetic condition on the underlying natural-number valuations. Since the instance is finite (4 agents and 12 goods) and all values are fully concrete, the claim is verified by exhaustive computation via `decide`.
The EFX property under the real-valued perturbed valuations is equivalent to checking that for every distinct pair of agents i and j, and every good g assigned to j, the total value of j's bundle to i is at most the total value of i's bundle to i plus the value of g to i, computed entirely in ℕ.
Rewriting with `is_efx_goods_nat_cast_iff` converts the definition of envy-freeness up to any good (EFX) from real-valued additive valuations to an equivalent condition phrased in terms of natural-number addition and sums over finite bundles.
uses
is_efx_goods_nat_cast_iffrw [is_efx_goods_nat_cast_iff]The EFX inequality holds for every pair of agents and every relevant good, establishing that the allocation is EFX. automation
Because there are only 4 agents and 12 goods, and all bundle assignments and perturbed valuations are explicitly given, the remaining goal is a bounded universal quantification over finite sets. The `decide` tactic verifies all cases by finite computation.
decide
is_efx_goods_nat_cast_iff- For natural-number valuations cast to the real numbers, an allocation is EFX if and only if for all distinct agents i and j and every good g in j's bundle, the sum of i's valuations of j's bundle is at most i's valuation of their own bundle plus i's valuation of 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
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_anchor_lock_full_efx : is_efx_goods (fun i g => (efx_anchor_lock_perturbed_values i g : ℝ)) ![(3 : Fin 4),1,1,1,2,2,1,2,1,0,3,0] := by rw [is_efx_goods_nat_cast_iff] decide