efx_nondeg_cycle_standard_moves_fail
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
- efx_nondeg_cycle_valuesThe nondegenerate perturbation of the minimum-cardinality champion-cycle matrix.
- efx_nondeg_cycle_valueThe natural additive value of a set in the nondegenerate cycle instance.
- efx_nondeg_cycle_baselineThe four old-bundle utilities in the nondegenerate cycle instance.
- 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…
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.
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.
decide
- The proof is carried out entirely by computational evaluation via `decide`; there are no intermediate lemma applications or paper-style deductive steps.
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_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