efx_source_two_envy_graph
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
- efx_source_two_valuesStrictly positive four-agent values for seven old goods and two unequal locks.
- efx_source_two_startThe initial old-good allocation, with both locks at agent 3 and good 6 unallocated.
- efx_partial_nat_utilityNatural utility in a partial allocation whose last owner label denotes unallocated goods.
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.
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.
fin_cases i <;> fin_cases j <;>
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.
uses
Fin.sum_univ_succsimp_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.
- The proof delegates the unrolling of the sums over the nine goods and the arithmetic evaluation of all 16 cases entirely to `simp_all`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]