AFTD Auto-Formalizing Theoretical Domains

mms_exists_monotone_of_partition_cover

theoremverifiedformalization

Reduction 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 which every agent i receives a superset of some bundle of P_i, then MMS allocations exist for n agents and m goods with monotone valuations.

Statement

theorem mms_exists_monotone_of_partition_cover (n m : ℕ) (hn : 1 ≤ n)
    (h : ∀ P : Fin n → Fin m → Fin n, ∃ σ : Fin m → Fin n, ∀ i, ∃ k,
      bundle_of (P i) k ⊆ bundle_of σ i) : mms_exists_monotone n m
Formalizes
arXiv:2610.06125 (On MMS allocations with few items), Sec. 1 (an MMS allocation is one in which each agent gets a superset of a part of her MMS partition)
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…
  • 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.
  • 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.
Used by 1

The proof, explained

To prove that an MMS allocation exists under monotone valuations, we first select for each agent an optimal partition that attains their maximin share, which exists because the set of partitions into n bundles is finite and nonempty. We then apply the partition cover hypothesis to obtain an allocation in which each agent receives a superset of some bundle from their chosen partition. By monotonicity, each agent's valuation for their assigned bundle is at least the value of that subset bundle, which is at least their maximin share.

  1. Assume monotone, normalized valuations for all agents, and note that the set of agents and the set of partitions are nonempty.

    Unpack the definition of `mms_exists_monotone`, introducing the agent valuations v and the assumption hv that each valuation is monotone with v i ∅ = 0. Since n ≥ 1, index 0 is valid, which establishes that both the agent index type Fin n and the space of partitions Fin m → Fin n are nonempty.

    lines 4–6

      intro v hv
      have : Nonempty (Fin m → Fin n) := ⟨fun _ => ⟨0, hn⟩⟩
      have : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩
  2. For each agent i, choose an optimal partition achieving agent i's maximin share.

    The maximin share of agent i is defined as the supremum over all partitions P of the minimum bundle value ⨅ k, v i (bundle_of P k). Because the partition space Fin m → Fin n is finite and nonempty, this supremum is attained at some partition P_i by `exists_eq_ciSup_of_finite`. Using choice (`choose`), we select a family of partitions P such that every agent i achieves their maximin share at P i.

    lines 7–12

    uses exists_eq_ciSup_of_finite

      have hP : ∀ i, ∃ P : Fin m → Fin n, maximin_share (v i) n = ⨅ k, v i (bundle_of P k) := by
        intro i
        obtain ⟨P, hP⟩ := exists_eq_ciSup_of_finite
          (f := fun P : Fin m → Fin n => ⨅ k, v i (bundle_of P k))
        exact ⟨P, hP.symm⟩
      choose P hP using hP
  3. Obtain an allocation σ that covers at least one bundle from each agent's optimal partition.

    Apply the partition cover hypothesis h to the family of partitions P. This provides an allocation σ : Fin m → Fin n such that every agent i receives a bundle containing at least one bundle k of their partition P i.

    line 13

      obtain ⟨σ, hσ⟩ := h P
  4. The allocation σ guarantees every agent at least their maximin share.

    For each agent i, let k be the bundle index from the covering condition such that bundle_of (P i) k ⊆ bundle_of σ i. Agent i's maximin share equals ⨅ j, v i (bundle_of (P i) j), which is at most v i (bundle_of (P i) k) by `ciInf_le` (the range is finite by `Set.finite_range`, hence bounded below). Valuation monotonicity of v i then implies v i (bundle_of (P i) k) ≤ v i (bundle_of σ i). By transitivity, agent i receives at least their maximin share.

    lines 14–17

    uses ciInf_le, Set.finite_range

      refine ⟨σ, fun i => ?_⟩
      obtain ⟨k, hk⟩ := hσ i
      rw [hP i]
      exact (ciInf_le (Set.finite_range _).bddBelow k).trans ((hv i).1.2 _ _ hk)
exists_eq_ciSup_of_finite
A function from a nonempty, finite type into a conditionally complete linear order attains its supremum.
ciInf_le
In a conditionally complete lattice, the infimum of a function with range bounded below is at most the function's value at any given point.
Set.finite_range
The range of a function defined on a finite domain is finite.

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_partition_cover (n m : ℕ) (hn : 1 ≤ n)    (h : ∀ P : Fin n → Fin m → Fin n, ∃ σ : Fin m → Fin n, ∀ i, ∃ k,      bundle_of (P i) k ⊆ bundle_of σ i) : mms_exists_monotone n m := by  intro v hv  have : Nonempty (Fin m → Fin n) := ⟨fun _ => ⟨0, hn⟩⟩  have : Nonempty (Fin n) := ⟨⟨0, hn⟩⟩  have hP : ∀ i, ∃ P : Fin m → Fin n, maximin_share (v i) n = ⨅ k, v i (bundle_of P k) := by    intro i    obtain ⟨P, hP⟩ := exists_eq_ciSup_of_finite      (f := fun P : Fin m → Fin n => ⨅ k, v i (bundle_of P k))    exact ⟨P, hP.symm⟩  choose P hP using hP  obtain ⟨σ, hσ⟩ := h P  refine ⟨σ, fun i => ?_⟩  obtain ⟨k, hk⟩ := hσ i  rw [hP i]  exact (ciInf_le (Set.finite_range _).bddBelow k).trans ((hv i).1.2 _ _ hk)
See it in the graphDiscuss this resultChallenge it