AFTD Auto-Formalizing Theoretical Domains

efx_nondeg_cycle_standard_moves_fail

theoremverified

All six standard two-cycle swaps and one-good repairs in the nondegenerate instance are Pareto improvements but fail EFX.

Statement

theorem efx_nondeg_cycle_standard_moves_fail :
  ∀ (c : Fin 2) (mode : Fin 3),
    ¬ (∀ i j : Fin 4, i ≠ j → ∀ g ∈ efx_min_cycle_outcome c mode j,
      efx_nondeg_cycle_value i ((efx_min_cycle_outcome c mode j).erase g) ≤
        efx_nondeg_cycle_value i (efx_min_cycle_outcome c mode i)) ∧
    (∀ i, efx_nondeg_cycle_baseline i ≤ efx_nondeg_cycle_value i (efx_min_cycle_outcome c mode i)) ∧
    efx_nondeg_cycle_baseline 0 < efx_nondeg_cycle_value 0 (efx_min_cycle_outcome c mode 0) ∧
    efx_nondeg_cycle_baseline 1 < efx_nondeg_cycle_value 1 (efx_min_cycle_outcome c mode 1)
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 4

The proof, explained

The theorem asserts that six candidate allocations—representing standard two-cycle swaps and one-good repairs in a 4-agent fair division problem—fail to be envy-free up to any good (EFX), yet each Pareto dominates the baseline allocation by strictly improving agents 0 and 1 and weakly improving all agents. Since all valuations, bundles, and baseline values are concrete finite data, the statement is a bounded quantifier sentence over finite sets and natural numbers. Lean settles the claim completely by computational reflection using the `decide` tactic.

  1. For all six combinations of cycle c ∈ Fin 2 and mode ∈ Fin 3, the allocation fails EFX but is a Pareto improvement over the baseline (weakly improving all agents and strictly improving agents 0 and 1). automation

    All quantifiers in the theorem range over finite types (c : Fin 2, mode : Fin 3, i, j : Fin 4, and elements g of a finite set of goods), and the valuations and baselines are given by explicit tables of natural numbers. Consequently, the quantified formula is purely computational and decidable. The `decide` tactic evaluates the truth value of the proposition by exhaustive computation in the Lean kernel, verifying that EFX fails and that the Pareto dominance inequalities hold for each of the six outcomes.

    line 9

      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_standard_moves_fail :  ∀ (c : Fin 2) (mode : Fin 3),    ¬ (∀ i j : Fin 4, i ≠ j → ∀ g ∈ efx_min_cycle_outcome c mode j,      efx_nondeg_cycle_value i ((efx_min_cycle_outcome c mode j).erase g) ≤        efx_nondeg_cycle_value i (efx_min_cycle_outcome c mode i)) ∧    (∀ i, efx_nondeg_cycle_baseline i ≤ efx_nondeg_cycle_value i (efx_min_cycle_outcome c mode i)) ∧    efx_nondeg_cycle_baseline 0 < efx_nondeg_cycle_value 0 (efx_min_cycle_outcome c mode 0) ∧    efx_nondeg_cycle_baseline 1 < efx_nondeg_cycle_value 1 (efx_min_cycle_outcome c mode 1) := by  decide
See it in the graphDiscuss this resultChallenge it