AFTD Auto-Formalizing Theoretical Domains

efx_three_small_goods_completion_loss_or_split

theoremverified

In the explicit eleven-good instance cast to real values, every complete EFX allocation which keeps each of the four old adjacent pairs intact has some agent whose utility is strictly less than her starting ten-good EFX utility threshold. Thus a completion preserving all current utilities must split an old pair.

Statement

theorem efx_three_small_goods_completion_loss_or_split (σ : Fin 11 → Fin 4)
    (hEF : is_efx_goods (fun i g => (efx_three_small_goods_obstruction_values i g : ℝ)) σ)
    (hstay : σ 0 = σ 1 ∧ σ 2 = σ 3 ∧ σ 4 = σ 5 ∧ σ 6 = σ 7) :
    ∃ i : Fin 4, additive_valuation (fun g => (efx_three_small_goods_obstruction_values i g : ℝ))
      (bundle_of σ i) < (efx_three_small_goods_obstruction_threshold i : ℝ)
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 7
  • efx_three_small_goods_obstruction_valuesThe explicit positive four-agent eleven-good natural-valued matrix from experiment 11269, with four old adjacent pairs among goods 0…
  • efx_three_small_goods_obstruction_coarseAn allocation of the eleven goods obtained by assigning each of the four old adjacent pairs intact to arbitrary agents p(0),...,p(3), and…
  • efx_three_small_goods_obstruction_thresholdThe four current utility thresholds (883,1992,800,800), attained by the starting EFX allocation of the first ten goods in the explicit…
  • efx_three_small_goods_obstruction_no_current_irIn the explicit eleven-good instance cast to real values, every EFX coarse completion has some agent whose utility is strictly less than…
  • 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.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.

The proof, explained

The proof reduces the claim to the obstruction theorem `efx_three_small_goods_obstruction_no_current_ir`, which rules out coarse EFX allocations that preserve all utility thresholds. Because the allocation σ keeps the four adjacent pairs of goods intact, it is functionally identical to a coarse allocation p of 7 items (the four pairs plus the three individual goods). After verifying this identity by exhaustive casework on all eleven goods, applying the obstruction theorem concludes that some agent must fall strictly below their starting utility threshold.

  1. Decompose the pair-preservation hypothesis and define the coarse 7-item allocation p.

    The hypothesis `hstay` decomposes into four equalities: σ(0) = σ(1), σ(2) = σ(3), σ(4) = σ(5), and σ(6) = σ(7), which assert that each of the four adjacent pairs of goods is assigned to the same agent. We then define a coarse allocation p on 7 items that assigns each of the four intact pairs (via representative goods 0, 2, 4, 6) and the three remaining individual goods (8, 9, 10) to their respective recipients under σ.

    lines 8–9

      rcases hstay with ⟨h0,h1,h2,h3⟩
      let p : Fin 7 → Fin 4 := ![σ 0,σ 2,σ 4,σ 6,σ 8,σ 9,σ 10]
  2. The allocation σ coincides with the coarse allocation induced by p.

    By function extensionality, it suffices to show σ(g) = efx_three_small_goods_obstruction_coarse(p)(g) for every good g in {0, ..., 10}. An exhaustive case analysis over all eleven goods confirms this: for each pair {0, 1}, {2, 3}, {4, 5}, and {6, 7}, both goods receive the same agent by the pair-preservation hypotheses, and the remaining goods 8, 9, 10 match the definition of p directly.

    lines 10–12

      have heq : σ = efx_three_small_goods_obstruction_coarse p := by
        funext g
        fin_cases g <;> simp [p, efx_three_small_goods_obstruction_coarse, h0, h1, h2, h3]
  3. Some agent receives utility strictly below their threshold.

    Rewriting σ with the coarse allocation efx_three_small_goods_obstruction_coarse(p) in both the EFX hypothesis and the goal turns the statement into the obstruction theorem `efx_three_small_goods_obstruction_no_current_ir`, which directly concludes that some agent's utility falls strictly below their starting EFX threshold.

    lines 13–14

    uses efx_three_small_goods_obstruction_no_current_ir

      rw [heq] at hEF ⊢
      exact efx_three_small_goods_obstruction_no_current_ir p hEF
efx_three_small_goods_obstruction_no_current_ir
For any coarse allocation of 7 items among 4 agents, if the induced 11-good allocation is EFX with respect to the obstruction valuations, then at least one agent receives an additive utility strictly less than their starting threshold.

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_three_small_goods_completion_loss_or_split (σ : Fin 11 → Fin 4)    (hEF : is_efx_goods (fun i g => (efx_three_small_goods_obstruction_values i g : ℝ)) σ)    (hstay : σ 0 = σ 1 ∧ σ 2 = σ 3 ∧ σ 4 = σ 5 ∧ σ 6 = σ 7) :    ∃ i : Fin 4, additive_valuation (fun g => (efx_three_small_goods_obstruction_values i g : ℝ))      (bundle_of σ i) < (efx_three_small_goods_obstruction_threshold i : ℝ) := by  rcases hstay with ⟨h0,h1,h2,h3⟩  let p : Fin 7 → Fin 4 := ![σ 0,σ 2,σ 4,σ 6,σ 8,σ 9,σ 10]  have heq : σ = efx_three_small_goods_obstruction_coarse p := by    funext g    fin_cases g <;> simp [p, efx_three_small_goods_obstruction_coarse, h0, h1, h2, h3]  rw [heq] at hEF ⊢  exact efx_three_small_goods_obstruction_no_current_ir p hEF
See it in the graphDiscuss this resultChallenge it