AFTD Auto-Formalizing Theoretical Domains

efx_three_bonus_distinct_no_2_nat

theoremverified

No feasible allocation in the specified natural matrix gives old good 0 to agent 2.

Statement

theorem efx_three_bonus_distinct_no_2_nat (σ : Fin 7 → Fin 4) (h : σ 0 = 2) : ¬ efx_three_bonus_distinct_feasible_nat σ
Source
Finite obstruction to the distinct-recipient exchange route for OP-7, experiments 11403, 11405 and 11406.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • efx_three_bonus_distinct_feasible_natA seven-good allocation gives the four old goods to distinct agents and the three bonuses to distinct agents, gives each agent natural…
  • efx_three_bonus_distinct_valuesThe natural-valued four-agent, seven-good matrix whose rows are (38,36,58,56,1,1,17), (18,38,54,36,1,1,17), (18,38,38,36,17,1,1), and…
Used by 1
  • efx_three_bonus_distinct_no_natNo assignment in the explicit matrix simultaneously keeps old and bonus recipients respectively distinct, satisfies EFX, and preserves…

The proof, explained

We argue by contradiction, assuming that σ is a feasible allocation that assigns old good 0 to agent 2. Because feasibility requires all four old goods to be assigned to pairwise distinct agents, agent 2 cannot receive any of goods 1, 2, or 3. Agent 2 therefore receives value 18 from good 0, nothing from goods 1, 2, 3, and at most 17 + 1 + 1 from the three bonus goods, for a maximum total utility of 37. This contradicts the feasibility requirement that every agent must receive a total utility of at least 38.

  1. Assume for contradiction that σ is feasible, and extract the feasibility conditions.

    We assume that σ is feasible (`hf`), seeking a contradiction. By definition, feasibility gives four conditions: old goods go to distinct agents (`h1`), bonus goods go to distinct agents (`h2`), each agent gets utility at least 38 (`h3`), and envy-freeness up to any good holds (`h4`).

    lines 2–3

      intro hf
      obtain ⟨h1, h2, h3, h4⟩ := hf
  2. Agent 2 does not receive old goods 1, 2, or 3.

    Condition `h1` requires any two distinct old goods to be assigned to distinct agents. Since good 0 is assigned to agent 2 (σ 0 = 2), applying `h1` to good 0 and each good g ∈ {1, 2, 3} gives σ 0 ≠ σ g. Substituting σ 0 = 2 and using symmetry of equality (`eq_comm`) establishes σ 1 ≠ 2, σ 2 ≠ 2, and σ 3 ≠ 2.

    lines 5–13

    uses eq_comm

      have h01 : σ 1 ≠ 2 := by
        have := h1 0 1 (by decide)
        simpa [h, eq_comm] using this
      have h02 : σ 2 ≠ 2 := by
        have := h1 0 2 (by decide)
        simpa [h, eq_comm] using this
      have h03 : σ 3 ≠ 2 := by
        have := h1 0 3 (by decide)
        simpa [h, eq_comm] using this
  3. Agent 2 receives utility 18 from good 0, and 0 from old goods 1, 2, and 3.

    Since σ 0 = 2, the conditional utility for good 0 evaluates by `if_pos` to agent 2's valuation of good 0, which is definitionally 18 (`e0`). For goods 1, 2, and 3, because agent 2 does not receive them (σ g ≠ 2), the conditional utility evaluates by `if_neg` to 0 (`e1`, `e2`, `e3`).

    lines 16–23

    uses if_pos, if_neg

      have e0 : (if σ 0 = 2 then efx_three_bonus_distinct_values 2 0 else 0) = 18 := by
        rw [if_pos h]; rfl
      have e1 : (if σ 1 = 2 then efx_three_bonus_distinct_values 2 1 else 0) = 0 := by
        rw [if_neg h01]
      have e2 : (if σ 2 = 2 then efx_three_bonus_distinct_values 2 2 else 0) = 0 := by
        rw [if_neg h02]
      have e3 : (if σ 3 = 2 then efx_three_bonus_distinct_values 2 3 else 0) = 0 := by
        rw [if_neg h03]
  4. Agent 2 receives at most 17 from bonus good 4, and at most 1 from each of bonus goods 5 and 6.

    For each bonus good g ∈ {4, 5, 6}, we split on whether agent 2 receives good g. If not, the utility is 0; if so, agent 2's valuation is 17 for good 4, and 1 for goods 5 and 6. In both cases, the utility is bounded by 17, 1, and 1 respectively.

    lines 24–29

      have e4 : (if σ 4 = 2 then efx_three_bonus_distinct_values 2 4 else 0) ≤ 17 := by
        split <;> simp [efx_three_bonus_distinct_values]
      have e5 : (if σ 5 = 2 then efx_three_bonus_distinct_values 2 5 else 0) ≤ 1 := by
        split <;> simp [efx_three_bonus_distinct_values]
      have e6 : (if σ 6 = 2 then efx_three_bonus_distinct_values 2 6 else 0) ≤ 1 := by
        split <;> simp [efx_three_bonus_distinct_values]
  5. Agent 2's total utility across all seven goods is at most 37.

    Expanding the sum over the seven goods via `Fin.sum_univ_seven` and substituting the utilities for the first four goods gives 18 + 0 + 0 + 0 plus the contributions of goods 4, 5, and 6. Since those bonus contributions are at most 17, 1, and 1, linear arithmetic (`omega`) bounds the total sum by 18 + 17 + 1 + 1 = 37.

    lines 30–32

    uses Fin.sum_univ_seven

      have hsum : (∑ g, if σ g = 2 then efx_three_bonus_distinct_values 2 g else 0) ≤ 37 := by
        rw [Fin.sum_univ_seven, e0, e1, e2, e3]
        omega
  6. A contradiction is reached with the feasibility lower bound of 38.

    Feasibility condition `h3` instantiated for agent 2 requires agent 2's total utility to be at least 38. This directly contradicts the established upper bound of 37, which linear arithmetic (`omega`) detects to conclude the proof.

    lines 33–34

      have := h3 2
      omega
eq_comm
Equality is symmetric: `a = b` is equivalent to `b = a`.
if_pos
If the condition `c` holds, the conditional expression `if c then t else e` reduces to `t`.
if_neg
If the condition `c` does not hold, the conditional expression `if c then t else e` reduces to `e`.
Fin.sum_univ_seven
A sum over the index type `Fin 7` unwinds into the explicit sum of the terms evaluated at 0, 1, 2, 3, 4, 5, and 6.

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

theorem efx_three_bonus_distinct_no_2_nat (σ : Fin 7 → Fin 4) (h : σ 0 = 2) : ¬ efx_three_bonus_distinct_feasible_nat σ := by  intro hf  obtain ⟨h1, h2, h3, h4⟩ := hf  -- old goods 1, 2, 3 do not go to agent 2, since old goods go to distinct agents  have h01 : σ 1 ≠ 2 := by    have := h1 0 1 (by decide)    simpa [h, eq_comm] using this  have h02 : σ 2 ≠ 2 := by    have := h1 0 2 (by decide)    simpa [h, eq_comm] using this  have h03 : σ 3 ≠ 2 := by    have := h1 0 3 (by decide)    simpa [h, eq_comm] using this  -- agent 2's utility: 18 from old good 0, nothing from old goods 1,2,3,  -- and at most 17 + 1 + 1 from the bonuses  have e0 : (if σ 0 = 2 then efx_three_bonus_distinct_values 2 0 else 0) = 18 := by    rw [if_pos h]; rfl  have e1 : (if σ 1 = 2 then efx_three_bonus_distinct_values 2 1 else 0) = 0 := by    rw [if_neg h01]  have e2 : (if σ 2 = 2 then efx_three_bonus_distinct_values 2 2 else 0) = 0 := by    rw [if_neg h02]  have e3 : (if σ 3 = 2 then efx_three_bonus_distinct_values 2 3 else 0) = 0 := by    rw [if_neg h03]  have e4 : (if σ 4 = 2 then efx_three_bonus_distinct_values 2 4 else 0) ≤ 17 := by    split <;> simp [efx_three_bonus_distinct_values]  have e5 : (if σ 5 = 2 then efx_three_bonus_distinct_values 2 5 else 0) ≤ 1 := by    split <;> simp [efx_three_bonus_distinct_values]  have e6 : (if σ 6 = 2 then efx_three_bonus_distinct_values 2 6 else 0) ≤ 1 := by    split <;> simp [efx_three_bonus_distinct_values]  have hsum : (∑ g, if σ g = 2 then efx_three_bonus_distinct_values 2 g else 0) ≤ 37 := by    rw [Fin.sum_univ_seven, e0, e1, e2, e3]    omega  have := h3 2  omega
See it in the graphDiscuss this resultChallenge it