AFTD Auto-Formalizing Theoretical Domains

mms_two_agents_four_goods_not_exists

theoremverifiedformalization

With two agents, four goods and monotone valuations, an MMS allocation need not exist (both agents have MMS 2 in the Table 1 instance, but every allocation leaves one of them with value at most 1). Hence μ(2) ≤ 3.

Statement

theorem mms_two_agents_four_goods_not_exists : ¬ mms_exists_monotone 2 4
Formalizes
arXiv:2610.06125 (On MMS allocations with few items), Table 1 (a well-known example recalled in Sec. 1)
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • mms4_grid_valueTable 1 of arXiv:2610.06125: two agents, four goods in a 2 × 2 grid; nonempty bundles have value 1, except value 2 for bundles containing…
  • 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
  • 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

A counterexample showing MMS allocation does not always exist.

  1. Monotonicity of grid values

    Decide checks finite cases.

    lines 1–3

    theorem mms4_grid_value_mono : ∀ i S T, S ⊆ T → mms4_grid_value i S ≤ mms4_grid_value i T := by
      decide
    
  2. No good allocation

    Decide checks finite cases.

    lines 4–6

    theorem mms4_grid_no_good_allocation :
        ∀ σ : Fin 4 → Fin 2, ∃ i, mms4_grid_value i (bundle_of σ i) ≤ 1 := by decide
    
  3. Main theorem

    The main theorem.

    lines 7–24

    theorem mms_two_agents_four_goods_not_exists : ¬ mms_exists_monotone 2 4 := by
      intro h
      obtain ⟨σ, hσ⟩ := h (fun i S => (mms4_grid_value i S : ℝ)) (fun i =>
        ⟨⟨by positivity, fun S T hST => Nat.cast_le.2 (mms4_grid_value_mono i S T hST)⟩,
          by simp [mms4_grid_value]⟩)
      have hm : ∀ i, (2 : ℝ) ≤ maximin_share (fun S => (mms4_grid_value i S : ℝ)) 2 := by
        intro i
        unfold maximin_share
        refine le_ciSup_of_le (Set.finite_range _).bddAbove
          (if i = 0 then ![0, 0, 1, 1] else ![0, 1, 0, 1]) (le_ciInf fun j => ?_)
        have : ∀ i j : Fin 2, 2 ≤ mms4_grid_value i
            (bundle_of (if i = 0 then ![0, 0, 1, 1] else ![0, 1, 0, 1]) j) := by decide
        show (2 : ℝ) ≤ (mms4_grid_value i _ : ℝ)
        exact_mod_cast this i j
      obtain ⟨i, hi⟩ := mms4_grid_no_good_allocation σ
      have h1 : (2 : ℝ) ≤ (mms4_grid_value i (bundle_of σ i) : ℝ) := (hm i).trans (hσ i)
      have h2 : (mms4_grid_value i (bundle_of σ i) : ℝ) ≤ 1 := by exact_mod_cast hi
      linarith

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 mms4_grid_value_mono : ∀ i S T, S ⊆ T → mms4_grid_value i S ≤ mms4_grid_value i T := by  decidetheorem mms4_grid_no_good_allocation :    ∀ σ : Fin 4 → Fin 2, ∃ i, mms4_grid_value i (bundle_of σ i) ≤ 1 := by decidetheorem mms_two_agents_four_goods_not_exists : ¬ mms_exists_monotone 2 4 := by  intro h  obtain ⟨σ, hσ⟩ := h (fun i S => (mms4_grid_value i S : ℝ)) (fun i =>    ⟨⟨by positivity, fun S T hST => Nat.cast_le.2 (mms4_grid_value_mono i S T hST)⟩,      by simp [mms4_grid_value]⟩)  have hm : ∀ i, (2 : ℝ) ≤ maximin_share (fun S => (mms4_grid_value i S : ℝ)) 2 := by    intro i    unfold maximin_share    refine le_ciSup_of_le (Set.finite_range _).bddAbove      (if i = 0 then ![0, 0, 1, 1] else ![0, 1, 0, 1]) (le_ciInf fun j => ?_)    have : ∀ i j : Fin 2, 2 ≤ mms4_grid_value i        (bundle_of (if i = 0 then ![0, 0, 1, 1] else ![0, 1, 0, 1]) j) := by decide    show (2 : ℝ) ≤ (mms4_grid_value i _ : ℝ)    exact_mod_cast this i j  obtain ⟨i, hi⟩ := mms4_grid_no_good_allocation σ  have h1 : (2 : ℝ) ≤ (mms4_grid_value i (bundle_of σ i) : ℝ) := (hm i).trans (hσ i)  have h2 : (mms4_grid_value i (bundle_of σ i) : ℝ) ≤ 1 := by exact_mod_cast hi  linarith
See it in the graphDiscuss this resultChallenge it