AFTD Auto-Formalizing Theoretical Domains

mms_exists_monotone_of_le

theoremverifiedformalization

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.

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

    lines 3–4

    uses Fin.castLE

      intro v hv
      refine ⟨Fin.castLE hmn, fun i => ?_⟩
  2. 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).

    lines 5–8

    uses ciSup_le

      have : Nonempty (Fin m → Fin n) := ⟨fun _ => ⟨0, hn⟩⟩
      have : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩
      unfold maximin_share
      refine ciSup_le fun P => ?_
  3. 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.

    lines 9–19

    uses Finset.mem_filter, Finset.mem_univ, true_and

      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)
  4. 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.

    lines 20–23

    uses Fintype.card_le_of_surjective, Fintype.card_fin, Fintype.bijective_iff_surjective_and_card

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

    lines 24–29

    uses Fin.castLE, Finset.mem_filter, Finset.mem_univ, true_and

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

    lines 30–31

    uses ciInf_le, Set.finite_range

      obtain ⟨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.

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