AFTD Auto-Formalizing Theoretical Domains

mms_threshold_monotone_two

theoremverifiedoriginal

μ(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.

  1. 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.

    lines 2–3

    uses IsGreatest.csSup_eq

      apply IsGreatest.csSup_eq
      refine ⟨fun m' hm' => ?_, fun m hm => ?_⟩
  2. 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.

    lines 4–7

    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
  3. 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.

    lines 8–9

    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

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