AFTD Auto-Formalizing Theoretical Domains

efx_three_bonus_distinct_no_0_nat

theoremverified

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

Statement

theorem efx_three_bonus_distinct_no_0_nat (σ : Fin 7 → Fin 4) (h : σ 0 = 0) : ¬ 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

The theorem states that no feasible allocation in the specified natural valuation matrix can assign good 0 to agent 0. With good 0 fixed to agent 0, the remaining six goods have only 4^6 = 4096 possible agent assignments, a finite search space that the `decide` tactic exhaustively rules out by computation. The theorem then follows by expressing any allocation σ with σ(0) = 0 in explicit vector notation and applying this exhaustive non-feasibility result.

  1. No allocation assigning item 0 to agent 0 can be feasible. automation

    Unfolding the definition of `efx_three_bonus_distinct_feasible_nat` exposes the feasibility conditions: the first four items are assigned to distinct agents, the next three items are assigned to distinct agents, every agent receives a bundle with total value at least 38, and the allocation is envy-free up to any good (EFX). Since the remaining six items each have 4 possible owners, there are 4^6 = 4096 configurations. The `decide` tactic evaluates the decidable predicate for all 4096 cases by computation, confirming that none satisfy all conditions.

    lines 4–6

      have key : ∀ a b c d e f : Fin 4, ¬ efx_three_bonus_distinct_feasible_nat ![0, a, b, c, d, e, f] := by
        unfold efx_three_bonus_distinct_feasible_nat
        decide
  2. The allocation σ is identical to the explicit vector ![0, σ 1, σ 2, σ 3, σ 4, σ 5, σ 6].

    By function extensionality (`funext`), two allocations are identical if they agree on each good i in Fin 7. A case split on the index i (`fin_cases`) produces seven cases. For item 0, the first vector entry is 0, which equals σ 0 by the assumption h. For items 1 through 6, the i-th vector entry evaluates definitionally to σ i.

    lines 7–9

      have hσ : σ = ![0, σ 1, σ 2, σ 3, σ 4, σ 5, σ 6] := by
        funext i
        fin_cases i <;> simp [h]
  3. σ is not feasible, completing the theorem.

    Rewriting σ using its vector representation reduces the goal to ¬ efx_three_bonus_distinct_feasible_nat ![0, σ 1, ..., σ 6]. This matches the key lemma instantiated with the owners a = σ 1, ..., f = σ 6.

    lines 10–11

      rw [hσ]
      exact key _ _ _ _ _ _

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_0_nat (σ : Fin 7 → Fin 4) (h : σ 0 = 0) : ¬ efx_three_bonus_distinct_feasible_nat σ := by  -- With item 0 fixed to agent 0, the remaining six owners form a finite space;  -- decide checks all 4^6 = 4096 cases against the feasible predicate.  have key : ∀ a b c d e f : Fin 4, ¬ efx_three_bonus_distinct_feasible_nat ![0, a, b, c, d, e, f] := by    unfold efx_three_bonus_distinct_feasible_nat    decide  have hσ : σ = ![0, σ 1, σ 2, σ 3, σ 4, σ 5, σ 6] := by    funext i    fin_cases i <;> simp [h]  rw [hσ]  exact key _ _ _ _ _ _
See it in the graphDiscuss this resultChallenge it