AFTD Auto-Formalizing Theoretical Domains

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