AFTD Auto-Formalizing Theoretical Domains

efx_pair_binary_requires_two_splits

theoremverified

Every complete EFX allocation of the explicit binary nine-good matrix cast to real values separates the two members of at least two distinct old adjacent pairs among goods 0 through 7.

Statement

theorem efx_pair_binary_requires_two_splits (σ : Fin 9 → Fin 4)
    (hσ : is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ)) σ) :
    ∃ a b : Fin 4, a ≠ b ∧
      σ (![0,2,4,6] a) ≠ σ (![1,3,5,7] a) ∧
      σ (![0,2,4,6] b) ≠ σ (![1,3,5,7] b)
Source
Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. Exact route obstruction from experiment 10993, not a counterexample to EFX existence; no novelty claim.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • efx_pair_binary_valuesA positive four-agent nine-good valuation matrix: the first two rows are (2,1,2,1,2,1,2,1,2), and the last two rows are (1,2,1,2,1,2,1,2,2).
  • efx_pair_binary_no_one_split_allocationFor the explicit binary nine-good matrix cast to real values, any allocation which preserves all but possibly one of the four old adjacent…
  • is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…

The proof, explained

The theorem is proved by leveraging an auxiliary impossibility result: an allocation for this valuation matrix cannot be EFX if at most one adjacent pair is split. From this, the proof derives that avoiding any single pair index still leaves at least one split pair. Instantiating this fact once yields a first split pair a, and instantiating it again to avoid a yields a second, distinct split pair b.

  1. For any pair index r ∈ {0, 1, 2, 3}, there exists a different pair index j ≠ r whose two goods are allocated to different agents.

    We proceed by contradiction. If no such j existed, then every pair j ≠ r would have its two goods assigned to the same agent. However, `efx_pair_binary_no_one_split_allocation` proves that no allocation that splits at most one pair can be EFX for this binary valuation matrix, contradicting the assumption hσ that σ is an EFX allocation.

    lines 8–12

    uses efx_pair_binary_no_one_split_allocation

      classical
      have h (r : Fin 4) : ∃ j : Fin 4, j ≠ r ∧ σ (![0,2,4,6] j) ≠ σ (![1,3,5,7] j) := by
        by_contra h
        push Not at h
        exact efx_pair_binary_no_one_split_allocation σ r h hσ
  2. There exist two distinct pair indices a and b such that both pairs are split by σ.

    Applying the intermediate claim to r = 0 yields an index a whose pair is split. Applying it again with r = a yields a second split pair b with b ≠ a. By symmetry of inequality, a ≠ b, so a and b furnish the two distinct split pairs required by the theorem.

    lines 13–15

      obtain ⟨a, _, ha⟩ := h 0
      obtain ⟨b, hb, hbs⟩ := h a
      exact ⟨a, b, hb.symm, ha, hbs⟩
efx_pair_binary_no_one_split_allocation
No allocation of the 9 goods to 4 agents under the binary valuation matrix can be EFX if all adjacent pairs among goods 0 through 7, except possibly a single designated pair r, are kept together (assigned to the same agent).

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

open Function Finsettheorem efx_pair_binary_requires_two_splits (σ : Fin 9 → Fin 4)    (hσ : is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ)) σ) :    ∃ a b : Fin 4, a ≠ b ∧      σ (![0,2,4,6] a) ≠ σ (![1,3,5,7] a) ∧      σ (![0,2,4,6] b) ≠ σ (![1,3,5,7] b) := by  classical  have h (r : Fin 4) : ∃ j : Fin 4, j ≠ r ∧ σ (![0,2,4,6] j) ≠ σ (![1,3,5,7] j) := by    by_contra h    push Not at h    exact efx_pair_binary_no_one_split_allocation σ r h hσ  obtain ⟨a, _, ha⟩ := h 0  obtain ⟨b, hb, hbs⟩ := h a  exact ⟨a, b, hb.symm, ha, hbs⟩
See it in the graphDiscuss this resultChallenge it