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 instance with four goods has none.
Statement
theorem mms_threshold_monotone_two : mms_threshold_monotone 2 = 3- Related work
- exact value of the threshold μ(n) of arXiv:2610.06125 (On MMS allocations with few items) at n = 2 (the paper studies the asymptotics; for additive valuations μ(2) is unbounded by cut and choose)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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_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_exists_monotone_two_threeTwo agents with monotone valuations over three goods always have an MMS allocation.
- 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…
The proof, explained
The threshold μ(2) is defined as the supremum of all m such that MMS allocations exist for 2 agents and any number of goods m' ≤ m. The proof shows that 3 is the greatest element of this set, which implies the supremum is 3. First, every m' ≤ 3 admits an allocation, either by the general result for at most as many goods as agents (when m' ≤ 2) or by the specific existence theorem for 2 agents and 3 goods. Second, 3 is an upper bound because any m ≥ 4 would require an allocation for 4 goods, contradicting the known counterexample with 2 agents and 4 goods.
To prove mms_threshold_monotone 2 = 3, it suffices to show that 3 is the greatest element of the set {m | ∀ m' ≤ m, mms_exists_monotone 2 m'}.
The threshold is defined as the supremum of the set of numbers of goods m for which MMS allocations exist for all m' ≤ m. By IsGreatest.csSup_eq, the supremum of a set equals any greatest element of that set. The proof then splits the definition of greatest element into two obligations: verifying that 3 belongs to the set, and showing that every element m in the set satisfies m ≤ 3.
uses
IsGreatest.csSup_eqapply IsGreatest.csSup_eq refine ⟨fun m' hm' => ?_, fun m hm => ?_⟩
For every m' ≤ 3, an MMS allocation exists for 2 agents and m' goods (so 3 belongs to the set).
By Nat.lt_or_ge, either m' < 3 or m' ≥ 3. If m' < 3, then m' ≤ 2; since the number of goods is at most the number of agents (1 ≤ 2 and m' ≤ 2), mms_exists_monotone_of_le guarantees the existence of an MMS allocation. If m' ≥ 3, then m' = 3 because m' ≤ 3 as well, and mms_exists_monotone_two_three directly supplies the existence of an allocation.
uses
Nat.lt_or_ge,mms_exists_monotone_of_le,mms_exists_monotone_two_three· rcases Nat.lt_or_ge m' 3 with h | h · exact mms_exists_monotone_of_le 2 m' (by norm_num) (by omega) · obtain rfl : m' = 3 := by omega exact mms_exists_monotone_two_three
Every element m of the set satisfies m ≤ 3 (so 3 is an upper bound).
Assume for contradiction that m > 3, which implies 4 ≤ m. By the assumption that m belongs to the set, an MMS allocation must exist for any number of goods up to m, and in particular for 4 goods. However, mms_two_agents_four_goods_not_exists states that no MMS allocation exists for 2 agents and 4 goods under monotone valuations, producing a contradiction.
uses
mms_two_agents_four_goods_not_exists· by_contra h exact mms_two_agents_four_goods_not_exists (hm 4 (by omega))
IsGreatest.csSup_eq- If an element a is the greatest element of a set s in a conditionally complete lattice, then the supremum of s equals a.
Nat.lt_or_ge- For any natural numbers n and m, either n < m or n ≥ m.
mms_exists_monotone_of_le- For any n ≥ 1, if the number of goods m is at most the number of agents n, then an MMS allocation always exists under monotone valuations.
mms_exists_monotone_two_three- An MMS allocation always exists for 2 agents and 3 goods under monotone valuations.
mms_two_agents_four_goods_not_exists- An MMS allocation does not always exist for 2 agents and 4 goods under monotone valuations.
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_threshold_monotone_two : mms_threshold_monotone 2 = 3 := by apply IsGreatest.csSup_eq refine ⟨fun m' hm' => ?_, fun m hm => ?_⟩ · rcases Nat.lt_or_ge m' 3 with h | h · exact mms_exists_monotone_of_le 2 m' (by norm_num) (by omega) · obtain rfl : m' = 3 := by omega exact mms_exists_monotone_two_three · by_contra h exact mms_two_agents_four_goods_not_exists (hm 4 (by omega))