mms_exists_monotone_two_three
Two agents with monotone valuations over three goods always have an MMS allocation.
Statement
theorem mms_exists_monotone_two_three : mms_exists_monotone 2 3- Related work
- small case of the threshold μ(n) of arXiv:2610.06125 (On MMS allocations with few items); the paper recalls that two agents and four goods can fail (Table 1)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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_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…
- 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
The proof reduces the existence of an MMS allocation to a combinatorial partition-covering property via `mms_exists_monotone_of_partition_cover`. That lemma requires that for any pair of partitions of the three goods into two bundles, there is an allocation that gives each agent a superset of one of their partition's bundles. Because the number of agents and items is small, this universal property over finite functions is verified exhaustively by computational reflection (`decide`), along with the arithmetic condition $1 \le 2$ verified by `norm_num`.
An MMS allocation exists for any two agents with monotone valuations over three goods. automation
The result is established by applying `mms_exists_monotone_of_partition_cover` with $n = 2$ agents and $m = 3$ items. This requires two hypotheses: the trivial inequality $1 \le 2$, verified by numerical normalization (`norm_num`), and a combinatorial partition-covering condition, which asserts that for every profile of two partitions of the three items into two parts, there exists an allocation where each agent receives a bundle containing at least one part of their partition. Because the space of partitions and allocations on two agents and three goods is finite, Lean evaluates this condition directly by exhaustive computation (`decide`).
uses
mms_exists_monotone_of_partition_covermms_exists_monotone_of_partition_cover 2 3 (by norm_num) (by decide)
mms_exists_monotone_of_partition_cover- If $1 \le n$ and every profile of partitions of $m$ items into $n$ bundles admits an allocation giving each agent a superset of at least one bundle from their partition, then an MMS allocation exists for any $n$ monotone valuations.
- The combinatorial covering condition is verified purely by computational reflection (`decide`), which exhaustively checks all 64 pairs of partitions of 3 goods into 2 bundles against the 8 possible allocations without producing human-readable deduction steps.
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_two_three : mms_exists_monotone 2 3 := mms_exists_monotone_of_partition_cover 2 3 (by norm_num) (by decide)