AFTD Auto-Formalizing Theoretical Domains

efx_anchor_lock_start_sanity

theoremverified

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

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.

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

    lines 9–10

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