efx_anchor_lock_start_sanity
All values are positive, the starting allocation is EFX with the specified utilities, and every tested EFX inequality is strict.
Statement
theorem efx_anchor_lock_start_sanity : (∀ i g, 0 < efx_anchor_lock_perturbed_values i g) ∧ efx_partial_nat efx_anchor_lock_perturbed_values efx_anchor_lock_start ∧ (∀ i : Fin 4, efx_partial_nat_utility efx_anchor_lock_perturbed_values efx_anchor_lock_start i = efx_anchor_lock_perturbed_baseline i) ∧ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 12, efx_anchor_lock_start g = j.castSucc → (∑ h : Fin 12, if efx_anchor_lock_start h = j.castSucc then efx_anchor_lock_perturbed_values i h else 0) < efx_partial_nat_utility efx_anchor_lock_perturbed_values efx_anchor_lock_start i + efx_anchor_lock_perturbed_values i g)
- 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 7
- efx_anchor_lock_valuesThe explicit positive twelve-good anchor-and-lock matrix: three anchors at goods 7,8,9 and two locked goods 10,11, with the first seven…
- efx_anchor_lock_exponentsThe four binary exponent rows, each a permutation of 0 through 11.
- efx_anchor_lock_perturbed_valuesThe nondegenerate integer perturbation of the anchor-and-lock instance.
- efx_anchor_lock_startThe partial starting allocation, with owner 4 denoting the unallocated good 6; its four bundle sizes are 4,3,2,2.
- efx_anchor_lock_perturbed_baselineThe four starting utilities after the binary perturbation.
- efx_partial_natNatural EFX inequalities for a partial allocation whose last owner label denotes unallocated goods.
- efx_partial_nat_utilityNatural utility in a partial allocation whose last owner label denotes unallocated goods.
The proof, explained
The theorem is proved by finite computational verification. Because the sets of agents (Fin 4) and goods (Fin 12) are finite and all valuations, baseline utilities, and allocation assignments are explicitly defined integers, the four conjuncts form a closed decidable proposition. Expanding the definitions of partial EFX and agent utility allows the `decide` tactic to verify all bounds, baseline utilities, and strict inequalities by direct evaluation.
The explicit finite conditions for positivity, partial EFX, baseline utilities, and strict inequality margins are verified by direct arithmetic evaluation. automation
Unfolding `efx_partial_nat` and `efx_partial_nat_utility` expands the partial EFX property and bundle utilities into explicit bounded quantifiers, sums, and conditionals over the finite sets Fin 4 and Fin 12. Because the valuation matrix, starting allocation, and baseline utilities are concrete computable constants, the goal becomes a closed decidable proposition that `decide` proves by exhaustive finite computation.
unfold efx_partial_nat efx_partial_nat_utility decide
- The tactic `unfold efx_partial_nat efx_partial_nat_utility` is a formal detail needed for Lean's typeclass synthesis to recognise the goal as a decidable proposition; on paper, expanding definitions is implicit.
- The entire mathematical verification is performed by the `decide` tactic via exhaustive computation in the Lean kernel over all agents and goods, without displaying intermediate arithmetic steps.
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_start_sanity : (∀ i g, 0 < efx_anchor_lock_perturbed_values i g) ∧ efx_partial_nat efx_anchor_lock_perturbed_values efx_anchor_lock_start ∧ (∀ i : Fin 4, efx_partial_nat_utility efx_anchor_lock_perturbed_values efx_anchor_lock_start i = efx_anchor_lock_perturbed_baseline i) ∧ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 12, efx_anchor_lock_start g = j.castSucc → (∑ h : Fin 12, if efx_anchor_lock_start h = j.castSucc then efx_anchor_lock_perturbed_values i h else 0) < efx_partial_nat_utility efx_anchor_lock_perturbed_values efx_anchor_lock_start i + efx_anchor_lock_perturbed_values i g) := by unfold efx_partial_nat efx_partial_nat_utility decide