AFTD Auto-Formalizing Theoretical Domains

efx_pair_binary_no_one_split_zero_nat

theoremverified

For the explicit binary nine-good matrix, every one-split allocation allowing only the old pair indexed 0 to split fails a natural-number total-value EFX inequality.

Statement

theorem efx_pair_binary_no_one_split_zero_nat : ∀ (a b c d e f : Fin 4),
    ¬ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 9, efx_pair_binary_one_split 0 a b c d e f g = j →
      (∑ h : Fin 9, if efx_pair_binary_one_split 0 a b c d e f h = j then efx_pair_binary_values i h else 0) ≤
      (∑ h : Fin 9, if efx_pair_binary_one_split 0 a b c d e f h = i then efx_pair_binary_values i h else 0) +
        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 2
  • 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…
Used by 1
  • efx_pair_binary_no_one_split_natFor the explicit binary nine-good matrix, every allocation encoded by the one-split construction fails a natural-number total-value EFX…

The proof, explained

The theorem states that in a fair division setting with 4 agents and 9 items under the specified binary valuations, no allocation following the template where only the first pair of goods is split can be envy-free up to any good (EFX). Because the parameter and item sets are finite, there are only $4^6 = 4096$ candidate allocations to consider. The proof introduces the recipient $a \in \{0, 1, 2, 3\}$ of the first good, branches into four cases, and uses exhaustive evaluation in the Lean kernel (`decide +kernel`) to verify that an EFX violation occurs in every case.

  1. It suffices to fix an arbitrary agent $a \in \{0, 1, 2, 3\}$ receiving the first item and show the non-EFX property for all remaining parameters $b, c, d, e, f$.

    We introduce the parameter $a$, which represents the agent receiving the first item of the split pair, leaving a universal quantification over the remaining recipients $b, c, d, e, f \in \{0, 1, 2, 3\}$.

    line 8

      intro a
  2. In each of the four cases $a \in \{0, 1, 2, 3\}$, no choice of the remaining parameters $b, c, d, e, f$ produces an EFX allocation. automation

    We perform a case analysis on the four possible values of $a \in \{0, 1, 2, 3\}$. For each fixed $a$, the claim is a decidable proposition quantifying over the finite parameter space $\{0, 1, 2, 3\}^5$ (1024 allocations), where each allocation is tested against all pairs of distinct agents $i \ne j$ and goods $g$ allocated to $j$. The kernel decision procedure evaluates these sums and inequalities directly, confirming that in every case there is a pair of agents $(i, j)$ and a good $g \in A_j$ such that agent $i$'s valuation of $A_j \setminus \{g\}$ strictly exceeds their valuation of their own bundle $A_i$.

    line 9

      fin_cases a <;> decide +kernel

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_zero_nat : ∀ (a b c d e f : Fin 4),    ¬ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 9, efx_pair_binary_one_split 0 a b c d e f g = j →      (∑ h : Fin 9, if efx_pair_binary_one_split 0 a b c d e f h = j then efx_pair_binary_values i h else 0) ≤      (∑ h : Fin 9, if efx_pair_binary_one_split 0 a b c d e f h = i then efx_pair_binary_values i h else 0) +        efx_pair_binary_values i g) := by  intro a  fin_cases a <;> decide +kernel
See it in the graphDiscuss this resultChallenge it