AFTD Auto-Formalizing Theoretical Domains

efx_nondeg_cycle_sanity

theoremverified

All values are positive, the old allocation with good 12 unallocated is EFX with the stated baselines, and the only envy edges are 0→3 and 2→3; thus agents 0,1,2 are sources.

Statement

theorem efx_nondeg_cycle_sanity :
  (∀ i g, 0 < efx_nondeg_cycle_values i g) ∧
  (∀ i, efx_nondeg_cycle_value i (efx_no_self_three_split_old i) = efx_nondeg_cycle_baseline i) ∧
  efx_partial_nat efx_nondeg_cycle_values ![(0 : Fin 5),0,0,1,1,1,2,2,2,3,3,3,4] ∧
  (∀ i j : Fin 4, i ≠ j →
    (efx_nondeg_cycle_value i (efx_no_self_three_split_old i) < efx_nondeg_cycle_value i (efx_no_self_three_split_old j) ↔
      (i = 0 ∧ j = 3) ∨ (i = 2 ∧ j = 3)))
Source
Nondegenerate three-source champion two-cycle exchange obstruction for OP-7, experiments 11481–11487; related arXiv:2002.05119 Section 3.1.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6

The proof, explained

The theorem verifies four sanity conditions for a 4-agent, 13-good fair division instance: all item valuations are strictly positive, each agent's initial 3-item bundle matches a specified baseline value, leaving good 12 unallocated produces an EFX partial allocation, and the only envy edges in the old allocation are 0 → 3 and 2 → 3. Because all agents and goods belong to finite index types and all valuations are concrete natural numbers, the assertion is a decidable proposition. Unfolding the definition of partial EFX exposes the bounded quantifiers so that Lean's decision procedure (`decide`) completes the proof by exhaustive computation.

  1. The valuation profile has strictly positive entries, bundle values match their designated baselines, the partial allocation is EFX, and the only envy pairs are 0 envying 3 and 2 envying 3. automation

    Unfolding the definitions of `efx_partial_nat` and `efx_partial_nat_utility` expands the partial EFX condition into explicit finite sums and inequalities over agents and goods. Because the agents and goods belong to finite sets (4 agents and 13 goods) and all valuations are concrete natural numbers, the entire proposition consists of decidable arithmetic checks. Lean's `decide` tactic verifies all inequalities, equalities, and logical equivalences by exhaustive finite evaluation.

    lines 8–9

      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_nondeg_cycle_sanity :  (∀ i g, 0 < efx_nondeg_cycle_values i g) ∧  (∀ i, efx_nondeg_cycle_value i (efx_no_self_three_split_old i) = efx_nondeg_cycle_baseline i) ∧  efx_partial_nat efx_nondeg_cycle_values ![(0 : Fin 5),0,0,1,1,1,2,2,2,3,3,3,4] ∧  (∀ i j : Fin 4, i ≠ j →    (efx_nondeg_cycle_value i (efx_no_self_three_split_old i) < efx_nondeg_cycle_value i (efx_no_self_three_split_old j) ↔      (i = 0 ∧ j = 3) ∨ (i = 2 ∧ j = 3))) := by  unfold efx_partial_nat efx_partial_nat_utility  decide
See it in the graphDiscuss this resultChallenge it