AFTD Auto-Formalizing Theoretical Domains

efx_min_cycle_sanity

theoremverified

Every value is positive; each agent values all old bundles equally, values each good of her own old bundle at least as much as good 12, and each old bundle has a good that some foreign agent values less than good 12. The old partial allocation is EFX.

Statement

theorem efx_min_cycle_sanity :
  (∀ i g, 0 < efx_min_cycle_values i g) ∧
  (∀ i j, efx_min_cycle_value i (efx_no_self_three_split_old j) = efx_min_cycle_baseline i) ∧
  (∀ i g, g ∈ efx_no_self_three_split_old i → efx_min_cycle_values i 12 ≤ efx_min_cycle_values i g) ∧
  (∀ j, ∃ i : Fin 4, i ≠ j ∧ ∃ g ∈ efx_no_self_three_split_old j, efx_min_cycle_values i g < efx_min_cycle_values i 12) ∧
  efx_min_cycle_partial_efx efx_no_self_three_split_old
Source
Minimum-cardinality champion-cycle swap obstruction for OP-7, experiments 11442–11449; comparison with arXiv:2002.05119 Section 3.1.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

The proof, explained

The theorem verifies five sanity properties for an explicit fair-division instance with four agents and thirteen goods, where four bundles of three goods are allocated and good 12 remains unallocated. The properties state that all valuations are positive, every agent values all four bundles equally at her baseline value, each agent values every good in her own bundle at least as much as good 12, each bundle contains a good that an outside agent values strictly less than good 12, and the allocation is EFX. Because the agent and item sets are finite, the proof splits the conjunction into five subgoals and resolves each by exhaustive case analysis and direct arithmetic evaluation.

  1. The proof reduces to verifying the five conjuncts independently.

    The goal is a conjunction of five statements. Splitting the conjunction yields five separate subgoals corresponding to the five sanity conditions.

    line 7

      refine ⟨?_, ?_, ?_, ?_, ?_⟩
  2. Every agent assigns a strictly positive value to every good. automation

    Introducing an arbitrary agent i and good g, exhaustive case analysis on i ∈ {0, 1, 2, 3} and g ∈ {0, ..., 12} produces 52 cases. In each case, Lean evaluates 0 < v_i(g) from the concrete valuation matrix by direct arithmetic computation.

    lines 8–9

      · intro i g
        fin_cases i <;> fin_cases g <;> decide
  3. Each agent values all four initial bundles equally, matching that agent's baseline value. automation

    Introducing an agent i and bundle index j, case exhaustion generates all 16 pairs (i, j). For each pair, the sum of values of the goods in bundle A(j) is computed and confirmed to equal the baseline value b_i (18 for agents 0, 1, and 3, and 36 for agent 2).

    lines 10–11

      · intro i j
        fin_cases i <;> fin_cases j <;> decide
  4. Every agent values each good in her own bundle at least as much as good 12. automation

    Assuming g ∈ A(i), case exhaustion enumerates all 52 pairs (i, g). Whenever g ∉ A(i), the membership hypothesis reduces to False and closes the branch. Whenever g ∈ A(i), simplifying the valuation matrix definitions confirms the inequality v_i(12) ≤ v_i(g).

    lines 12–14

      · intro i g hg
        fin_cases i <;> fin_cases g <;>
          simp_all [efx_no_self_three_split_old, efx_min_cycle_values]
  5. For every bundle, some other agent values an item in that bundle strictly less than good 12. automation

    For each bundle j ∈ {0, 1, 2, 3}, the existential condition asks for an outside agent i ≠ j and an item g ∈ A(j) such that v_i(g) < v_i(12). Because the domains are finite, the decision procedure exhaustively searches for and verifies such a witness pair.

    lines 15–16

      · intro j
        fin_cases j <;> decide
  6. The initial allocation is envy-free up to any good (EFX). automation

    By definition, the allocation is EFX if for all distinct agents i ≠ j and every good g ∈ A(j), v_i(A(j) \ {g}) ≤ v_i(A(i)). Case analysis enumerates all tuples (i, j, g); invalid tuples with i = j or g ∉ A(j) are dismissed by the hypotheses, and for all valid tuples the bundle sums are evaluated and shown to satisfy the inequality.

    lines 17–20

      · intro i j hij g hg
        fin_cases i <;> fin_cases j <;> fin_cases g <;>
          simp_all [efx_min_cycle_value, efx_no_self_three_split_old, efx_min_cycle_values] <;>
          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_min_cycle_sanity :  (∀ i g, 0 < efx_min_cycle_values i g) ∧  (∀ i j, efx_min_cycle_value i (efx_no_self_three_split_old j) = efx_min_cycle_baseline i) ∧  (∀ i g, g ∈ efx_no_self_three_split_old i → efx_min_cycle_values i 12 ≤ efx_min_cycle_values i g) ∧  (∀ j, ∃ i : Fin 4, i ≠ j ∧ ∃ g ∈ efx_no_self_three_split_old j, efx_min_cycle_values i g < efx_min_cycle_values i 12) ∧  efx_min_cycle_partial_efx efx_no_self_three_split_old := by  refine ⟨?_, ?_, ?_, ?_, ?_⟩  · intro i g    fin_cases i <;> fin_cases g <;> decide  · intro i j    fin_cases i <;> fin_cases j <;> decide  · intro i g hg    fin_cases i <;> fin_cases g <;>      simp_all [efx_no_self_three_split_old, efx_min_cycle_values]  · intro j    fin_cases j <;> decide  · intro i j hij g hg    fin_cases i <;> fin_cases j <;> fin_cases g <;>      simp_all [efx_min_cycle_value, efx_no_self_three_split_old, efx_min_cycle_values] <;>      decide
See it in the graphDiscuss this resultChallenge it