mms_exists_monotone_of_le
With n ≥ 1 agents and at most n goods, monotone valuations always admit an MMS allocation (give good j to agent j); so μ(n) ≥ n.
Statement
theorem mms_exists_monotone_of_le (n m : ℕ) (hn : 1 ≤ n) (hmn : m ≤ n) :
mms_exists_monotone n m- Formalizes
- arXiv:2610.06125 (On MMS allocations with few items), Sec. 1 (remark that μ(n) ≥ n); proof via a pigeonhole argument on the MMS partition rather than the paper's one-line remark
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- mms_exists_monotoneEvery 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…
- 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.
- 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 1
- mms_threshold_monotone_twoμ(2) = 3 for monotone valuations over goods: every instance with two agents and at most three goods has an MMS allocation, and some…
The proof, explained
We propose the allocation assigning good j to agent j for each j < m, which is well-defined since m ≤ n. To show that any agent i receives at least their maximin share, it suffices to show that under every partition P, some agent receives a bundle contained in agent i's assigned bundle. If no such agent existed, every bundle under P would be nonempty, making P a surjective map from m goods to n agents and forcing m = n; surjectivity then implies P is a bijection, so the agent receiving good i gets only {i}, which is contained in agent i's bundle, contradiction. By monotonicity of valuations, agent i's value is at least the value of this smaller bundle, which upper-bounds the minimum share of P.
Propose the candidate allocation assigning good j to agent j for all j < m.
Given n agents and m ≤ n goods with 1 ≤ n, and monotone valuation functions vᵢ with vᵢ(∅) = 0, we define the candidate allocation σ : Fin m → Fin n via the canonical embedding Fin.castLE hmn (giving good j to agent j). We then fix an arbitrary agent i and aim to show that agent i receives at least their maximin share.
uses
Fin.castLEintro v hv refine ⟨Fin.castLE hmn, fun i => ?_⟩
It suffices to show that for every partition P, the minimum bundle value is at most vᵢ(bundle_of σ i).
Using 1 ≤ n, the agent set Fin n and the space of partitions Fin m → Fin n are shown to be nonempty. Unfolding the definition maximin_share(vᵢ, n) = ⨆ P, ⨅ k, vᵢ(bundle_of P k), we apply ciSup_le to reduce the goal to showing that for an arbitrary partition P, the infimum ⨅ k, vᵢ(bundle_of P k) is at most vᵢ(bundle_of σ i).
uses
ciSup_lehave : Nonempty (Fin m → Fin n) := ⟨fun _ => ⟨0, hn⟩⟩ have : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩ unfold maximin_share refine ciSup_le fun P => ?_
Under the assumption that no bundle of P is contained in agent i's bundle under σ, the partition P is surjective.
To show that some agent receives a bundle under P that is a subset of agent i's bundle under σ, we proceed by contradiction and assume that no bundle of P is a subset of bundle_of σ i. If any agent k were not in the image of P, their bundle under P would be empty; since the empty set is a subset of any set, this contradicts the assumption. Hence P : Fin m → Fin n must be surjective.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave hk : ∃ k, bundle_of P k ⊆ bundle_of (Fin.castLE hmn) i := by by_contra hno push Not at hno have hsurj : Function.Surjective P := by intro k by_contra hk push Not at hk apply hno k intro x hx simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at hx exact absurd hx (hk x)
The number of goods equals the number of agents (m = n) and P is injective.
Since P is surjective, the cardinality of the codomain is at most that of the domain (Fintype.card_le_of_surjective), giving n ≤ m via Fintype.card_fin. Combined with the hypothesis m ≤ n, this forces m = n. A surjective function between finite types of equal cardinality is bijective (Fintype.bijective_iff_surjective_and_card), so P is in particular injective.
uses
Fintype.card_le_of_surjective,Fintype.card_fin,Fintype.bijective_iff_surjective_and_cardhave hcard := Fintype.card_le_of_surjective P hsurj simp only [Fintype.card_fin] at hcard have hinj : Function.Injective P := ((Fintype.bijective_iff_surjective_and_card P).2 ⟨hsurj, by simp; omega⟩).1
There exists an agent k whose bundle under P is a subset of agent i's bundle under σ.
Because m = n, agent index i is also a valid good index in Fin m. Let k = P(i) be the agent receiving good i under P. Since P is injective, any good x assigned to k must satisfy P(x) = P(i), so x = i. Thus bundle_of P k = {i}. Under σ, good i is assigned to agent i, so {i} ⊆ bundle_of σ i. This contradicts the assumption that no bundle of P is contained in bundle_of σ i, concluding the proof of the existence of such a k.
uses
Fin.castLE,Finset.mem_filter,Finset.mem_univ,true_andapply hno (P ⟨i, by omega⟩) intro x hx simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢ have := hinj hx subst this ext; simp
Agent i's valuation for their assigned bundle is at least their maximin share.
With k such that bundle_of P k ⊆ bundle_of σ i in hand, we bound the infimum ⨅ j, vᵢ(bundle_of P j) from above by vᵢ(bundle_of P k) using ciInf_le (which applies because the range of values on a finite domain is finite by Set.finite_range, hence bounded below). By monotonicity of vᵢ, vᵢ(bundle_of P k) ≤ vᵢ(bundle_of σ i). This shows that the minimum bundle value under P is at most agent i's value under σ, closing the goal.
uses
ciInf_le,Set.finite_rangeobtain ⟨k, hk⟩ := hk exact (ciInf_le (Set.finite_range _).bddBelow k).trans ((hv i).1.2 _ _ hk)
Fin.castLE- Given m ≤ n, embeds the finite type Fin m into Fin n by preserving the underlying natural number index.
ciSup_le- In a conditionally complete lattice with a nonempty index type, if f(x) ≤ c for all x, then ⨆ x, f(x) ≤ c.
Finset.mem_filter- An element belongs to the filtered subfinset if and only if it belongs to the ambient finset and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
true_and- The proposition True ∧ p simplifies to p.
Fintype.card_le_of_surjective- If there is a surjective function between finite types, the cardinality of the codomain is at most the cardinality of the domain.
Fintype.card_fin- The cardinality of the type Fin k is k.
Fintype.bijective_iff_surjective_and_card- A map between finite types of the same cardinality is bijective if and only if it is surjective.
ciInf_le- In a conditionally complete lattice, if the range of f is bounded below, then ⨅ x, f(x) ≤ f(c) for any index c.
Set.finite_range- The range of a function defined on a finite domain is a finite set.
- Lines 5–6 prove that the agent type Fin n and the partition space Fin m → Fin n are nonempty using the hypothesis 1 ≤ n; this is a formal prerequisite for applying ciSup_le in the conditionally complete lattice ℝ.
- The embedding Fin.castLE hmn explicitly casts each good j < m to agent j < n, formalizing the allocation that gives good j to agent j.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem mms_exists_monotone_of_le (n m : ℕ) (hn : 1 ≤ n) (hmn : m ≤ n) : mms_exists_monotone n m := by intro v hv refine ⟨Fin.castLE hmn, fun i => ?_⟩ have : Nonempty (Fin m → Fin n) := ⟨fun _ => ⟨0, hn⟩⟩ have : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩ unfold maximin_share refine ciSup_le fun P => ?_ have hk : ∃ k, bundle_of P k ⊆ bundle_of (Fin.castLE hmn) i := by by_contra hno push Not at hno have hsurj : Function.Surjective P := by intro k by_contra hk push Not at hk apply hno k intro x hx simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at hx exact absurd hx (hk x) have hcard := Fintype.card_le_of_surjective P hsurj simp only [Fintype.card_fin] at hcard have hinj : Function.Injective P := ((Fintype.bijective_iff_surjective_and_card P).2 ⟨hsurj, by simp; omega⟩).1 apply hno (P ⟨i, by omega⟩) intro x hx simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] at hx ⊢ have := hinj hx subst this ext; simp obtain ⟨k, hk⟩ := hk exact (ciInf_le (Set.finite_range _).bddBelow k).trans ((hv i).1.2 _ _ hk)