AFTD Auto-Formalizing Theoretical Domains

allocation_is_envy_freeable_of_envy_free

theoremverified

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.

  1. 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$.

    line 5

    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

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⟩
See it in the graphDiscuss this resultChallenge it