efx_min_cycle_all_standard_moves_fail
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
- efx_min_cycle_outcomeThe six outcomes obtained from the two inclusion-minimal two-cycles: for each chosen pair of upper halves, mode 0 swaps them, mode 1…
- efx_min_cycle_valuesThe four rows of the positive natural valuation matrix are (3,3,12,2,15,1,1,1,16,16,1,1,3), (3,14,1,3,3,12,16,1,1,1,1,16,3),…
- efx_min_cycle_valueNatural additive value of a set in the explicit matrix.
- efx_no_self_three_split_oldThe old partial allocation consists of four consecutive triples; good 12 is unallocated.
- efx_min_cycle_baselineThe initial utilities of the four agents.
- efx_min_cycle_partial_efxNatural EFX inequalities for a possibly partial four-bundle allocation.
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.
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.
unfold efx_min_cycle_partial_efx decide
- Unfolding `efx_min_cycle_partial_efx` on line 7 is a Lean-specific technicality: Lean lacks a precomputed `Decidable` instance for the named definition, so unfolding it into explicit bounded quantifiers over finite types is required before `decide` can evaluate the proposition.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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