AFTD Auto-Formalizing Theoretical Domains

efx_pair_binary_no_one_split

theoremverified

For the explicit binary nine-good matrix cast to real values, no allocation encoded by the one-split construction is EFX.

Statement

theorem efx_pair_binary_no_one_split (r a b c d e f : Fin 4) :
    ¬ is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ))
      (efx_pair_binary_one_split r a b c d e f)
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 6
  • is_efx_goods_nat_cast_iffFor natural-number item values, EFX after casting values to the reals is equivalent to all natural-number inequalities comparing each…
  • 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_split_natFor the explicit binary nine-good matrix, every allocation encoded by the one-split construction fails a natural-number total-value 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…
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
Used by 1

The proof, explained

The proof proceeds by contradiction, assuming that the one-split allocation is EFX under the real-cast binary valuation matrix. Using `is_efx_goods_nat_cast_iff`, this assumption is converted into an equivalent inequality on natural-number bundle sums. The proof then applies `efx_pair_binary_no_one_split_nat`, which establishes that no one-split allocation satisfies this EFX inequality when formulated using indicator sums over all goods. Finally, rewriting the bundle sums as indicator sums over all nine goods using `Finset.sum_filter` shows that the allocation satisfies that condition, reaching the desired contradiction.

  1. Assuming the allocation is EFX, the valuations satisfy the natural-number EFX inequality on agent bundles.

    We assume for contradiction that the one-split allocation is EFX under the real-cast valuations (line 6). Using `is_efx_goods_nat_cast_iff`, we convert the EFX condition on real numbers into an equivalent natural-number condition: for every pair of distinct agents i ≠ j and every good g in j's bundle, the sum of i's valuations on j's bundle is at most the sum on i's own bundle plus the value of g to agent i (line 7).

    lines 6–7

    uses is_efx_goods_nat_cast_iff

      intro h
      have hh := (is_efx_goods_nat_cast_iff efx_pair_binary_values (efx_pair_binary_one_split r a b c d e f)).mp h
  2. It suffices to show that the allocation satisfies the indicator-sum formulation of the EFX condition.

    We invoke `efx_pair_binary_no_one_split_nat`, which proves that no one-split allocation satisfies the EFX condition when written as sums over all goods with indicator conditionals. This reduces reaching a contradiction to proving that our allocation satisfies this indicator-sum inequality.

    line 8

    uses efx_pair_binary_no_one_split_nat

      apply efx_pair_binary_no_one_split_nat r a b c d e f
  3. The allocation satisfies the indicator-sum formulation of the EFX condition.

    To discharge the premise of `efx_pair_binary_no_one_split_nat`, we take distinct agents i ≠ j and an item g assigned to agent j (line 9). By definition of `bundle_of`, the assignment σ(g) = j means g belongs to j's bundle (line 10). Applying our natural-number EFX hypothesis hh gives the EFX inequality in terms of bundle sums (line 11). Finally, converting the sums over bundles into sums over all nine goods with indicator functions via `Finset.sum_filter` matches the target inequality and completes the proof (line 12).

    lines 9–12

    uses Finset.sum_filter

      intro i j hij g hg
      have hm : g ∈ bundle_of (efx_pair_binary_one_split r a b c d e f) j := by simpa [bundle_of] using hg
      have h' := hh i j hij g hm
      simpa only [bundle_of, Finset.sum_filter] using h'
is_efx_goods_nat_cast_iff
An allocation of goods is EFX for integer valuations cast to real numbers if and only if for all distinct agents i and j and every good g in j's bundle, the sum of i's values on j's bundle is at most the sum of i's values on i's own bundle plus i's value for g.
efx_pair_binary_no_one_split_nat
For any parameters defining a one-split allocation of nine goods among four agents, the allocation does not satisfy the discrete EFX condition formulated with indicator sums over all goods.
Finset.sum_filter
The sum of a function over elements of a finite set satisfying a predicate equals the sum over the entire finite set where terms not satisfying the predicate are replaced by zero.

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 (r a b c d e f : Fin 4) :    ¬ is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ))      (efx_pair_binary_one_split r a b c d e f) := by  intro h  have hh := (is_efx_goods_nat_cast_iff efx_pair_binary_values (efx_pair_binary_one_split r a b c d e f)).mp h  apply efx_pair_binary_no_one_split_nat r a b c d e f  intro i j hij g hg  have hm : g ∈ bundle_of (efx_pair_binary_one_split r a b c d e f) j := by simpa [bundle_of] using hg  have h' := hh i j hij g hm  simpa only [bundle_of, Finset.sum_filter] using h'
See it in the graphDiscuss this resultChallenge it