AFTD Auto-Formalizing Theoretical Domains

efx_source_two_envy_graph

theoremverified

The starting envy graph has exactly one edge, from agent 0 to agent 2, and thus three sources.

Statement

theorem efx_source_two_envy_graph (i j : Fin 4) (hij : i ≠ j) :
  (efx_partial_nat_utility efx_source_two_values efx_source_two_start i <
    ∑ g : Fin 9, if efx_source_two_start g = j.castSucc then efx_source_two_values i g else 0) ↔
  (i = 0 ∧ j = 2)
Source
Nine-good isolated-source completion obstruction; experiments 11561–11562.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

The proof, explained

The theorem is established by exhaustive case analysis over all pairs of distinct agents $(i, j)$ in $\{0, 1, 2, 3\}$. For each of the 16 cases, the partial utilities under the starting allocation are computed by unrolling the finite sums over all nine items. Arithmetic evaluation confirms that agent 0 envies agent 2 (489 < 513), while no other pair of distinct agents exhibits envy.

  1. The goal reduces to verifying the envy equivalence for each of the 16 specific agent pairs $(i, j) \in \{0, 1, 2, 3\}^2$.

    Because the agents are drawn from `Fin 4`, an exhaustive case split on $i$ and then on $j$ replaces the universal quantification with 16 concrete pairs.

    line 5

      fin_cases i <;> fin_cases j <;>
  2. For each pair of agents, agent $i$ envies agent $j$ if and only if $i = 0$ and $j = 2$. automation

    For each case, the definitions of the allocation `efx_source_two_start`, the valuation matrix `efx_source_two_values`, and `efx_partial_nat_utility` are unfolded, and the sums over the nine items are expanded by repeatedly applying `Fin.sum_univ_succ`. When $i = j$, the hypothesis $i \neq j$ is contradictory. For distinct pairs, direct arithmetic evaluation shows that agent 0 values their own bundle at 489 and agent 2's bundle at 513, so $489 < 513$ holds (matching $i = 0 \wedge j = 2$), while for all other distinct pairs the envy inequality evaluates to false.

    lines 6–7

    uses Fin.sum_univ_succ

        simp_all [efx_partial_nat_utility, efx_source_two_values, efx_source_two_start,
          Fin.sum_univ_succ]
Fin.sum_univ_succ
The sum of a function over `Fin (n + 1)` can be split into the term at index 0 and the sum over the remaining indices.

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_source_two_envy_graph (i j : Fin 4) (hij : i ≠ j) :  (efx_partial_nat_utility efx_source_two_values efx_source_two_start i <    ∑ g : Fin 9, if efx_source_two_start g = j.castSucc then efx_source_two_values i g else 0) ↔  (i = 0 ∧ j = 2) := by  fin_cases i <;> fin_cases j <;>    simp_all [efx_partial_nat_utility, efx_source_two_values, efx_source_two_start,      Fin.sum_univ_succ]
See it in the graphDiscuss this resultChallenge it