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.
Monotonicity of grid values
Decide checks finite cases.
theorem mms4_grid_value_mono : ∀ i S T, S ⊆ T → mms4_grid_value i S ≤ mms4_grid_value i T := by decide
No good allocation
Decide checks finite cases.
theorem mms4_grid_no_good_allocation : ∀ σ : Fin 4 → Fin 2, ∃ i, mms4_grid_value i (bundle_of σ i) ≤ 1 := by decide
Main theorem
The main theorem.
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
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 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