AFTD Auto-Formalizing Theoretical Domains

efx_min_cycle_all_standard_moves_fail

theoremverified

For each of the two two-cycle choices, the upper-half swap and either single-good lower-half repair all fail EFX despite preserving every old utility and strictly improving both cycle agents.

Statement

theorem efx_min_cycle_all_standard_moves_fail :
  ∀ (c : Fin 2) (mode : Fin 3),
    ¬ efx_min_cycle_partial_efx (efx_min_cycle_outcome c mode) ∧
    (∀ i, efx_min_cycle_baseline i ≤ efx_min_cycle_value i (efx_min_cycle_outcome c mode i)) ∧
    efx_min_cycle_baseline 0 < efx_min_cycle_value 0 (efx_min_cycle_outcome c mode 0) ∧
    efx_min_cycle_baseline 1 < efx_min_cycle_value 1 (efx_min_cycle_outcome c mode 1)
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 6

The proof, explained

The theorem asserts that across both choices of two-cycles and all three standard repair modes (the upper-half swap and the two single-good lower-half repairs), the resulting allocation fails the EFX fairness criterion while weakly preserving every agent's baseline utility and strictly improving both cycle agents' utilities. Because there are only $2 \\times 3 = 6$ possible allocations over 4 agents and 13 goods with concrete additive valuations, all four properties reduce to finite arithmetic checks. Unfolding the definition of EFX exposes these bounded conditions, allowing Lean's `decide` tactic to establish the theorem by exhaustive finite computation.

  1. For all six combinations of cycle choice and repair mode, the outcome violates EFX, preserves baseline utility for all agents, and strictly improves utility for agents 0 and 1. automation

    The claim is purely finitary: there are two cycle choices ($c \\in \\{0, 1\\}$), three repair modes (mode $\\in \\{0, 1, 2\\}$), four agents, and bundles formed from 13 goods with concrete additive integer values. Unfolding the definition of EFX (`efx_min_cycle_partial_efx`) expresses envy-freeness up to any good as bounded universal quantifications over finite sets. Lean's decision procedure (`decide`) then evaluates all six candidate allocations by exhaustive computation, verifying that each outcome fails EFX, satisfies $v_i(A_i) \\ge \\text{baseline}(i)$ for all four agents, and strictly improves the utilities of agents 0 and 1 over their baselines.

    lines 7–8

      unfold efx_min_cycle_partial_efx
      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_all_standard_moves_fail :  ∀ (c : Fin 2) (mode : Fin 3),    ¬ efx_min_cycle_partial_efx (efx_min_cycle_outcome c mode) ∧    (∀ i, efx_min_cycle_baseline i ≤ efx_min_cycle_value i (efx_min_cycle_outcome c mode i)) ∧    efx_min_cycle_baseline 0 < efx_min_cycle_value 0 (efx_min_cycle_outcome c mode 0) ∧    efx_min_cycle_baseline 1 < efx_min_cycle_value 1 (efx_min_cycle_outcome c mode 1) := by  unfold efx_min_cycle_partial_efx  decide
See it in the graphDiscuss this resultChallenge it