AFTD Auto-Formalizing Theoretical Domains

efx_three_small_goods_obstruction_no_two_nat

theoremverified

Every coarse allocation whose first old pair is given to agent 2 fails the conjunction of current utility preservation and the exact natural-number EFX inequalities in the explicit eleven-good instance.

Statement

theorem efx_three_small_goods_obstruction_no_two_nat : ∀ b c d e f g : Fin 4,
    ¬ efx_three_small_goods_obstruction_feasible_nat ![2,b,c,d,e,f,g]
Source
Route obstruction for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. Experiments 11265, 11268, and 11269. The last independently exhausts all 16384 full coarse assignments and all 1152 old-permutation two-bonus states; a row scaling removes a welfare-maximizer tie. General Pareto-monotone EFX completion barriers are already known in arXiv:2002.05119v3 Section 5. This explicit three-universally-small-goods example constrains maximum-sum two-bonus completion, not EFX existence or the original-diagonal three-bonus conjecture, and carries no research-level novelty claim.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1

The proof, explained

The theorem establishes that no coarse allocation in the explicit eleven-good instance can be feasible if the first pair of goods is assigned to agent 2. Assuming feasibility for contradiction, the proof extracts each agent's utility threshold requirement and rewrites the allocated bundles using a sum decomposition lemma that groups the eleven goods into four pairs and three single items. Auxiliary lemmas upper-bound the maximum utility any agent can obtain from the three single items by 200, 400, 200, and 200, respectively. Finally, an exhaustive case analysis across all 64 possible assignments of the remaining three pairs of goods demonstrates via linear arithmetic that the threshold inequalities can never be simultaneously met.

  1. The total utility sum for agent $i$ decomposes into the sum of values of the four pairs of goods and the three single goods assigned to $i$. automation

    Expanding the definition of the coarse allocation and the sum over $\operatorname{Fin} 11$ using `Fin.sum_univ_succ`, the proof splits by cases over whether $p(k) = i$ for each $k \in \{0, \dots, 6\}$. In each of the 128 branches, simplification and linear arithmetic (`omega`) verify that the sum of the eleven items matches the seven grouped terms.

    lines 12–15

    uses Fin.sum_univ_succ

      simp only [efx_three_small_goods_obstruction_coarse, Fin.sum_univ_succ]
      by_cases h0 : p 0 = i <;> by_cases h1 : p 1 = i <;> by_cases h2 : p 2 = i <;>
        by_cases h3 : p 3 = i <;> by_cases h4 : p 4 = i <;> by_cases h5 : p 5 = i <;>
        by_cases h6 : p 6 = i <;> simp_all <;> omega
  2. The utility contribution of the three single goods to agent 0 is at most 200. automation

    For agent 0, goods 8, 9, and 10 have values 83, 115, and 2. Since $83 + 115 + 2 = 200$, the sum of values of goods assigned to agent 0 is at most 200, verified by case analysis on whether $e=0, f=0, g=0$ (`split_ifs`) and linear arithmetic (`omega`).

    lines 17–19

    private lemma efx_three_small_goods_obstruction_no_two_nat_bound0 (e f g : Fin 4) :
        (if e = 0 then 83 else 0) + (if f = 0 then 115 else 0) + (if g = 0 then 2 else 0) ≤ 200 := by
      split_ifs <;> omega
  3. The utility contribution of the three single goods to agent 1 is at most 400. automation

    For agent 1, goods 8, 9, and 10 have values 4, 392, and 4, whose sum is $4 + 392 + 4 = 400 \le 400$. The bound holds for all recipient choices $e, f, g$, verified by `split_ifs` and `omega`.

    lines 21–23

    private lemma efx_three_small_goods_obstruction_no_two_nat_bound1 (e f g : Fin 4) :
        (if e = 1 then 4 else 0) + (if f = 1 then 392 else 0) + (if g = 1 then 4 else 0) ≤ 400 := by
      split_ifs <;> omega
  4. The utility contribution of the three single goods to agent 2 is at most 200. automation

    For agent 2, goods 8, 9, and 10 have values 34, 2, and 164, whose sum is $34 + 2 + 164 = 200 \le 200$. The bound holds for all recipient choices $e, f, g$, verified by `split_ifs` and `omega`.

    lines 25–27

    private lemma efx_three_small_goods_obstruction_no_two_nat_bound2 (e f g : Fin 4) :
        (if e = 2 then 34 else 0) + (if f = 2 then 2 else 0) + (if g = 2 then 164 else 0) ≤ 200 := by
      split_ifs <;> omega
  5. The utility contribution of the three single goods to agent 3 is at most 200. automation

    For agent 3, goods 8, 9, and 10 have values 2, 83, and 115, whose sum is $2 + 83 + 115 = 200 \le 200$. The bound holds for all recipient choices $e, f, g$, verified by `split_ifs` and `omega`.

    lines 29–31

    private lemma efx_three_small_goods_obstruction_no_two_nat_bound3 (e f g : Fin 4) :
        (if e = 3 then 2 else 0) + (if f = 3 then 83 else 0) + (if g = 3 then 115 else 0) ≤ 200 := by
      split_ifs <;> omega
  6. Assuming feasibility, each agent $0, 1, 2, 3$ must receive total utility at least their threshold.

    We introduce the allocation variables $b, c, d, e, f, g$ and the feasibility hypothesis `hf`. Specializing the threshold condition of feasibility (`hf.1`) at agents 0, 1, 2, and 3 yields four utility lower bounds $h_0, h_1, h_2, h_3$.

    lines 35–39

      intro b c d e f g hf
      have h0 := hf.1 0
      have h1 := hf.1 1
      have h2 := hf.1 2
      have h3 := hf.1 3
  7. The threshold inequalities for agents 0, 1, 2, 3 are rewritten in terms of the specific valuations, with agent 2 receiving the first pair.

    We rewrite the utility sums in $h_0, h_1, h_2, h_3$ using `efx_three_small_goods_obstruction_no_two_nat_sum_id`. We then evaluate the values and thresholds: agent 2 receives the first pair (value $284 + 284 = 568$), while agents 0, 1, and 3 receive 0 from that pair; their thresholds are 883, 1992, 800, and 800 respectively.

    lines 40–41

    uses efx_three_small_goods_obstruction_no_two_nat_sum_id

      rw [efx_three_small_goods_obstruction_no_two_nat_sum_id] at h0 h1 h2 h3
      simp [efx_three_small_goods_obstruction_values, efx_three_small_goods_obstruction_threshold] at h0 h1 h2 h3
  8. The single-good utility bounds are established for each agent under the given allocation.

    We instantiate the four auxiliary lemmas `efx_three_small_goods_obstruction_no_two_nat_bound0` through `bound3` with the single-good recipients $e, f, g$, obtaining upper bounds $hb_0, hb_1, hb_2, hb_3$ on the utility each agent can obtain from items 8, 9, and 10.

    lines 42–45

    uses efx_three_small_goods_obstruction_no_two_nat_bound0, efx_three_small_goods_obstruction_no_two_nat_bound1, efx_three_small_goods_obstruction_no_two_nat_bound2, efx_three_small_goods_obstruction_no_two_nat_bound3

      have hb0 := efx_three_small_goods_obstruction_no_two_nat_bound0 e f g
      have hb1 := efx_three_small_goods_obstruction_no_two_nat_bound1 e f g
      have hb2 := efx_three_small_goods_obstruction_no_two_nat_bound2 e f g
      have hb3 := efx_three_small_goods_obstruction_no_two_nat_bound3 e f g
  9. No assignment of the remaining three pairs of goods can satisfy all four threshold inequalities, deriving a contradiction. automation

    We perform an exhaustive case split using `fin_cases` across all $4^3 = 64$ possible assignments of the pairs $b, c, d \in \{0, 1, 2, 3\}$. In every case, simplifying the threshold hypotheses and invoking `omega` with the single-good bounds shows that the required utilities cannot be simultaneously satisfied, reaching a contradiction in all branches.

    lines 46–47

      fin_cases b <;> fin_cases c <;> fin_cases d <;>
        simp at h0 h1 h2 h3 <;> omega
Fin.sum_univ_succ
A finite sum over $\operatorname{Fin}(n+1)$ can be split into the first term at 0 plus the sum of the remaining terms.
efx_three_small_goods_obstruction_no_two_nat_sum_id
Under coarse allocation $p$, the total utility agent $i$ receives from all eleven goods equals the sum of values of the four pairs (if assigned to $i$) plus the values of the three single goods (if assigned to $i$).
efx_three_small_goods_obstruction_no_two_nat_bound0
The total utility agent 0 can receive from the three single goods is at most 200, regardless of the assignment $e, f, g$.
efx_three_small_goods_obstruction_no_two_nat_bound1
The total utility agent 1 can receive from the three single goods is at most 400, regardless of the assignment $e, f, g$.
efx_three_small_goods_obstruction_no_two_nat_bound2
The total utility agent 2 can receive from the three single goods is at most 200, regardless of the assignment $e, f, g$.
efx_three_small_goods_obstruction_no_two_nat_bound3
The total utility agent 3 can receive from the three single goods is at most 200, regardless of the assignment $e, f, g$.

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

Lean’s trace was cut to the first 400 of 569 tactics.

open Function Finsetprivate lemma efx_three_small_goods_obstruction_no_two_nat_sum_id (p : Fin 7 → Fin 4) (i : Fin 4) :  (∑ h : Fin 11, if efx_three_small_goods_obstruction_coarse p h = i then efx_three_small_goods_obstruction_values i h else 0)  = (if p 0 = i then efx_three_small_goods_obstruction_values i 0 + efx_three_small_goods_obstruction_values i 1 else 0)    + (if p 1 = i then efx_three_small_goods_obstruction_values i 2 + efx_three_small_goods_obstruction_values i 3 else 0)    + (if p 2 = i then efx_three_small_goods_obstruction_values i 4 + efx_three_small_goods_obstruction_values i 5 else 0)    + (if p 3 = i then efx_three_small_goods_obstruction_values i 6 + efx_three_small_goods_obstruction_values i 7 else 0)    + (if p 4 = i then efx_three_small_goods_obstruction_values i 8 else 0)    + (if p 5 = i then efx_three_small_goods_obstruction_values i 9 else 0)    + (if p 6 = i then efx_three_small_goods_obstruction_values i 10 else 0) := by  simp only [efx_three_small_goods_obstruction_coarse, Fin.sum_univ_succ]  by_cases h0 : p 0 = i <;> by_cases h1 : p 1 = i <;> by_cases h2 : p 2 = i <;>    by_cases h3 : p 3 = i <;> by_cases h4 : p 4 = i <;> by_cases h5 : p 5 = i <;>    by_cases h6 : p 6 = i <;> simp_all <;> omegaprivate lemma efx_three_small_goods_obstruction_no_two_nat_bound0 (e f g : Fin 4) :    (if e = 0 then 83 else 0) + (if f = 0 then 115 else 0) + (if g = 0 then 2 else 0) ≤ 200 := by  split_ifs <;> omegaprivate lemma efx_three_small_goods_obstruction_no_two_nat_bound1 (e f g : Fin 4) :    (if e = 1 then 4 else 0) + (if f = 1 then 392 else 0) + (if g = 1 then 4 else 0) ≤ 400 := by  split_ifs <;> omegaprivate lemma efx_three_small_goods_obstruction_no_two_nat_bound2 (e f g : Fin 4) :    (if e = 2 then 34 else 0) + (if f = 2 then 2 else 0) + (if g = 2 then 164 else 0) ≤ 200 := by  split_ifs <;> omegaprivate lemma efx_three_small_goods_obstruction_no_two_nat_bound3 (e f g : Fin 4) :    (if e = 3 then 2 else 0) + (if f = 3 then 83 else 0) + (if g = 3 then 115 else 0) ≤ 200 := by  split_ifs <;> omegatheorem efx_three_small_goods_obstruction_no_two_nat : ∀ b c d e f g : Fin 4,    ¬ efx_three_small_goods_obstruction_feasible_nat ![2,b,c,d,e,f,g] := by  intro b c d e f g hf  have h0 := hf.1 0  have h1 := hf.1 1  have h2 := hf.1 2  have h3 := hf.1 3  rw [efx_three_small_goods_obstruction_no_two_nat_sum_id] at h0 h1 h2 h3  simp [efx_three_small_goods_obstruction_values, efx_three_small_goods_obstruction_threshold] at h0 h1 h2 h3  have hb0 := efx_three_small_goods_obstruction_no_two_nat_bound0 e f g  have hb1 := efx_three_small_goods_obstruction_no_two_nat_bound1 e f g  have hb2 := efx_three_small_goods_obstruction_no_two_nat_bound2 e f g  have hb3 := efx_three_small_goods_obstruction_no_two_nat_bound3 e f g  fin_cases b <;> fin_cases c <;> fin_cases d <;>    simp at h0 h1 h2 h3 <;> omega
See it in the graphDiscuss this resultChallenge it