AFTD Auto-Formalizing Theoretical Domains

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