allocation_is_envy_freeable_of_envy_free
An envy-free allocation is envy-freeable (with zero payments).
Statement
theorem allocation_is_envy_freeable_of_envy_free {N M : Type*} [Fintype M] [DecidableEq N] (v : N → Finset M → ℝ) (A : M → N) (h : ∀ i j, v i (allocation_bundle A j) ≤ v i (allocation_bundle A i)) : allocation_is_envy_freeable v A
- Source
- Sanity lemma for envy-freeability, arXiv:2610.14994 (Best-of-both-worlds fair division via subsidies), Sec. 2.
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- allocation_is_envy_freeableAn allocation is envy-freeable if there are nonnegative payments p such that every agent i weakly prefers its own bundle plus payment to…
- allocation_bundleFor a complete allocation A of the goods M to the agents N (each good to one agent), the bundle of agent i is the set of goods A assigns…
The proof, explained
An envy-free allocation is shown to be envy-freeable by exhibiting the zero payment function as the witness. Each payment is non-negative by reflexivity of the order ($0 \le 0$), and adding zero to both sides simplifies the envy-freeable condition directly to the assumed envy-freeness of the allocation.
The allocation is envy-freeable, witnessed by the zero payment function.
By definition, an allocation is envy-freeable if there exists a non-negative payment function $p : N \to \mathbb{R}$ ensuring that for all agents $i$ and $j$, $v_i(A_j) + p_j \le v_i(A_i) + p_i$. We choose $p(i) = 0$ for all $i$. Non-negativity $0 \le 0$ holds immediately by reflexivity (`le_rfl`). For envy-freeness, substituting zero payments yields $v_i(A_j) + 0 \le v_i(A_i) + 0$, which simplifies to $v_i(A_j) \le v_i(A_i)$ and holds directly by the hypothesis $h$.
uses
le_rfl⟨fun _ => 0, fun _ => le_rfl, fun i j => by simpa using h i j⟩
le_rfl- In any preorder, every element is less than or equal to itself ($a \le a$).
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 allocation_is_envy_freeable_of_envy_free {N M : Type*} [Fintype M] [DecidableEq N] (v : N → Finset M → ℝ) (A : M → N) (h : ∀ i j, v i (allocation_bundle A j) ≤ v i (allocation_bundle A i)) : allocation_is_envy_freeable v A := ⟨fun _ => 0, fun _ => le_rfl, fun i j => by simpa using h i j⟩