AFTD Auto-Formalizing Theoretical Domains

efx_pair_binary_no_one_split_allocation

theoremverified

For the explicit binary nine-good matrix cast to real values, any allocation which preserves all but possibly one of the four old adjacent pairs fails EFX.

Statement

theorem efx_pair_binary_no_one_split_allocation (σ : Fin 9 → Fin 4) (r : Fin 4)
    (hstay : ∀ j : Fin 4, j ≠ r → σ (![0,2,4,6] j) = σ (![1,3,5,7] j)) :
    ¬ is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ)) σ
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 4
  • 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_one_splitAssign the four old adjacent pairs among goods 0 through 7 and the new good 8 to arbitrary agents, except the pair indexed r may have its…
  • efx_pair_binary_no_one_splitFor the explicit binary nine-good matrix cast to real values, no allocation encoded by the one-split construction is EFX.
  • 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…
Used by 1

The proof, explained

The theorem shows that any allocation of 9 goods among 4 agents that leaves at least three of the four designated pairs (0,1), (2,3), (4,5), and (6,7) unseparated cannot be envy-free up to any good (EFX) under the valuation matrix efx_pair_binary_values. The proof splits into four cases depending on which pair r ∈ {0, 1, 2, 3} may be separated. In each case, preserving the remaining three pairs allows σ to be rewritten in the canonical template efx_pair_binary_one_split r, at which point the lemma efx_pair_binary_no_one_split immediately rules out the EFX property.

  1. It suffices to prove the result for each possible value of r ∈ {0, 1, 2, 3}.

    The index r designates the single pair among the four pairs of goods that is allowed to be split across different agents. A case analysis on r in the finite type Fin 4 divides the problem into four subcases: r = 0, 1, 2, and 3.

    line 6

      fin_cases r
  2. When r = 0, the allocation σ is not EFX.

    When r = 0, the hypothesis hstay applied to j = 1, 2, 3 ensures that the other three pairs remain unsplit: σ(2) = σ(3), σ(4) = σ(5), and σ(6) = σ(7). By evaluating on each of the nine goods, σ matches the parameterized template efx_pair_binary_one_split 0 (σ 0) (σ 1) (σ 2) (σ 4) (σ 6) (σ 8). Applying efx_pair_binary_no_one_split shows that this allocation cannot be EFX.

    lines 7–14

    uses efx_pair_binary_no_one_split

      · have h1 : σ 2 = σ 3 := hstay 1 (by decide)
        have h2 : σ 4 = σ 5 := hstay 2 (by decide)
        have h3 : σ 6 = σ 7 := hstay 3 (by decide)
        have heq : σ = efx_pair_binary_one_split 0 (σ 0) (σ 1) (σ 2) (σ 4) (σ 6) (σ 8) := by
          funext g
          fin_cases g <;> simp [efx_pair_binary_one_split, h1, h2, h3]
        rw [heq]
        exact efx_pair_binary_no_one_split 0 (σ 0) (σ 1) (σ 2) (σ 4) (σ 6) (σ 8)
  3. When r = 1, the allocation σ is not EFX.

    When r = 1, pairs 0, 2, and 3 remain intact: σ(0) = σ(1), σ(4) = σ(5), and σ(6) = σ(7). Checking each of the nine goods shows that σ coincides with efx_pair_binary_one_split 1 (σ 0) (σ 2) (σ 3) (σ 4) (σ 6) (σ 8). Applying efx_pair_binary_no_one_split completes this case.

    lines 15–22

    uses efx_pair_binary_no_one_split

      · have h0 : σ 0 = σ 1 := hstay 0 (by decide)
        have h2 : σ 4 = σ 5 := hstay 2 (by decide)
        have h3 : σ 6 = σ 7 := hstay 3 (by decide)
        have heq : σ = efx_pair_binary_one_split 1 (σ 0) (σ 2) (σ 3) (σ 4) (σ 6) (σ 8) := by
          funext g
          fin_cases g <;> simp [efx_pair_binary_one_split, h0, h2, h3]
        rw [heq]
        exact efx_pair_binary_no_one_split 1 (σ 0) (σ 2) (σ 3) (σ 4) (σ 6) (σ 8)
  4. When r = 2, the allocation σ is not EFX.

    When r = 2, pairs 0, 1, and 3 remain intact: σ(0) = σ(1), σ(2) = σ(3), and σ(6) = σ(7). Evaluating on all nine goods shows that σ is identical to efx_pair_binary_one_split 2 (σ 0) (σ 2) (σ 4) (σ 5) (σ 6) (σ 8). Applying efx_pair_binary_no_one_split completes this case.

    lines 23–30

    uses efx_pair_binary_no_one_split

      · have h0 : σ 0 = σ 1 := hstay 0 (by decide)
        have h1 : σ 2 = σ 3 := hstay 1 (by decide)
        have h3 : σ 6 = σ 7 := hstay 3 (by decide)
        have heq : σ = efx_pair_binary_one_split 2 (σ 0) (σ 2) (σ 4) (σ 5) (σ 6) (σ 8) := by
          funext g
          fin_cases g <;> simp [efx_pair_binary_one_split, h0, h1, h3]
        rw [heq]
        exact efx_pair_binary_no_one_split 2 (σ 0) (σ 2) (σ 4) (σ 5) (σ 6) (σ 8)
  5. When r = 3, the allocation σ is not EFX.

    When r = 3, pairs 0, 1, and 2 remain intact: σ(0) = σ(1), σ(2) = σ(3), and σ(4) = σ(5). Evaluating on all nine goods shows that σ is identical to efx_pair_binary_one_split 3 (σ 0) (σ 2) (σ 4) (σ 6) (σ 7) (σ 8). Applying efx_pair_binary_no_one_split completes the final case.

    lines 31–38

    uses efx_pair_binary_no_one_split

      · have h0 : σ 0 = σ 1 := hstay 0 (by decide)
        have h1 : σ 2 = σ 3 := hstay 1 (by decide)
        have h2 : σ 4 = σ 5 := hstay 2 (by decide)
        have heq : σ = efx_pair_binary_one_split 3 (σ 0) (σ 2) (σ 4) (σ 6) (σ 7) (σ 8) := by
          funext g
          fin_cases g <;> simp [efx_pair_binary_one_split, h0, h1, h2]
        rw [heq]
        exact efx_pair_binary_no_one_split 3 (σ 0) (σ 2) (σ 4) (σ 6) (σ 7) (σ 8)
efx_pair_binary_no_one_split
For any index r ∈ Fin 4 and agent assignments a, b, c, d, e, f ∈ Fin 4, the allocation efx_pair_binary_one_split r a b c d e f fails to satisfy the EFX property with respect to the binary valuation matrix efx_pair_binary_values.

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_no_one_split_allocation (σ : Fin 9 → Fin 4) (r : Fin 4)    (hstay : ∀ j : Fin 4, j ≠ r → σ (![0,2,4,6] j) = σ (![1,3,5,7] j)) :    ¬ is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ)) σ := by  fin_cases r  · have h1 : σ 2 = σ 3 := hstay 1 (by decide)    have h2 : σ 4 = σ 5 := hstay 2 (by decide)    have h3 : σ 6 = σ 7 := hstay 3 (by decide)    have heq : σ = efx_pair_binary_one_split 0 (σ 0) (σ 1) (σ 2) (σ 4) (σ 6) (σ 8) := by      funext g      fin_cases g <;> simp [efx_pair_binary_one_split, h1, h2, h3]    rw [heq]    exact efx_pair_binary_no_one_split 0 (σ 0) (σ 1) (σ 2) (σ 4) (σ 6) (σ 8)  · have h0 : σ 0 = σ 1 := hstay 0 (by decide)    have h2 : σ 4 = σ 5 := hstay 2 (by decide)    have h3 : σ 6 = σ 7 := hstay 3 (by decide)    have heq : σ = efx_pair_binary_one_split 1 (σ 0) (σ 2) (σ 3) (σ 4) (σ 6) (σ 8) := by      funext g      fin_cases g <;> simp [efx_pair_binary_one_split, h0, h2, h3]    rw [heq]    exact efx_pair_binary_no_one_split 1 (σ 0) (σ 2) (σ 3) (σ 4) (σ 6) (σ 8)  · have h0 : σ 0 = σ 1 := hstay 0 (by decide)    have h1 : σ 2 = σ 3 := hstay 1 (by decide)    have h3 : σ 6 = σ 7 := hstay 3 (by decide)    have heq : σ = efx_pair_binary_one_split 2 (σ 0) (σ 2) (σ 4) (σ 5) (σ 6) (σ 8) := by      funext g      fin_cases g <;> simp [efx_pair_binary_one_split, h0, h1, h3]    rw [heq]    exact efx_pair_binary_no_one_split 2 (σ 0) (σ 2) (σ 4) (σ 5) (σ 6) (σ 8)  · have h0 : σ 0 = σ 1 := hstay 0 (by decide)    have h1 : σ 2 = σ 3 := hstay 1 (by decide)    have h2 : σ 4 = σ 5 := hstay 2 (by decide)    have heq : σ = efx_pair_binary_one_split 3 (σ 0) (σ 2) (σ 4) (σ 6) (σ 7) (σ 8) := by      funext g      fin_cases g <;> simp [efx_pair_binary_one_split, h0, h1, h2]    rw [heq]    exact efx_pair_binary_no_one_split 3 (σ 0) (σ 2) (σ 4) (σ 6) (σ 7) (σ 8)
See it in the graphDiscuss this resultChallenge it