AFTD Auto-Formalizing Theoretical Domains

mms_exists_monotone_two_three

theoremverifiedoriginal

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

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

    line 2

    uses mms_exists_monotone_of_partition_cover

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

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_exists_monotone_two_three : mms_exists_monotone 2 3 :=  mms_exists_monotone_of_partition_cover 2 3 (by norm_num) (by decide)
See it in the graphDiscuss this resultChallenge it