is_budget_feasible
def
An allocation of m items to n agents is budget-feasible under item sizes s and agent budgets B if the allocated bundles are pairwise disjoint and each agent i's bundle has total size at most B_i.
Statement
def is_budget_feasible {m n : ℕ} (s : Fin m → ℝ) (B : Fin n → ℝ) (X : Fin n → Finset (Fin m)) : Prop
- Defined in
- arXiv:2611.12740 Section 2
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 1
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- Used by 1
- is_budget_feasible_emptyThe empty allocation giving no items to any agent is budget-feasible whenever all agent budgets are nonnegative.
Read back from the Lean
For natural numbers m and n, a function s : Fin m → ℝ, a function B : Fin n → ℝ, and an allocation X : Fin n → Finset (Fin m), is_budget_feasible s B X asserts that:
1. For all distinct i, j : Fin n (i.e., i ≠ j), the sets X i and X j are disjoint; and
2. For every i : Fin n, the additive valuation additive_valuation s (X i) is at most B i.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- An allocation of m items to n agents is budget-feasible under item sizes s and budgets B. -/ def is_budget_feasible {m n : ℕ} (s : Fin m → ℝ) (B : Fin n → ℝ) (X : Fin n → Finset (Fin m)) : Prop := (Pairwise fun i j => Disjoint (X i) (X j)) ∧ ∀ i : Fin n, additive_valuation s (X i) ≤ B i