is_non_wasteful_rule
Given finite types Agent and Object with decidable equality on Object, a rule f : (Agent -> LinearOrder Object) -> Agent -> Finset Object satisfies is_non_wasteful_rule if for every preference profile succ : Agent -> LinearOrder Object, the union over all agents of the finite bundles f succ a equals the universe of objects Finset.univ.
Statement
def is_non_wasteful_rule {Agent Object : Type*} [Fintype Agent] [Fintype Object] [DecidableEq Object] (f : (Agent → LinearOrder Object) → Agent → Finset Object) : Prop
- Defined in
- arXiv:2611.09685 Section 2.3
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Used by 1
- bundle_card_bounds_of_ef1_non_wastefulFor any allocation rule on n agents and k * n + r objects that is non-wasteful and EF1, every agent receives either k or k + 1 objects…
Read back from the Lean
For finite types Agent and Object (with decidable equality on Object), a rule f : (Agent → LinearOrder Object) → Agent → Finset Object satisfies is_non_wasteful_rule if and only if for every profile of linear orders succ : Agent → LinearOrder Object, the union of the allocated sets f succ a over all agents a : Agent equals the set of all objects (Finset.univ : Finset Object). That is, under every profile, every object is allocated to at least one agent.
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
/-- A rule is non-wasteful if all objects are allocated at every profile. -/ def is_non_wasteful_rule {Agent Object : Type*} [Fintype Agent] [Fintype Object] [DecidableEq Object] (f : (Agent → LinearOrder Object) → Agent → Finset Object) : Prop := ∀ succ, Finset.univ.biUnion (f succ) = Finset.univ