pmms_matroid_rank_mms_factor_two_agents
For two agents with matroid-rank valuations, every complete pairwise maximin-share fair allocation gives each agent at least 1/(2-1) = 1 of her maximin share: MMS_i(2, M) ≤ (2 - 1) * v_i(bundle_of σ i).
Statement
theorem pmms_matroid_rank_mms_factor_two_agents (m : ℕ) (v : Fin 2 → Finset (Fin m) → ℝ)
(hv : ∀ i, is_matroid_rank_valuation (v i))
(σ : Fin m → Fin 2) (hpmms : ∀ i, is_pmms_fair v σ i) (i : Fin 2) :
maximin_share (v i) 2 ≤ (2 - 1 : ℝ) * v i (bundle_of σ i)- Formalizes
- arXiv:2012.12710
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- is_matroid_rank_valuationA set function on a finite set of indivisible goods is a matroid-rank valuation if it evaluates the empty set to 0, is submodular, and has…
- is_pmms_fairAn allocation is pairwise-MMS-fair to agent i if, for every other agent j, i's bundle is worth to i at least i's two-agent maximin share…
- 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.
- pairwise_maximin_shareThe maximin share of a valuation when the items U are split into two bundles: the maximum over T inside U of min(v(T), v(U - T)).
Read back from the Lean
Given:
- a natural number m (the number of items),
- valuation functions v 0, v 1 : Finset (Fin m) → ℝ for two agents,
- a hypothesis hv that for both agents i : Fin 2, v i is a matroid rank valuation (normalized, submodular, with binary marginal gains),
- an allocation σ : Fin m → Fin 2,
- a hypothesis hpmms that the allocation σ is PMMS-fair (pairwise-maximin-share fair) for both agents, and
- an agent i : Fin 2:
The theorem asserts that the 2-agent maximin share of agent i's valuation v i is at most (2 - 1 : ℝ) * v i (bundle_of σ i) (which equals v i (bundle_of σ i)).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
For two agents, every complete allocation partitions the universe of items between them, so the pooled bundle of the two agents is the entire item set. Consequently, pairwise maximin-share (PMMS) fairness guarantees that each agent receives at least the pairwise maximin share of all items. Since any 2-partition of all items defines a valid bipartition, the standard 2-agent maximin share is bounded by the pairwise maximin share of the grand bundle, and scaling by the factor $2 - 1 = 1$ concludes the proof.
In any 2-partition $P$, agent 1's bundle is the complement of agent 0's bundle: $\text{bundle\_of } P\ 1 = \text{Finset.univ} \setminus \text{bundle\_of } P\ 0$.
By extensionality, an item $x$ belongs to $\text{bundle\_of } P\ 1$ if and only if $P(x) = 1$. Since the agents are in $\text{Fin } 2 = \{0, 1\}$, $P(x) = 1$ is equivalent to $P(x) \ne 0$, which is the condition for $x$ to be in the set difference $\text{Finset.univ} \setminus \text{bundle\_of } P\ 0$. Case analysis on $y = P(x) \in \{0, 1\}$ closes the equivalence.
uses
Finset.mem_filter,Finset.mem_sdiff,Finset.mem_univ,true_andext x simp only [bundle_of, Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, true_and] generalize hy : P x = y fin_cases y <;> simp
In a complete 2-agent allocation $\sigma$, the union of the bundles of two distinct agents $i \ne j$ is the full set of items $\text{Finset.univ}$.
By extensionality, an item $x$ is in $\text{bundle\_of } \sigma\ i \cup \text{bundle\_of } \sigma\ j$ if and only if $\sigma(x) = i$ or $\sigma(x) = j$. Since $i, j \in \text{Fin } 2$ with $j \ne i$, the set $\{i, j\}$ is the entire agent set $\{0, 1\}$ (ruling out $i = j$ by contradiction). Exhausting the values of $i$, $j$, and $\sigma(x) \in \{0, 1\}$ shows that $\sigma(x)$ always equals $i$ or $j$.
uses
Finset.mem_union,Finset.mem_filter,Finset.mem_univ,true_andext x simp only [Finset.mem_union, bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] fin_cases i <;> fin_cases j · contradiction · generalize hy : σ x = y; fin_cases y <;> simp · generalize hy : σ x = y; fin_cases y <;> simp · contradiction
To show $\text{maximin\_share } u\ 2 \le \text{pairwise\_maximin\_share } u\ \text{Finset.univ}$, it suffices to show that for every 2-partition $P$, the infimum of bundle values under $P$ is at most $\text{pairwise\_maximin\_share } u\ \text{Finset.univ}$.
Unfolding the definition of the 2-agent maximin share as the supremum over all 2-partitions $P$ of the infimum bundle value, the universal property of the supremum (`ciSup_le`) reduces the claim to verifying the bound for an arbitrary fixed partition $P$.
uses
ciSup_ledsimp [maximin_share] apply ciSup_le intro P dsimp [pairwise_maximin_share]
For any 2-partition $P$, the value $\min(u(\text{bundle\_of } P\ 0), u(\text{Finset.univ} \setminus \text{bundle\_of } P\ 0))$ is at most $\text{pairwise\_maximin\_share } u\ \text{Finset.univ}$.
Setting $T = \text{bundle\_of } P\ 0 \subseteq \text{Finset.univ}$, the pair $(T, \text{Finset.univ} \setminus T)$ is a candidate partition in the definition of the pairwise maximin share. Since the domain is finite, the range of such values is finite and thus bounded above (`Set.finite_range`), so the value at $T$ is bounded above by the supremum (`le_ciSup`).
uses
Finset.subset_univ,Set.finite_range,le_ciSuplet T : {T : Finset (Fin m) // T ≤ Finset.univ} := ⟨bundle_of P 0, Finset.subset_univ _⟩ have hbdd_sup : BddAbove (Set.range fun (T : {T : Finset (Fin m) // T ≤ Finset.univ}) => min (u T.1) (u (Finset.univ \ T.1))) := (Set.finite_range _).bddAbove have hT : min (u (bundle_of P 0)) (u (Finset.univ \ bundle_of P 0)) ≤ pairwise_maximin_share u Finset.univ := le_ciSup hbdd_sup T
The infimum of bundle values under $P$ is at most $\text{pairwise\_maximin\_share } u\ \text{Finset.univ}$, completing the proof of Lemma 3.
The infimum over $k \in \text{Fin } 2$ is at most $u(\text{bundle\_of } P\ 0)$ and at most $u(\text{bundle\_of } P\ 1)$, hence at most their minimum (`le_min`). By Lemma 1, $\text{bundle\_of } P\ 1 = \text{Finset.univ} \setminus \text{bundle\_of } P\ 0$, matching the expression bounded by the pairwise maximin share in the previous step. Transitivity (`le_trans`) completes the inequality for partition $P$.
uses
Set.finite_range,ciInf_le,le_min,pmms_matroid_rank_mms_factor_two_agents_bundle_of_one_eq_sdiff_zero,le_transhave hbdd_inf : BddBelow (Set.range fun k : Fin 2 => u (bundle_of P k)) := (Set.finite_range _).bddBelow have h0 : (⨅ k : Fin 2, u (bundle_of P k)) ≤ u (bundle_of P 0) := ciInf_le hbdd_inf 0 have h1 : (⨅ k : Fin 2, u (bundle_of P k)) ≤ u (bundle_of P 1) := ciInf_le hbdd_inf 1 have hmin : (⨅ k : Fin 2, u (bundle_of P k)) ≤ min (u (bundle_of P 0)) (u (bundle_of P 1)) := le_min h0 h1 rw [pmms_matroid_rank_mms_factor_two_agents_bundle_of_one_eq_sdiff_zero P] at hmin exact le_trans hmin hT
Given agent $i \in \text{Fin } 2$, there exists a distinct agent $j \ne i$ such that the union of their bundles is all items: $\text{bundle\_of } \sigma\ i \cup \text{bundle\_of } \sigma\ j = \text{Finset.univ}$.
The matroid-rank valuation hypothesis $hv$ is registered but not used. Case splitting on $i \in \text{Fin } 2$ yields a distinct partner $j \in \text{Fin } 2$ (if $i = 0$ choose $j = 1$; if $i = 1$ choose $j = 0$). By Lemma 2 (`pmms_matroid_rank_mms_factor_two_agents_bundle_of_union`), the union of the bundles of these two distinct agents is $\text{Finset.univ}$.
uses
pmms_matroid_rank_mms_factor_two_agents_bundle_of_unionhave _ := hv obtain ⟨j, hj⟩ : ∃ j : Fin 2, j ≠ i := by fin_cases i · exact ⟨1, by decide⟩ · exact ⟨0, by decide⟩ have h_union : bundle_of σ i ∪ bundle_of σ j = Finset.univ := pmms_matroid_rank_mms_factor_two_agents_bundle_of_union σ i j hj
Agent $i$'s bundle value is at least the pairwise maximin share of all items: $\text{pairwise\_maximin\_share}(v_i, \text{Finset.univ}) \le v_i(\text{bundle\_of } \sigma\ i)$.
By PMMS fairness against the other agent $j$, agent $i$'s bundle value is at least the pairwise maximin share of their pooled bundles, $\text{pairwise\_maximin\_share}(v_i, \text{bundle\_of } \sigma\ i \cup \text{bundle\_of } \sigma\ j)$. Rewriting this pooled set with the equality $\text{bundle\_of } \sigma\ i \cup \text{bundle\_of } \sigma\ j = \text{Finset.univ}$ established in the previous step yields the inequality.
have h_pmms_ij := hpmms i j hj rw [h_union] at h_pmms_ij
$\text{maximin\_share}(v_i, 2) \le (2 - 1) \cdot v_i(\text{bundle\_of } \sigma\ i)$.
By Lemma 3 (`pmms_matroid_rank_mms_factor_two_agents_mms_two_le_pairwise`), the 2-agent maximin share $\text{maximin\_share}(v_i, 2)$ is at most $\text{pairwise\_maximin\_share}(v_i, \text{Finset.univ})$. Chaining this with the PMMS lower bound via transitivity (`le_trans`) gives $\text{maximin\_share}(v_i, 2) \le v_i(\text{bundle\_of } \sigma\ i)$. Since $(2 - 1) = 1$ by ring arithmetic, this matches the required inequality.
uses
pmms_matroid_rank_mms_factor_two_agents_mms_two_le_pairwise,le_transhave h_mms_le := pmms_matroid_rank_mms_factor_two_agents_mms_two_le_pairwise m (v i) have h_le : maximin_share (v i) 2 ≤ v i (bundle_of σ i) := le_trans h_mms_le h_pmms_ij have h_factor : (2 - 1 : ℝ) * v i (bundle_of σ i) = v i (bundle_of σ i) := by ring rw [h_factor] exact h_le
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_sdiff- An element belongs to the set difference $s \setminus t$ if and only if it belongs to $s$ and does not belong to $t$.
Finset.mem_univ- In a finite type, every element belongs to the universal finset `Finset.univ`.
true_and- Conjunction with True simplifies to the proposition itself: $\text{True} \land p \iff p$.
Finset.mem_union- An element belongs to the union of two finsets if and only if it belongs to at least one of them.
ciSup_le- If every value in the range of a function is at most $c$, then the conditional supremum of the function is at most $c$.
Finset.subset_univ- Every finset of a finite type is a subset of the universal finset `Finset.univ`.
Set.finite_range- The range of any function defined on a finite domain is a finite set.
le_ciSup- If the range of a function is bounded above, then any value in the range is at most the conditional supremum.
ciInf_le- If the range of a function is bounded below, then the conditional infimum is at most any value in the range.
le_min- If $c \le a$ and $c \le b$, then $c \le \min(a, b)$.
pmms_matroid_rank_mms_factor_two_agents_bundle_of_one_eq_sdiff_zero- For any 2-partition of items, the bundle of agent 1 is the complement in the universal finset of the bundle of agent 0.
pmms_matroid_rank_mms_factor_two_agents_bundle_of_union- In a complete two-agent allocation, the union of the bundles of two distinct agents is the entire set of items.
pmms_matroid_rank_mms_factor_two_agents_mms_two_le_pairwise- For any valuation, the 2-agent maximin share is at most the pairwise maximin share evaluated on the grand bundle of all items.
le_trans- Transitivity of inequality: if $a \le b$ and $b \le c$, then $a \le c$.
- The hypothesis `hv : ∀ i, is_matroid_rank_valuation (v i)` (that valuations are matroid-rank valuations) is unused; line 43 (`have _ := hv`) discards it. The theorem holds for arbitrary valuations because in a two-agent allocation, the two bundles partition the universe of all items.
- In lines 44–47, the existence of the other agent $j \ne i$ in $\text{Fin } 2$ is resolved by exhaustive case analysis (`fin_cases i`), choosing $1$ when $i = 0$ and $0$ when $i = 1$, checked by `decide`.
- In Lemma 3 (lines 25–30), the boundedness conditions `BddAbove` and `BddBelow` required by `ciSup` and `ciInf` are justified by the finiteness of the set of bundles over a finite universe (`Set.finite_range`).
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.
lemma pmms_matroid_rank_mms_factor_two_agents_bundle_of_one_eq_sdiff_zero {m : ℕ} (P : Fin m → Fin 2) : bundle_of P 1 = Finset.univ \ bundle_of P 0 := by ext x simp only [bundle_of, Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, true_and] generalize hy : P x = y fin_cases y <;> simplemma pmms_matroid_rank_mms_factor_two_agents_bundle_of_union {m : ℕ} (σ : Fin m → Fin 2) (i j : Fin 2) (hij : j ≠ i) : bundle_of σ i ∪ bundle_of σ j = Finset.univ := by ext x simp only [Finset.mem_union, bundle_of, Finset.mem_filter, Finset.mem_univ, true_and] fin_cases i <;> fin_cases j · contradiction · generalize hy : σ x = y; fin_cases y <;> simp · generalize hy : σ x = y; fin_cases y <;> simp · contradictionlemma pmms_matroid_rank_mms_factor_two_agents_mms_two_le_pairwise (m : ℕ) (u : Finset (Fin m) → ℝ) : maximin_share u 2 ≤ pairwise_maximin_share u Finset.univ := by dsimp [maximin_share] apply ciSup_le intro P dsimp [pairwise_maximin_share] let T : {T : Finset (Fin m) // T ≤ Finset.univ} := ⟨bundle_of P 0, Finset.subset_univ _⟩ have hbdd_sup : BddAbove (Set.range fun (T : {T : Finset (Fin m) // T ≤ Finset.univ}) => min (u T.1) (u (Finset.univ \ T.1))) := (Set.finite_range _).bddAbove have hT : min (u (bundle_of P 0)) (u (Finset.univ \ bundle_of P 0)) ≤ pairwise_maximin_share u Finset.univ := le_ciSup hbdd_sup T have hbdd_inf : BddBelow (Set.range fun k : Fin 2 => u (bundle_of P k)) := (Set.finite_range _).bddBelow have h0 : (⨅ k : Fin 2, u (bundle_of P k)) ≤ u (bundle_of P 0) := ciInf_le hbdd_inf 0 have h1 : (⨅ k : Fin 2, u (bundle_of P k)) ≤ u (bundle_of P 1) := ciInf_le hbdd_inf 1 have hmin : (⨅ k : Fin 2, u (bundle_of P k)) ≤ min (u (bundle_of P 0)) (u (bundle_of P 1)) := le_min h0 h1 rw [pmms_matroid_rank_mms_factor_two_agents_bundle_of_one_eq_sdiff_zero P] at hmin exact le_trans hmin hT/-- Case n = 2 of OP-598: PMMS implies MMS for two agents with matroid-rank valuations. -/theorem pmms_matroid_rank_mms_factor_two_agents (m : ℕ) (v : Fin 2 → Finset (Fin m) → ℝ) (hv : ∀ i, is_matroid_rank_valuation (v i)) (σ : Fin m → Fin 2) (hpmms : ∀ i, is_pmms_fair v σ i) (i : Fin 2) : maximin_share (v i) 2 ≤ (2 - 1 : ℝ) * v i (bundle_of σ i) := by have _ := hv obtain ⟨j, hj⟩ : ∃ j : Fin 2, j ≠ i := by fin_cases i · exact ⟨1, by decide⟩ · exact ⟨0, by decide⟩ have h_union : bundle_of σ i ∪ bundle_of σ j = Finset.univ := pmms_matroid_rank_mms_factor_two_agents_bundle_of_union σ i j hj have h_pmms_ij := hpmms i j hj rw [h_union] at h_pmms_ij have h_mms_le := pmms_matroid_rank_mms_factor_two_agents_mms_two_le_pairwise m (v i) have h_le : maximin_share (v i) 2 ≤ v i (bundle_of σ i) := le_trans h_mms_le h_pmms_ij have h_factor : (2 - 1 : ℝ) * v i (bundle_of σ i) = v i (bundle_of σ i) := by ring rw [h_factor] exact h_le