is_budget_feasible_empty
The empty allocation giving no items to any agent is budget-feasible whenever all agent budgets are nonnegative.
Statement
theorem is_budget_feasible_empty {m n : ℕ} (s : Fin m → ℝ) (B : Fin n → ℝ) (hB : ∀ i, 0 ≤ B i) : is_budget_feasible s B (fun _ => ∅)
- Source
- arXiv:2611.12740 Section 2
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_budget_feasibleAn allocation of m items to n agents is budget-feasible under item sizes s and agent budgets B if the allocated bundles are pairwise…
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Read back from the Lean
For any natural numbers $m$ and $n$, any valuation function $s : \text{Fin } m \to \mathbb{R}$, and any budget function $B : \text{Fin } n \to \mathbb{R}$, if $B(i) \ge 0$ for all $i \in \text{Fin } n$, then the allocation that assigns the empty set to every agent $i \in \text{Fin } n$ is budget-feasible with respect to valuations $s$ and budgets $B$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof unfolds the definition of budget feasibility into two obligations: pairwise disjointness of the allocated bundles and satisfaction of each agent's budget constraint. The disjointness condition is immediate because every agent is assigned the empty set. For the budget constraints, the additive valuation of the empty set evaluates to zero by `Finset.sum_empty`, which is at most each agent's budget by the assumption that all budgets are nonnegative.
Budget feasibility of the empty allocation reduces to pairwise disjointness of the bundles and budget satisfaction for each agent.
Unfolding the definition of budget feasibility (`is_budget_feasible`) requires verifying two conditions: that distinct agents receive disjoint bundles and that the valuation of each agent's bundle is at most their budget. We split these into two separate goals.
unfold is_budget_feasible constructor
The bundles assigned to distinct agents are pairwise disjoint.
For any distinct agents $i$ and $j$, both receive the empty set $\emptyset$. Since the empty set is disjoint from itself, this holds trivially.
· intro i j _ _; simp
Each agent's allocated bundle costs at most their budget.
Fix an agent $i$. Unfolding the definition of `additive_valuation` expresses the bundle's value as the sum $\sum_{j \in \emptyset} s(j)$. By `Finset.sum_empty`, this sum over the empty set is $0$, reducing the requirement to $0 \le B(i)$, which is given by the assumption that budgets are nonnegative (`hB`).
uses
Finset.sum_empty· intro i unfold additive_valuation simp only [Finset.sum_empty] exact hB i
Finset.sum_empty- The sum of any function over the empty finite set is zero.
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.
/-- The empty allocation is budget-feasible whenever budgets are nonnegative. -/theorem is_budget_feasible_empty {m n : ℕ} (s : Fin m → ℝ) (B : Fin n → ℝ) (hB : ∀ i, 0 ≤ B i) : is_budget_feasible s B (fun _ => ∅) := by unfold is_budget_feasible constructor · intro i j _ _; simp · intro i unfold additive_valuation simp only [Finset.sum_empty] exact hB i