AFTD Auto-Formalizing Theoretical Domains

pmms_matroid_rank_mms_factor_two_agents

theoremverifiedformalization

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.

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

    lines 3–6

    uses Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, true_and

      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 <;> simp
  2. 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$.

    lines 10–16

    uses Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and

      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
      · contradiction
  3. 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$.

    lines 20–23

    uses ciSup_le

      dsimp [maximin_share]
      apply ciSup_le
      intro P
      dsimp [pairwise_maximin_share]
  4. 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`).

    lines 24–28

    uses Finset.subset_univ, Set.finite_range, le_ciSup

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

    lines 29–36

    uses Set.finite_range, ciInf_le, le_min, pmms_matroid_rank_mms_factor_two_agents_bundle_of_one_eq_sdiff_zero, le_trans

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

    lines 43–49

    uses pmms_matroid_rank_mms_factor_two_agents_bundle_of_union

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

    lines 50–51

      have h_pmms_ij := hpmms i j hj
      rw [h_union] at h_pmms_ij
  8. $\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.

    lines 52–56

    uses pmms_matroid_rank_mms_factor_two_agents_mms_two_le_pairwise, le_trans

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

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

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