mms_exists_monotone
def
Every instance with n agents and m goods, in which every agent has a monotone valuation v_i with v_i(∅) = 0, has an MMS allocation: an allocation A with v_i(A_i) ≥ MMS(M, v_i, n) for every agent i.
Statement
def mms_exists_monotone (n m : ℕ) : Prop
- Defined in
- arXiv:2610.06125 (On MMS allocations with few items), Sec. 1 (MMS allocations for monotone valuations over goods)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Built on 3
- maximin_shareThe maximin share of a valuation among n agents: the maximum, over partitions of the items into n bundles, of the value of the worst bundle.
- is_monotone_valuationA valuation is monotone and nonnegative: v(∅) ≥ 0 and S ⊆ T implies v(S) ≤ v(T).
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- Used by 5
- mms_exists_monotone_of_leWith n ≥ 1 agents and at most n goods, monotone valuations always admit an MMS allocation (give good j to agent j); so μ(n) ≥ n.
- mms_threshold_monotoneμ(n): the largest m such that every instance with n agents, at most m goods and monotone valuations has an MMS allocation.
- mms_exists_monotone_of_partition_coverReduction to MMS partitions: if for every choice of one partition P_i of the m goods into n bundles per agent there is an allocation in…
- mms_two_agents_four_goods_not_existsWith two agents, four goods and monotone valuations, an MMS allocation need not exist (both agents have MMS 2 in the Table 1 instance, but…
- mms_exists_monotone_two_threeTwo agents with monotone valuations over three goods always have an MMS allocation.
Lean source view module on GitHub
/-- MMS allocations always exist for `n` agents and `m` goods with monotone valuations: for every profile of monotone valuations with `v i ∅ = 0`, some allocation gives every agent at least her maximin share. -/ def mms_exists_monotone (n m : ℕ) : Prop := ∀ v : Fin n → Finset (Fin m) → ℝ, (∀ i, is_monotone_valuation (v i) ∧ v i ∅ = 0) → ∃ σ : Fin m → Fin n, ∀ i, maximin_share (v i) n ≤ v i (bundle_of σ i)