AFTD Auto-Formalizing Theoretical Domains

efx_exists_of_two_universal_small_goods_ir

theoremverifiedoriginal

Let m and n be natural numbers with n positive. There are m+2 goods with nonnegative real additive values for n agents. Each agent values each of the last two goods no more than every one of the first m goods, with no required order between the last two. Given any complete EFX allocation of the first m goods, there exists a complete EFX allocation of all m+2 goods in which every agent has at least her original utility and any two old goods originally allocated together are still allocated together, possibly to a different agent. EFX tests deletion of every good, including a zero-valued one.

Statement

theorem efx_exists_of_two_universal_small_goods_ir {m n : ℕ} (hn : 0 < n)
    (u : Fin n → Fin (m+2) → ℝ) (hu : ∀ i g, 0 ≤ u i g)
    (hsmall₀ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m).castSucc ≤ u i g.castSucc.castSucc)
    (hsmall₁ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last (m+1)) ≤ u i g.castSucc.castSucc)
    (σ : Fin m → Fin n) (hσ : is_efx_goods (fun i g => u i g.castSucc.castSucc) σ) :
    ∃ τ : Fin (m+2) → Fin n, is_efx_goods u τ ∧
      (∀ i, additive_valuation (fun g : Fin m => u i g.castSucc.castSucc) (bundle_of σ i) ≤
        additive_valuation (u i) (bundle_of τ i)) ∧
      (∀ g h : Fin m, σ g = σ h → τ g.castSucc.castSucc = τ h.castSucc.castSucc)
Related work
Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. The baseline is universally least-good insertion for a common individual ranking in arXiv:1707.04769v3 Appendix B. Here the two new goods need not have a common order. Web searches on 2026-11-01 for two smallest goods, ordered pairs, common pair order, and EFX completion found no matching result; arXiv:2504.03951 concerns n+2 goods and does not supply this arbitrary-old-allocation preservation statement. This does not settle unrestricted four-agent EFX.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • additive_valuation_erase_of_memRemoving a good belonging to a finite bundle subtracts exactly its item value from the additive value of that bundle.
  • bundle_of_permute_agentsReassigning every good by the inverse of an agent permutation makes the bundle of agent i equal to the old bundle of the permuted agent.
  • is_efx_goods_all_pairsFor nonnegative additive values, the EFX inequalities also hold when the observer and the target agent coincide.
  • additive_valuation_bundle_last_casesAssigning the additional last good to agent s adds exactly its value to the old bundle value of s and leaves every other bundle value…
  • finite_two_bonus_ordered_assignmentFor any finite nonempty real matrix w and two nonnegative agent-dependent bonuses a and b, there is a permutation of the old columns, a…
  • 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.
Used by 1

Read back from the Lean

For any natural numbers $m$ and $n$ with $0 < n$, any valuation profile $u : \text{Fin } n \to \text{Fin } (m+2) \to \mathbb{R}$ such that: 1. $u$ is non-negative everywhere ($0 \le u(i, g)$ for all $i, g$); 2. the item at index $m$ (represented by (Fin.last m).castSucc) is weakly less valued by every agent $i$ than any of the first $m$ items (represented by g.castSucc.castSucc for $g : \text{Fin } m$); 3. the item at index $m+1$ (represented by Fin.last (m+1)) is weakly less valued by every agent $i$ than any of the first $m$ items; and for any allocation $\sigma : \text{Fin } m \to \text{Fin } n$ of the first $m$ items that is EFX for goods under the valuations restricted to the first $m$ items: there exists an allocation $\tau : \text{Fin } (m+2) \to \text{Fin } n$ of all $m+2$ items such that: 1. $\tau$ is EFX for goods under $u$; 2. every agent $i$ values their bundle under $\tau$ (under $u(i)$) at least as much as they valued their bundle under $\sigma$ (under the restricted valuation); 3. any two items $g, h \in \text{Fin } m$ that were assigned to the same agent under $\sigma$ remain assigned to the same agent under $\tau$ (i.e., $\sigma(g) = \sigma(h) \implies \tau(g) = \tau(h)$ after embedding into $\text{Fin } (m+2)$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof extends an existing EFX allocation σ of m goods to all m + 2 goods by reducing the extension to an assignment problem with two bonus goods. Applying the lemma finite_two_bonus_ordered_assignment yields a permutation p of the original bundles and two designated bonus recipients r and s such that each agent weakly improves their utility and non-envy holds whenever a bonus good is trimmed. In the resulting allocation τ, any removed item g is either one of the bonus goods (satisfying EFX by the assignment lemma) or an original good, in which case removing g reduces envy at least as much as trimming a bonus good (by universal smallness) or reduces to the original EFX allocation (if the bundle contains no bonus goods). Bundles from σ are preserved intact because the permutation reassigns each original bundle as an indivisible unit.

  1. There exist a permutation p of the agents and recipients r, s for the two bonus goods satisfying individual rationality and non-envy upon removing each bonus good.

    We define w(i, j) as agent i's valuation of bundle j under the initial allocation σ, and a(i), b(i) as agent i's valuations of the two additional goods (at indices m and m + 1). Since n > 0, the agent type is nonempty. Applying finite_two_bonus_ordered_assignment to w, a, and b yields a permutation p of the agents and two recipients r and s such that each agent weakly prefers their assigned package to their initial bundle (hI), and removing bonus good a from agent r or bonus good b from agent s guarantees no other agent envies them (hA, hB).

    lines 12–18

    uses Nat.ne_of_gt, finite_two_bonus_ordered_assignment

      classical
      letI : NeZero n := ⟨Nat.ne_of_gt hn⟩
      let w (i j : Fin n) := additive_valuation (fun g : Fin m => u i g.castSucc.castSucc) (bundle_of σ j)
      let a (i : Fin n) := u i (Fin.last m).castSucc
      let b (i : Fin n) := u i (Fin.last (m+1))
      obtain ⟨p, r, s, hI, hA, hB⟩ := finite_two_bonus_ordered_assignment w a b
        (fun i => hu i _) (fun i => hu i _)
  2. Define the new allocation τ of all m + 2 goods.

    We define τ₀ on the original m goods by giving agent j the original bundle σ(p(j)), so that τ₀(g) = p⁻¹(σ(g)). We then extend τ₀ to τ₁ on m + 1 goods by assigning the first bonus good (at index m) to recipient r, and finally extend τ₁ to τ on all m + 2 goods by assigning the second bonus good (at index m + 1) to recipient s.

    lines 19–21

      let τ₀ : Fin m → Fin n := fun g => p.symm (σ g)
      let τ₁ : Fin (m+1) → Fin n := Fin.lastCases r τ₀
      let τ : Fin (m+2) → Fin n := Fin.lastCases s τ₁
  3. Under τ, agent i's valuation of agent j's bundle is w(i, p(j)) + (if j = r then a(i) else 0) + (if j = s then b(i) else 0).

    By unfolding the recursive definition of τ and applying additive_valuation_bundle_last_cases twice for the two extra goods, followed by bundle_of_permute_agents for the permuted original allocation, agent j's bundle decomposes into the original bundle p(j) plus bonus good a if j = r and bonus good b if j = s.

    lines 22–26

    uses additive_valuation_bundle_last_cases, bundle_of_permute_agents, eq_comm

      have hval (i j : Fin n) : additive_valuation (u i) (bundle_of τ j) =
          w i (p j) + (if j = r then a i else 0) + (if j = s then b i else 0) := by
        dsimp [τ, τ₁, τ₀]
        rw [additive_valuation_bundle_last_cases, additive_valuation_bundle_last_cases, bundle_of_permute_agents]
        simp only [w, a, b, eq_comm]
  4. Each agent i achieves at least their initial utility under σ: w(i, i) ≤ u_i(bundle_of τ i).

    Rewriting the assignment guarantee hI with the valuation formula hval shows that agent i's utility under τ is at least their utility under σ.

    lines 27–28

      have hown (i : Fin n) : w i i ≤ additive_valuation (u i) (bundle_of τ i) := by
        simpa only [hval] using hI i
  5. Removing the first bonus good from agent r's bundle prevents any agent i ≠ r from envying r.

    Rewriting the condition hA using the bundle valuation formula hval and simplifying the conditionals when j = r, linear arithmetic establishes that agent i's valuation of bundle r minus a(i) is at most their valuation of their own bundle.

    lines 29–35

    uses ite_true

      have htrim₀ (i : Fin n) (hi : i ≠ r) :
          additive_valuation (u i) (bundle_of τ r) - a i ≤
            additive_valuation (u i) (bundle_of τ i) := by
        have hh := hA i hi
        rw [hval, hval]
        simp only [ite_true]
        linarith
  6. Removing the second bonus good from agent s's bundle prevents any agent i ≠ s from envying s.

    Similarly, rewriting the condition hB using hval and simplifying the conditionals when j = s shows by linear arithmetic that agent i's valuation of bundle s minus b(i) is at most their valuation of their own bundle.

    lines 36–42

    uses ite_true

      have htrim₁ (i : Fin n) (hi : i ≠ s) :
          additive_valuation (u i) (bundle_of τ s) - b i ≤
            additive_valuation (u i) (bundle_of τ i) := by
        have hh := hB i hi
        rw [hval, hval]
        simp only [ite_true]
        linarith
  7. It suffices to show that τ is EFX, satisfies individual rationality, and preserves original bundles.

    We provide τ as the witness for the existential quantifier, splitting the theorem into three subgoals: the EFX property of τ, the preservation of each agent's utility, and the bundle integrity condition.

    line 43

      refine ⟨τ, ?_, ?_, ?_⟩
  8. To verify EFX, for any distinct agents i ≠ j and any good g in bundle j, it suffices to show u_i(bundle_of τ j) - u_i(g) ≤ u_i(bundle_of τ i).

    Assuming i ≠ j and g is allocated to j under τ, additive_valuation_erase_of_mem rewrites the valuation of bundle j with g removed as the total valuation of bundle j minus u_i(g).

    lines 44–46

    uses additive_valuation_erase_of_mem

      · intro i j hij g hg
        have hg' : τ g = j := by simpa [bundle_of] using hg
        rw [additive_valuation_erase_of_mem _ _ _ hg]
  9. The EFX condition holds when g is an original good and j = r.

    Using Fin.eq_castSucc_or_eq_last twice, we split on whether g is an original good or one of the two bonus goods. If g is an original good and j = r, agent i ≠ r does not envy r upon removing a(i) by htrim₀. Since g is an original good, the universal smallness hypothesis hsmall₀ gives a(i) ≤ u_i(g), so removing g reduces the bundle value by at least a(i), which leaves no envy by linear arithmetic.

    lines 47–55

    uses Fin.eq_castSucc_or_eq_last

        rcases Fin.eq_castSucc_or_eq_last g with ⟨g₁, rfl⟩ | rfl
        · rcases Fin.eq_castSucc_or_eq_last g₁ with ⟨g₀, rfl⟩ | rfl
          · by_cases hjr : j = r
            · have hi : i ≠ r := by simpa only [hjr] using hij
              rw [hjr]
              have hh := htrim₀ i hi
              have hl := hsmall₀ i g₀
              change a i ≤ u i g₀.castSucc.castSucc at hl
              linarith
  10. The EFX condition holds when g is an original good and j = s (with j ≠ r).

    If j = s, agent i ≠ s does not envy s upon removing b(i) by htrim₁. By the universal smallness hypothesis hsmall₁, b(i) ≤ u_i(g), so removing g removes at least b(i), eliminating envy by linear arithmetic.

    lines 56–62

            · by_cases hjs : j = s
              · have hi : i ≠ s := by simpa only [hjs] using hij
                rw [hjs]
                have hh := htrim₁ i hi
                have hl := hsmall₁ i g₀
                change b i ≤ u i g₀.castSucc.castSucc at hl
                linarith
  11. The EFX condition holds when g is an original good and j receives no bonus goods (j ≠ r and j ≠ s).

    When j ≠ r and j ≠ s, bundle j under τ contains only original goods from bundle p(j), so g belongs to bundle σ(p(j)) via Equiv.symm_apply_eq. Since the original allocation σ was EFX, is_efx_goods_all_pairs and additive_valuation_erase_of_mem imply that removing g leaves at most w(i, i). Since bundle j has no bonus goods, its value is exactly w(i, p(j)), and by individual rationality (hown), w(i, i) ≤ u_i(bundle_of τ i), completing the inequality.

    lines 63–71

    uses Equiv.symm_apply_eq, is_efx_goods_all_pairs, additive_valuation_erase_of_mem, if_neg, add_zero

              · have hold : g₀ ∈ bundle_of σ (p j) := by
                  simpa [τ, τ₁, τ₀, bundle_of, Equiv.symm_apply_eq] using hg'
                have hh := is_efx_goods_all_pairs (fun i (g : Fin m) => u i g.castSucc.castSucc)
                  (fun i g => hu i _) σ hσ i (p j) g₀ hold
                rw [additive_valuation_erase_of_mem _ _ _ hold] at hh
                change w i (p j) - u i g₀.castSucc.castSucc ≤ w i i at hh
                rw [hval]
                simp only [if_neg hjr, if_neg hjs, add_zero]
                exact hh.trans (hown i)
  12. The EFX condition holds when g is the first bonus good.

    Because the first bonus good was given to r, its owner j must be r, so i ≠ r. Removing this good leaves bundle r trimmed by a(i), which is bounded by agent i's bundle value by htrim₀.

    lines 72–75

          · have howner : r = j := by simpa [τ, τ₁, τ₀] using hg'
            have hi : i ≠ r := by simpa only [← howner] using hij
            rw [← howner]
            exact htrim₀ i hi
  13. The EFX condition holds when g is the second bonus good.

    Because the second bonus good was given to s, its owner j must be s, so i ≠ s. Removing this good leaves bundle s trimmed by b(i), which is bounded by agent i's bundle value by htrim₁.

    lines 76–79

        · have howner : s = j := by simpa [τ] using hg'
          have hi : i ≠ s := by simpa only [← howner] using hij
          rw [← howner]
          exact htrim₁ i hi
  14. Each agent i has utility under τ at least their utility under σ.

    This is the individual rationality guarantee hown proved earlier from hI.

    lines 81–82

      · intro i
        exact hown i
  15. Any two original goods allocated together under σ remain allocated together under τ.

    Original goods are assigned by τ according to τ₀ = p⁻¹ ∘ σ. If σ(g) = σ(h), then τ(g) = p⁻¹(σ(g)) = p⁻¹(σ(h)) = τ(h), which simp verifies by unfolding definitions.

    lines 83–84

      · intro g h hgh
        simp [τ, τ₁, τ₀, hgh]
Nat.ne_of_gt
If b < a for natural numbers, then a ≠ b.
finite_two_bonus_ordered_assignment
Given an n × n matrix of valuations and nonnegative valuations for two bonus goods, there exists a permutation of the n agents and two bonus recipients such that each agent weakly prefers their assigned bundle to their initial bundle, and no agent envies either recipient once that recipient's bonus good is removed.
additive_valuation_bundle_last_cases
The additive valuation of a bundle extended by a new item assigned to agent s is the valuation of the unextended bundle plus the value of the new item if s is the owner.
bundle_of_permute_agents
Permuting agents by p assigns to agent i the bundle that was originally allocated to agent p(i).
eq_comm
Equality is symmetric: a = b is equivalent to b = a.
ite_true
An if-then-else expression with a true condition evaluates to the 'then' branch.
Fin.eq_castSucc_or_eq_last
Every element of Fin (n + 1) is either the canonical embedding of an element of Fin n or the last element Fin.last n.
Equiv.symm_apply_eq
For an equivalence e, applying the inverse e.symm to x equals y if and only if x equals e(y).
is_efx_goods_all_pairs
In an EFX allocation with nonnegative valuations, removing any good from agent j's bundle leaves agent i valuing it no more than i's own bundle, even when i = j.
additive_valuation_erase_of_mem
For an additive valuation, removing an item g from a finite set S subtracts the value of g from the total valuation of S.
if_neg
An if-then-else expression with a false condition evaluates to the 'else' branch.
add_zero
Adding zero to an element leaves it unchanged.

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_exists_of_two_universal_small_goods_ir {m n : ℕ} (hn : 0 < n)    (u : Fin n → Fin (m+2) → ℝ) (hu : ∀ i g, 0 ≤ u i g)    (hsmall₀ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m).castSucc ≤ u i g.castSucc.castSucc)    (hsmall₁ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last (m+1)) ≤ u i g.castSucc.castSucc)    (σ : Fin m → Fin n) (hσ : is_efx_goods (fun i g => u i g.castSucc.castSucc) σ) :    ∃ τ : Fin (m+2) → Fin n, is_efx_goods u τ ∧      (∀ i, additive_valuation (fun g : Fin m => u i g.castSucc.castSucc) (bundle_of σ i) ≤        additive_valuation (u i) (bundle_of τ i)) ∧      (∀ g h : Fin m, σ g = σ h → τ g.castSucc.castSucc = τ h.castSucc.castSucc) := by  classical  letI : NeZero n := ⟨Nat.ne_of_gt hn⟩  let w (i j : Fin n) := additive_valuation (fun g : Fin m => u i g.castSucc.castSucc) (bundle_of σ j)  let a (i : Fin n) := u i (Fin.last m).castSucc  let b (i : Fin n) := u i (Fin.last (m+1))  obtain ⟨p, r, s, hI, hA, hB⟩ := finite_two_bonus_ordered_assignment w a b    (fun i => hu i _) (fun i => hu i _)  let τ₀ : Fin m → Fin n := fun g => p.symm (σ g)  let τ₁ : Fin (m+1) → Fin n := Fin.lastCases r τ₀  let τ : Fin (m+2) → Fin n := Fin.lastCases s τ₁  have hval (i j : Fin n) : additive_valuation (u i) (bundle_of τ j) =      w i (p j) + (if j = r then a i else 0) + (if j = s then b i else 0) := by    dsimp [τ, τ₁, τ₀]    rw [additive_valuation_bundle_last_cases, additive_valuation_bundle_last_cases, bundle_of_permute_agents]    simp only [w, a, b, eq_comm]  have hown (i : Fin n) : w i i ≤ additive_valuation (u i) (bundle_of τ i) := by    simpa only [hval] using hI i  have htrim₀ (i : Fin n) (hi : i ≠ r) :      additive_valuation (u i) (bundle_of τ r) - a i ≤        additive_valuation (u i) (bundle_of τ i) := by    have hh := hA i hi    rw [hval, hval]    simp only [ite_true]    linarith  have htrim₁ (i : Fin n) (hi : i ≠ s) :      additive_valuation (u i) (bundle_of τ s) - b i ≤        additive_valuation (u i) (bundle_of τ i) := by    have hh := hB i hi    rw [hval, hval]    simp only [ite_true]    linarith  refine ⟨τ, ?_, ?_, ?_⟩  · intro i j hij g hg    have hg' : τ g = j := by simpa [bundle_of] using hg    rw [additive_valuation_erase_of_mem _ _ _ hg]    rcases Fin.eq_castSucc_or_eq_last g with ⟨g₁, rfl⟩ | rfl    · rcases Fin.eq_castSucc_or_eq_last g₁ with ⟨g₀, rfl⟩ | rfl      · by_cases hjr : j = r        · have hi : i ≠ r := by simpa only [hjr] using hij          rw [hjr]          have hh := htrim₀ i hi          have hl := hsmall₀ i g₀          change a i ≤ u i g₀.castSucc.castSucc at hl          linarith        · by_cases hjs : j = s          · have hi : i ≠ s := by simpa only [hjs] using hij            rw [hjs]            have hh := htrim₁ i hi            have hl := hsmall₁ i g₀            change b i ≤ u i g₀.castSucc.castSucc at hl            linarith          · have hold : g₀ ∈ bundle_of σ (p j) := by              simpa [τ, τ₁, τ₀, bundle_of, Equiv.symm_apply_eq] using hg'            have hh := is_efx_goods_all_pairs (fun i (g : Fin m) => u i g.castSucc.castSucc)              (fun i g => hu i _) σ hσ i (p j) g₀ hold            rw [additive_valuation_erase_of_mem _ _ _ hold] at hh            change w i (p j) - u i g₀.castSucc.castSucc ≤ w i i at hh            rw [hval]            simp only [if_neg hjr, if_neg hjs, add_zero]            exact hh.trans (hown i)      · have howner : r = j := by simpa [τ, τ₁, τ₀] using hg'        have hi : i ≠ r := by simpa only [← howner] using hij        rw [← howner]        exact htrim₀ i hi    · have howner : s = j := by simpa [τ] using hg'      have hi : i ≠ s := by simpa only [← howner] using hij      rw [← howner]      exact htrim₁ i hi    · intro i    exact hown i  · intro g h hgh    simp [τ, τ₁, τ₀, hgh]
See it in the graphDiscuss this resultChallenge it