AFTD Auto-Formalizing Theoretical Domains

two_agent_bivalued_equal_marginal_sharp_mms

theoremverifiedoriginal

For two agents (n = 2), ratio r with 1 ≤ r and r ≤ 2, and m chores with a cost profile c : Fin 2 → Fin m → ℝ satisfying is_scaled_bivalued_chores r c, there exists a lottery p ∈ stdSimplex ℝ (Fin m → Fin 2) such that is_equal_marginal_lottery p and is_ex_post_alpha_mms_chores ((r+1)/2) c p.

Statement

theorem two_agent_bivalued_equal_marginal_sharp_mms
    (r : ℝ) (hr1 : 1 ≤ r) (hr2 : r ≤ 2)
    (m : ℕ) (c : Fin 2 → Fin m → ℝ)
    (hc : is_scaled_bivalued_chores r c) :
    ∃ p ∈ stdSimplex ℝ (Fin m → Fin 2),
      is_equal_marginal_lottery p ∧
      is_ex_post_alpha_mms_chores ((r + 1) / 2) c p
Related work
Two-agent partial case of the proposed problem OP-1112. Related work: https://arxiv.org/abs/2609.35280, Sections 3.1 and 5.4, establishes the general equal-marginal 3/2 bound and its lower bound at cost ratio 2.
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • is_equal_marginal_lotteryA lottery p over complete allocations of m chores to n agents has equal marginals if every chore g is assigned to every agent i with…
  • is_scaled_bivalued_choresGiven ratio r : ℝ and a chore cost profile c : Fin n → Fin m → ℝ over n agents and m chores, c is scaled bivalued with ratio r if there…
  • is_ex_post_alpha_mms_choresAn allocation lottery p over allocations of m chores among n agents is ex-post α-MMS for chore costs c if every allocation σ in the…
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • chore_maximin_shareThe maximin share (MMS) of an agent with additive chore costs u among n agents: the infimum over all partitions P : Fin m → Fin n of the…
  • 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.
Used by 1

Read back from the Lean

For any real number $r$ satisfying $1 \le r \le 2$, any natural number $m$ (representing $m$ chores), and any chore cost function $c : \mathrm{Fin}\ 2 \to \mathrm{Fin}\ m \to \mathbb{R}$ such that $c$ is scaled bivalued with ratio $r$ (that is, for each agent $i \in \mathrm{Fin}\ 2$, there exists $a_i > 0$ such that for every chore $g$, $c(i, g) = a_i$ or $c(i, g) = r \cdot a_i$): There exists a probability distribution (lottery) $p \in \mathrm{stdSimplex}\ \mathbb{R}\ (\mathrm{Fin}\ m \to \mathrm{Fin}\ 2)$ over chore allocations such that: 1. $p$ has equal marginals: for every chore $g \in \mathrm{Fin}\ m$ and each agent $i \in \mathrm{Fin}\ 2$, the marginal probability that $g$ is allocated to $i$, $\sum_{\sigma : \mathrm{Fin}\ m \to \mathrm{Fin}\ 2,\ \sigma(g) = i} p(\sigma)$, equals $1/2$. 2. $p$ is ex-post $\frac{r+1}{2}$-MMS for chores: for every allocation $\sigma$ with $p(\sigma) > 0$ and each agent $i \in \mathrm{Fin}\ 2$, the cost assigned to $i$, $\sum_{g \in \mathrm{Fin}\ m,\ \sigma(g) = i} c(i, g)$, is at most $\frac{r + 1}{2}$ times agent $i$'s 2-agent chore maximin share, $\inf_{P : \mathrm{Fin}\ m \to \mathrm{Fin}\ 2} \sup_{k \in \mathrm{Fin}\ 2} \sum_{g \in \mathrm{Fin}\ m,\ P(g) = k} c(i, g)$.

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

To guarantee ex-post ((r+1)/2)-MMS for two agents with bivalued chore costs in ratio r ∈ [1, 2] under equal marginals, the proof constructs a balanced 2-partition (S, Sᶜ) of the m chores. By partitioning the chore set into four regions according to which agents consider each chore high-cost, a combinatorial lemma finds a subset S that simultaneously balances total chore count and each agent's high-cost chores to within ceiling halves. Arithmetic and MMS lower bounds show that any such balanced bundle costs at most ((r+1)/2) times the agent's chore MMS. Finally, the 50-50 swap lottery between allocations (S, Sᶜ) and (Sᶜ, S) assigns each chore to each agent with probability 1/2 and guarantees ex-post ((r+1)/2)-MMS.

  1. For k ≥ 1 and d ≥ 0, k + d ⌈(h+1)/2⌉ ≤ (1 + d/2)(k + dh/2).

    By integer arithmetic, 2⌈(h+1)/2⌉ ≤ h + 1, so k + h - 2⌈(h+1)/2⌉ ≥ 0 when k ≥ 1. Multiplying by d ≥ 0 and adding d²h ≥ 0, algebraic expansion shows the inequality holds.

    lines 4–11

    uses mul_nonneg

      have hc : 2 * ((h + 1) / 2) ≤ h + 1 := by omega
      have hcr : (2 : ℝ) * (((h + 1) / 2 : ℕ) : ℝ) ≤ (h : ℝ) + 1 := by
        exact_mod_cast hc
      have hkr : (1 : ℝ) ≤ k := by exact_mod_cast hk
      have harr : 0 ≤ (k : ℝ) + (h : ℝ) - 2 * (((h + 1) / 2 : ℕ) : ℝ) := by linarith
      have hmul := mul_nonneg hd harr
      have hsq : 0 ≤ d * d * (h : ℝ) := by positivity
      nlinarith
  2. For d ≥ 0, (k+1) + d ⌈(h+1)/2⌉ ≤ (1 + d/2)((k+1) + d(h-k)).

    Integer arithmetic gives 2⌈(h+1)/2⌉ ≤ (k+1) + 2(h-k), which yields a nonnegative term (k+1) + 2(h-k) - 2⌈(h+1)/2⌉ ≥ 0. Multiplying by d ≥ 0 and noting d²(h-k) ≥ 0, non-linear arithmetic confirms the inequality.

    lines 16–24

    uses mul_nonneg

      have hc : 2 * ((h + 1) / 2) ≤ k + 1 + 2 * (h - k) := by omega
      have hcr : (2 : ℝ) * (((h + 1) / 2 : ℕ) : ℝ) ≤
          (k : ℝ) + 1 + 2 * ((h - k : ℕ) : ℝ) := by
        exact_mod_cast hc
      have harr : 0 ≤ (k : ℝ) + 1 + 2 * ((h - k : ℕ) : ℝ) -
          2 * (((h + 1) / 2 : ℕ) : ℝ) := by linarith
      have hmul := mul_nonneg hd harr
      have hsq : 0 ≤ d * d * ((h - k : ℕ) : ℝ) := by positivity
      nlinarith
  3. For any four nonnegative integers a, b, c, d, there exist sub-counts w ≤ a, x ≤ b, y ≤ c, z ≤ d that balance all totals and pair sums to within ceiling halves.

    We split into 16 cases based on the parities of a, b, c, and d modulo 2. In each case, choosing each sub-count to be either the floor or ceiling half of the corresponding total satisfies all ten linear bounds by Presburger arithmetic.

    lines 34–56

    uses Nat.mod_lt

      have ha : a % 2 < 2 := Nat.mod_lt _ (by omega)
      have hb : b % 2 < 2 := Nat.mod_lt _ (by omega)
      have hc : c % 2 < 2 := Nat.mod_lt _ (by omega)
      have hd : d % 2 < 2 := Nat.mod_lt _ (by omega)
      interval_cases hma : a % 2 <;> interval_cases hmb : b % 2 <;>
        interval_cases hmc : c % 2 <;> interval_cases hmd : d % 2 <;>
        first
        | refine ⟨a / 2, b / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨a / 2, b / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨a / 2, b / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨a / 2, b / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨a / 2, (b + 1) / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨a / 2, (b + 1) / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨a / 2, (b + 1) / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨a / 2, (b + 1) / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨(a + 1) / 2, b / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨(a + 1) / 2, b / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨(a + 1) / 2, b / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨(a + 1) / 2, b / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨(a + 1) / 2, (b + 1) / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨(a + 1) / 2, (b + 1) / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨(a + 1) / 2, (b + 1) / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
        | refine ⟨(a + 1) / 2, (b + 1) / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega
  4. The universe of m chores is partitioned into four pairwise disjoint regions R₀ = Aᶜ \ B, R₁ = Aᶜ ∩ B, R₂ = A \ B, and R₃ = A ∩ B.

    We define the four regions corresponding to the Venn diagram cells of A and B, and prove they are pairwise disjoint by unfolding set differences and intersections.

    lines 67–107

      classical
      let R0 : Finset (Fin m) := (Finset.univ \ A) \ B
      let R1 : Finset (Fin m) := (Finset.univ \ A) ∩ B
      let R2 : Finset (Fin m) := A \ B
      let R3 : Finset (Fin m) := A ∩ B
      have d01 : Disjoint R0 R1 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hi hj
        tauto
      have d02 : Disjoint R0 R2 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hi hj
        tauto
      have d03 : Disjoint R0 R3 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hi hj
        tauto
      have d12 : Disjoint R1 R2 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hi hj
        tauto
      have d13 : Disjoint R1 R3 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hi hj
        tauto
      have d23 : Disjoint R2 R3 := by
        apply Finset.disjoint_left.mpr
        intro t hi hj
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hi hj
        tauto
  5. There exist disjoint subsets W ⊆ R₀, X ⊆ R₁, Y ⊆ R₂, Z ⊆ R₃ whose union S has size equal to the sum of the balanced counts w + x + y + z.

    Applying the four-type count lemma to the cardinalities of the four regions produces counts w, x, y, z. We choose subsets of those exact sizes within each region; pairwise disjointness of the regions ensures the cardinality of S = W ∪ X ∪ Y ∪ Z is w + x + y + z.

    lines 108–123

    uses in570_four_type_counts, Finset.exists_subset_card_eq, Finset.card_union_of_disjoint, Nat.add_assoc

      obtain ⟨w, x, y, z, hw, hx, hy, hz, htot, htotc, hB, hBc, hA, hAc⟩ :=
        in570_four_type_counts R0.card R1.card R2.card R3.card
      obtain ⟨W, hW, hWc⟩ := Finset.exists_subset_card_eq hw
      obtain ⟨X, hX, hXc⟩ := Finset.exists_subset_card_eq hx
      obtain ⟨Y, hY, hYc⟩ := Finset.exists_subset_card_eq hy
      obtain ⟨Z, hZ, hZc⟩ := Finset.exists_subset_card_eq hz
      have dWX : Disjoint W X := d01.mono hW hX
      have dWY : Disjoint W Y := d02.mono hW hY
      have dWZ : Disjoint W Z := d03.mono hW hZ
      have dXY : Disjoint X Y := d12.mono hX hY
      have dXZ : Disjoint X Z := d13.mono hX hZ
      have dYZ : Disjoint Y Z := d23.mono hY hZ
      let S := W ∪ X ∪ Y ∪ Z
      have hSc : S.card = w+x+y+z := by
        simp [S, Finset.card_union_of_disjoint, Finset.disjoint_union_left,
          dWX, dWY, dWZ, dXY, dXZ, dYZ, hWc, hXc, hYc, hZc, Nat.add_assoc]
  6. The four regions partition the m chores, A = R₂ ∪ R₃, B = R₁ ∪ R₃, S ∩ A = Y ∪ Z with size y + z, and S ∩ B = X ∪ Z with size x + z.

    Since the four regions partition the universe, their sizes sum to m. By definition of the regions, A and B are disjoint unions of their respective cells. Intersecting S with A and B isolates Y ∪ Z and X ∪ Z, whose cardinalities are y + z and x + z by disjointness.

    lines 124–168

    uses Finset.card_union_of_disjoint

      have hR : R0 ∪ R1 ∪ R2 ∪ R3 = Finset.univ := by
        ext t
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_union, Finset.mem_univ, true_and, iff_true]
        tauto
      have hRc : R0.card + R1.card + R2.card + R3.card = m := by
        have hc := congrArg Finset.card hR
        simp [Finset.card_union_of_disjoint, Finset.disjoint_union_left,
          d01, d02, d03, d12, d13, d23] at hc
        simpa [Nat.add_assoc] using hc
      have hAR : A = R2 ∪ R3 := by
        ext t
        simp only [R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_union]
        tauto
      have hBR : B = R1 ∪ R3 := by
        ext t
        simp only [R1, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ,
          Finset.mem_union, true_and]
        tauto
      have hAc' : A.card = R2.card + R3.card := by rw [hAR, Finset.card_union_of_disjoint d23]
      have hBc' : B.card = R1.card + R3.card := by rw [hBR, Finset.card_union_of_disjoint d13]
      have hSA : S ∩ A = Y ∪ Z := by
        ext t
        have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht
        have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht
        have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht
        have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hw' hx' hy' hz'
        simp only [S, Finset.mem_inter, Finset.mem_union]
        tauto
      have hSB : S ∩ B = X ∪ Z := by
        ext t
        have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht
        have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht
        have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht
        have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht
        simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,
          Finset.mem_univ, true_and] at hw' hx' hy' hz'
        simp only [S, Finset.mem_inter, Finset.mem_union]
        tauto
      have hSAc : (S ∩ A).card = y + z := by
        rw [hSA, Finset.card_union_of_disjoint dYZ, hYc, hZc]
      have hSBc : (S ∩ B).card = x + z := by
        rw [hSB, Finset.card_union_of_disjoint dXZ, hXc, hZc]
  7. The set S and its complement Sᶜ satisfy all six ceiling-half balance bounds for the total chore count and the sets A and B.

    The balance bounds on w, x, y, z translate directly into the required upper bounds on |S|, |Sᶜ|, |S ∩ A|, |A \ S|, |S ∩ B|, and |B \ S| via their cardinality formulas.

    lines 169–179

    uses Finset.card_sdiff

      refine ⟨S, ?_, ?_, ?_, ?_, ?_, ?_⟩
      · omega
      · rw [Finset.card_sdiff]
        simp only [Finset.inter_univ, Finset.card_univ, Fintype.card_fin, hSc]
        omega
      · omega
      · rw [Finset.card_sdiff, hSAc, hAc']
        omega
      · omega
      · rw [Finset.card_sdiff, hSBc, hBc']
        omega
  8. The additive valuation of any subset S under bivalued chore costs taking value r * a on H and a outside H is a(|S| + (r - 1)|S ∩ H|).

    We split the valuation sum over S into elements in S ∩ H (each costing r * a) and elements in S \ H (each costing a). Writing |S \ H| = |S| - |S ∩ H| and collecting terms yields a(|S| + (r - 1)|S ∩ H|).

    lines 186–192

    uses Finset.card_sdiff_add_card_inter

      classical
      have hc : ((S \ H).card : ℝ) + ((S ∩ H).card : ℝ) = (S.card : ℝ) := by
        exact_mod_cast Finset.card_sdiff_add_card_inter S H
      simp only [additive_valuation, hu, Finset.sum_ite, Finset.sum_const,
        Finset.filter_mem_eq_inter, Finset.filter_notMem_eq_sdiff, nsmul_eq_mul]
      rw [← hc]
      ring
  9. Half the total cost of all chores is a lower bound on the 2-agent chore MMS.

    In every 2-partition of chores, the sum of the costs of the two bundles equals the total cost of all chores, so the maximum bundle cost is at least half the total cost. Taking the infimum over all partitions bounds the chore MMS from below.

    lines 197–207

    uses le_ciInf, Fin.sum_univ_two, le_ciSup

      simp only [chore_maximin_share]
      refine le_ciInf fun P => ?_
      have hbdd : BddAbove (Set.range fun k : Fin 2 => additive_valuation u (bundle_of P k)) :=
        (Set.finite_range _).bddAbove
      have hsum : ∑ k : Fin 2, additive_valuation u (bundle_of P k) = ∑ g : Fin m, u g := by
        have h := Finset.sum_fiberwise (Finset.univ : Finset (Fin m)) P u
        simpa [bundle_of, additive_valuation] using h
      have h0 := le_ciSup hbdd (0 : Fin 2)
      have h1 := le_ciSup hbdd (1 : Fin 2)
      rw [Fin.sum_univ_two] at hsum
      linarith
  10. When m = 2k+1, any bundle S with |S| ≥ k + 1 has valuation at least a((k + 1) + (r - 1)(|H| - k)).

    When |S| ≥ k + 1, its complement has size at most k. High-cost chores outside S lie in Sᶜ, so |H \ S| ≤ k, which forces |S ∩ H| ≥ |H| - k. Since r ≥ 1, substituting these lower bounds into the valuation formula proves the claim.

    lines 215–237

    uses in570_bivalued_sum, Finset.card_sdiff, mul_le_mul_of_nonneg_left

      classical
      have hlarge (S : Finset (Fin (2*k+1))) (hbig : k + 1 ≤ S.card) :
          a * ((k + 1 : ℝ) + (r - 1) * ((H.card - k : ℕ) : ℝ)) ≤
            additive_valuation u S := by
        have hcomp : ((Finset.univ : Finset (Fin (2*k+1))) \ S).card ≤ k := by
          rw [Finset.card_sdiff]
          simp only [Finset.inter_univ, Finset.card_univ, Fintype.card_fin]
          omega
        have hsub : H \ S ⊆ (Finset.univ : Finset (Fin (2*k+1))) \ S := by
          intro g hg
          simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] at hg ⊢
          exact hg.2
        have hle := Finset.card_le_card hsub
        have hc : (H \ S).card + (S ∩ H).card = H.card := by
          simpa [Finset.inter_comm] using Finset.card_sdiff_add_card_inter H S
        have hh : H.card - k ≤ (S ∩ H).card := by omega
        have hbig' : (k + 1 : ℝ) ≤ (S.card : ℝ) := by exact_mod_cast hbig
        have hh' : ((H.card - k : ℕ) : ℝ) ≤ ((S ∩ H).card : ℝ) := by exact_mod_cast hh
        have hval : (k + 1 : ℝ) + (r - 1) * ((H.card - k : ℕ) : ℝ) ≤
            (S.card : ℝ) + (r - 1) * ((S ∩ H).card : ℝ) := by
          gcongr
        rw [in570_bivalued_sum (2*k+1) r a u H S hu]
        exact mul_le_mul_of_nonneg_left hval (le_of_lt ha)
  11. For 2k+1 chores, the 2-agent chore MMS is bounded below by a((k + 1) + (r - 1)(|H| - k)).

    In any 2-partition of 2k+1 chores, the pigeonhole principle guarantees that at least one bundle has size at least k + 1. The maximum bundle cost in the partition is therefore bounded below by that bundle's valuation, and taking the infimum over partitions completes the bound.

    lines 238–250

    uses le_ciInf, le_ciSup, le_trans

      simp only [chore_maximin_share]
      refine le_ciInf fun P => ?_
      have hsum : (bundle_of P 0).card + (bundle_of P 1).card = 2*k+1 := by
        have hh := Finset.sum_fiberwise (Finset.univ : Finset (Fin (2*k+1))) P (fun _ => (1 : ℕ))
        simpa [bundle_of, Fin.sum_univ_two] using hh
      have hex : ∃ i : Fin 2, k + 1 ≤ (bundle_of P i).card := by
        by_cases h0 : k + 1 ≤ (bundle_of P 0).card
        · exact ⟨0, h0⟩
        · exact ⟨1, by omega⟩
      obtain ⟨i, hi⟩ := hex
      have hbdd : BddAbove (Set.range fun i : Fin 2 => additive_valuation u (bundle_of P i)) :=
        (Set.finite_range _).bddAbove
      exact le_trans (hlarge (bundle_of P i) hi) (le_ciSup hbdd i)
  12. If |S| ≤ ⌈(m+1)/2⌉ and |S ∩ H| ≤ ⌈(|H|+1)/2⌉, then the valuation of S is at most a(⌈(m+1)/2⌉ + (r-1)⌈(|H|+1)/2⌉).

    Using the valuation formula u(S) = a(|S| + (r - 1)|S ∩ H|), because r ≥ 1 and a > 0, replacing |S| and |S ∩ H| with their upper bounds preserves the inequality.

    lines 260–265

    uses in570_bivalued_sum, mul_le_mul_of_nonneg_left

      have hs' : (S.card : ℝ) ≤ (((m + 1) / 2 : ℕ) : ℝ) := by exact_mod_cast hs
      have hh' : ((S ∩ H).card : ℝ) ≤ (((H.card + 1) / 2 : ℕ) : ℝ) := by exact_mod_cast hh
      rw [in570_bivalued_sum m r a u H S hu]
      apply mul_le_mul_of_nonneg_left _ (le_of_lt ha)
      have hh'' := mul_le_mul_of_nonneg_left hh' (sub_nonneg.mpr hr)
      linarith
  13. For m = 0, the balanced upper bound holds trivially.

    When m = 0, there are no chores and H is empty, so the upper bound evaluates to zero, which is at most ((r+1)/2) * MMS since MMS and (r+1)/2 are nonnegative.

    lines 274–291

    uses in570_total_half_le_mms, mul_nonneg

      classical
      have hd : 0 ≤ r - 1 := by linarith
      have halpha : 0 ≤ (r + 1) / 2 := by linarith
      have hu0 : ∀ g, 0 ≤ u g := by
        intro g
        rw [hu g]
        split_ifs <;> positivity
      have hmms : 0 ≤ chore_maximin_share 2 u := by
        have ht := in570_total_half_le_mms m u
        have hn : 0 ≤ ∑ g : Fin m, u g := Finset.sum_nonneg (fun g _ => hu0 g)
        linarith
      by_cases hz : m = 0
      · have hc : H.card = 0 := by
          have hh := Finset.card_le_univ H
          simp only [Fintype.card_fin, hz] at hh
          omega
        simp only [hz, hc, Nat.zero_add, Nat.reduceDiv, Nat.cast_zero, mul_zero, add_zero]
        exact mul_nonneg halpha hmms
  14. When m = 2k, the balanced ceiling upper bound is at most ((r+1)/2) times MMS.

    For m = 2k, ⌈(m+1)/2⌉ = k. Half the total cost is a(k + (r-1)|H|/2), which bounds MMS from below. The even arithmetic lemma with d = r - 1 shows that k + (r-1)⌈(|H|+1)/2⌉ ≤ (1 + (r-1)/2)(k + (r-1)|H|/2) = ((r+1)/2)(k + (r-1)|H|/2), completing the inequality.

    lines 292–316

    uses in570_even_arithmetic, in570_total_half_le_mms, in570_bivalued_sum, mul_le_mul_of_nonneg_left

      obtain ⟨k, hke | hko⟩ : ∃ k : ℕ, m = 2*k ∨ m = 2*k+1 := ⟨m/2, by omega⟩
      · subst m
        have hk : 1 ≤ k := by omega
        have hceil : (2*k+1)/2 = k := by omega
        have hsum : (∑ g : Fin (2*k), u g) =
            a * (2 * (k : ℝ) + (r - 1) * (H.card : ℝ)) := by
          have hs := in570_bivalued_sum (2*k) r a u H Finset.univ hu
          simpa [additive_valuation, Finset.card_univ, Fintype.card_fin,
            Nat.cast_mul] using hs
        have hhalf : a * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2) ≤
            chore_maximin_share 2 u := by
          calc
            a * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2) =
                (a * (2 * (k : ℝ) + (r - 1) * (H.card : ℝ))) / 2 := by ring
            _ = (∑ g : Fin (2*k), u g) / 2 := by rw [hsum]
            _ ≤ chore_maximin_share 2 u := in570_total_half_le_mms (2*k) u
        have hround := in570_even_arithmetic k H.card (r - 1) hk hd
        rw [hceil]
        calc
          a * ((k : ℝ) + (r - 1) * (((H.card + 1) / 2 : ℕ) : ℝ)) ≤
              a * ((1 + (r - 1) / 2) * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2)) :=
                mul_le_mul_of_nonneg_left hround (le_of_lt ha)
          _ = ((r + 1) / 2) * (a * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2)) := by ring
          _ ≤ ((r + 1) / 2) * chore_maximin_share 2 u :=
            mul_le_mul_of_nonneg_left hhalf halpha
  15. When m = 2k+1, the balanced ceiling upper bound is at most ((r+1)/2) times MMS.

    For m = 2k+1, ⌈(m+1+1)/2⌉ = k + 1. The odd arithmetic lemma bounds the upper bound by ((r+1)/2) a((k+1) + (r-1)(|H|-k)), which by the odd MMS lower bound is at most ((r+1)/2) * MMS.

    lines 317–329

    uses in570_odd_arithmetic, in570_odd_mms_lower, mul_le_mul_of_nonneg_left

      · subst m
        have hceil : (2*k+1+1)/2 = k+1 := by omega
        have hround := in570_odd_arithmetic k H.card (r - 1) hd
        have hlower := in570_odd_mms_lower k r a hr ha u H hu
        rw [hceil]
        simp only [Nat.cast_add, Nat.cast_one]
        calc
          a * ((k + 1 : ℝ) + (r - 1) * (((H.card + 1) / 2 : ℕ) : ℝ)) ≤
              a * ((1 + (r - 1) / 2) * ((k + 1 : ℝ) + (r - 1) * ((H.card - k : ℕ) : ℝ))) :=
                mul_le_mul_of_nonneg_left hround (le_of_lt ha)
          _ = ((r + 1) / 2) * (a * ((k + 1 : ℝ) + (r - 1) * ((H.card - k : ℕ) : ℝ))) := by ring
          _ ≤ ((r + 1) / 2) * chore_maximin_share 2 u :=
            mul_le_mul_of_nonneg_left hlower halpha
  16. Any bundle S satisfying the balance bounds ensures that both S and Sᶜ cost at most ((r+1)/2) times MMS for the agent.

    For bundle S, chaining the balanced cost upper bound with the bound relating it to MMS proves the inequality. For Sᶜ = univ \ S, its intersection with H is H \ S, which satisfies the same balance bound, so the identical chain applies.

    lines 342–349

    uses in570_balanced_upper_le_mms, in570_balanced_cost_upper, le_trans

      have hupp := in570_balanced_upper_le_mms m r a hr ha u H hu
      refine ⟨le_trans (in570_balanced_cost_upper m r a hr ha u H S hu hs hh) hupp, ?_⟩
      have hint : ((Finset.univ \ S) ∩ H) = H \ S := by
        ext g
        simp only [Finset.mem_inter, Finset.mem_sdiff, Finset.mem_univ, true_and]
        tauto
      have hhh : ((Finset.univ \ S) ∩ H).card ≤ (H.card + 1) / 2 := by rw [hint]; exact hhc
      exact le_trans (in570_balanced_cost_upper m r a hr ha u H (Finset.univ \ S) hu hsc hhh) hupp
  17. The swap lottery p assigning probability 1/2 to σ = (S, Sᶜ) and 1/2 to τ = (Sᶜ, S) is a valid probability distribution.

    We define allocations σ giving S to agent 0 and Sᶜ to agent 1, and τ swapping these bundles. The lottery p assigns probability 1/2 to each; the probabilities are nonnegative and sum to 1.

    lines 358–382

    uses Finset.sum_add_distrib

      classical
      let σ : Fin m → Fin 2 := fun g => if g ∈ S then 0 else 1
      let τ : Fin m → Fin 2 := fun g => if g ∈ S then 1 else 0
      let p : (Fin m → Fin 2) → ℝ := fun t =>
        (if t = σ then 1 / 2 else 0) + (if t = τ then 1 / 2 else 0)
      have bσ0 : bundle_of σ 0 = S := by
        ext g
        simp [bundle_of, σ]
      have bσ1 : bundle_of σ 1 = Finset.univ \ S := by
        ext g
        simp [bundle_of, σ]
      have bτ0 : bundle_of τ 0 = Finset.univ \ S := by
        ext g
        simp [bundle_of, τ]
      have bτ1 : bundle_of τ 1 = S := by
        ext g
        simp [bundle_of, τ]
      refine ⟨p, ?_, ?_, ?_⟩
      · constructor
        · intro t
          dsimp [p]
          positivity
        · dsimp [p]
          rw [Finset.sum_add_distrib]
          simp <;> norm_num
  18. Under p, every chore g is assigned to each agent i with marginal probability exactly 1/2.

    Because σ and τ assign each chore g to opposite agents, exactly one of the two allocations assigns chore g to agent i. The marginal probability sum reduces to that single allocation's probability, which is 1/2.

    lines 383–402

    uses congrFun, Finset.sum_add_distrib, Finset.sum_ite_eq', if_true

      · intro g i
        change (∑ t : Fin m → Fin 2, if t g = i then p t else 0) = 1 / (2 : ℝ)
        have hστ : σ ≠ τ := by
          intro h
          have hv := congrFun h g
          by_cases hg : g ∈ S <;> simp [σ, τ, hg] at hv
        have hexpand (t : Fin m → Fin 2) :
            (if t g = i then p t else 0) =
              (if t = σ then (if σ g = i then (1 / 2 : ℝ) else 0) else 0) +
              (if t = τ then (if τ g = i then (1 / 2 : ℝ) else 0) else 0) := by
          by_cases hσ : t = σ
          · subst t
            simp [p, hστ]
          · by_cases hτ : t = τ
            · subst t
              simp [p, Ne.symm hστ]
            · simp [p, hσ, hτ]
        simp only [hexpand, Finset.sum_add_distrib]
        simp only [Finset.sum_ite_eq', Finset.mem_univ, if_true]
        fin_cases i <;> by_cases hg : g ∈ S <;> simp [σ, τ, hg]
  19. Every allocation in the support of p is ex-post α-MMS for both agents.

    The allocations in the support of p are σ and τ. Both allocate S to one agent and Sᶜ to the other. By assumption, both bundles have valuation at most α * MMS for both agents.

    lines 403–413

      · intro t hp i
        change additive_valuation (c i) (bundle_of t i) ≤ α * chore_maximin_share 2 (c i)
        have ht : t = σ ∨ t = τ := by
          by_contra hh
          push_neg at hh
          simp [p, hh.1, hh.2] at hp
        rcases ht with rfl | rfl <;> fin_cases i
        · simpa [bσ0] using hS 0
        · simpa [bσ1] using hSc 1
        · simpa [bτ0] using hSc 0
        · simpa [bτ1] using hS 1
  20. For two agents with scaled bivalued chore costs with ratio r ∈ [1, 2], there exists an equal-marginal lottery that is ex-post ((r+1)/2)-MMS.

    We extract each agent's set of high-cost chores H₀ and H₁. The two-subset balancing lemma produces a bundle S balancing both the total chore count and H₀, H₁. By the one-agent balanced lemma, both S and Sᶜ guarantee at most ((r+1)/2) * MMS for both agents, and the swap lottery lemma produces the required equal-marginal, ex-post ((r+1)/2)-MMS lottery.

    lines 423–439

    uses in570_balance_two_subsets, in570_one_agent_balanced, in570_swap_lottery

      classical
      obtain ⟨a, ha, hv⟩ := hc
      let H : Fin 2 → Finset (Fin m) := fun i => Finset.univ.filter (fun g => c i g = r * a i)
      have hval (i : Fin 2) (g : Fin m) : c i g = if g ∈ H i then r * a i else a i := by
        by_cases h : c i g = r * a i
        · simp [H, h]
        · have hg := hv i g
          simp only [H, Finset.mem_filter, Finset.mem_univ, true_and, h, if_false]
          exact hg.resolve_right h
      obtain ⟨S, hs, hsc, h0, h0c, h1, h1c⟩ := in570_balance_two_subsets m (H 0) (H 1)
      have hboth (i : Fin 2) :
          additive_valuation (c i) S ≤ ((r + 1) / 2) * chore_maximin_share 2 (c i) ∧
          additive_valuation (c i) (Finset.univ \ S) ≤ ((r + 1) / 2) * chore_maximin_share 2 (c i) := by
        fin_cases i
        · exact in570_one_agent_balanced m r (a 0) hr1 (ha 0) (c 0) (H 0) S (hval 0) hs hsc h0 h0c
        · exact in570_one_agent_balanced m r (a 1) hr1 (ha 1) (c 1) (H 1) S (hval 1) hs hsc h1 h1c
      exact in570_swap_lottery m ((r + 1) / 2) c S (fun i => (hboth i).1) (fun i => (hboth i).2)
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.exists_subset_card_eq
For any finite set and integer n at most its cardinality, there exists a subset of size n.
Finset.card_sdiff
The cardinality of a set difference t \ s is |t| - |s ∩ t|.
Finset.card_sdiff_add_card_inter
For any finite sets s and t, |s \ t| + |s ∩ t| = |s|.
Finset.sum_add_distrib
The sum of two functions over a finite set equals the sum of their individual sums.
Finset.sum_ite_eq'
A sum over a finite set of a function non-zero only at a single point a equals the value at a if a is in the set.
Fin.sum_univ_two
A sum over the two elements of Fin 2 equals f(0) + f(1).
Nat.add_assoc
Addition of natural numbers is associative: (n + m) + k = n + (m + k).
Nat.mod_lt
The remainder of division of x by y is strictly less than y whenever y > 0.
congrFun
Equal functions take equal values on any input.
if_true
An if-then-else whose condition is True reduces to the then-branch.
le_ciInf
A lower bound for each value of a function is a lower bound for its infimum.
le_ciSup
Any value in the range of a bounded-above function is bounded above by its supremum.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
mul_le_mul_of_nonneg_left
Multiplying an inequality by a nonnegative factor preserves the inequality.
mul_nonneg
The product of two nonnegative numbers is nonnegative.
in570_balanced_cost_upper
For any bundle S with |S| and |S ∩ H| bounded by their ceiling halves, its valuation is at most a(⌈(m+1)/2⌉ + (r-1)⌈(|H|+1)/2⌉).
in570_balanced_upper_le_mms
The balanced ceiling cost bound a(⌈(m+1)/2⌉ + (r-1)⌈(|H|+1)/2⌉) is at most ((r+1)/2) times the 2-agent chore MMS.
in570_balance_two_subsets
Given two subsets A and B of m chores, there exists a subset S whose size and intersections with A, B, and their complements are bounded by their ceiling halves.
in570_bivalued_sum
For bivalued costs taking value r * a on H and a outside H, the additive valuation of S is a(|S| + (r - 1)|S ∩ H|).
in570_even_arithmetic
For k ≥ 1 and d ≥ 0, k + d ⌈(h+1)/2⌉ ≤ (1 + d/2)(k + d h / 2).
in570_four_type_counts
For four integers a, b, c, d, there exist sub-counts w ≤ a, x ≤ b, y ≤ c, z ≤ d whose sum and pairs balance with their complements to within ceiling halves.
in570_odd_arithmetic
For d ≥ 0, (k+1) + d ⌈(h+1)/2⌉ ≤ (1 + d/2)((k+1) + d(h - k)).
in570_odd_mms_lower
When m = 2k+1, the 2-agent chore MMS for a bivalued profile is at least a((k+1) + (r-1)(|H| - k)).
in570_one_agent_balanced
If a bundle S and its complement satisfy the ceiling balance conditions for an agent, then both bundles cost at most ((r+1)/2) times MMS.
in570_swap_lottery
Given a bundle S such that both S and its complement cost at most α MMS for both agents, the 50-50 swap lottery is equal-marginal and ex-post α-MMS.
in570_total_half_le_mms
Half of the total cost of all chores is a lower bound on the 2-agent chore MMS.

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

Lean’s trace was cut to the first 400 of 697 tactics.

private lemma in570_even_arithmetic (k h : ℕ) (d : ℝ) (hk : 1 ≤ k) (hd : 0 ≤ d) :    (k : ℝ) + d * (((h + 1) / 2 : ℕ) : ℝ) ≤      (1 + d / 2) * ((k : ℝ) + d * (h : ℝ) / 2) := by  have hc : 2 * ((h + 1) / 2) ≤ h + 1 := by omega  have hcr : (2 : ℝ) * (((h + 1) / 2 : ℕ) : ℝ) ≤ (h : ℝ) + 1 := by    exact_mod_cast hc  have hkr : (1 : ℝ) ≤ k := by exact_mod_cast hk  have harr : 0 ≤ (k : ℝ) + (h : ℝ) - 2 * (((h + 1) / 2 : ℕ) : ℝ) := by linarith  have hmul := mul_nonneg hd harr  have hsq : 0 ≤ d * d * (h : ℝ) := by positivity  nlinarithprivate lemma in570_odd_arithmetic (k h : ℕ) (d : ℝ) (hd : 0 ≤ d) :    (k + 1 : ℝ) + d * (((h + 1) / 2 : ℕ) : ℝ) ≤      (1 + d / 2) * ((k + 1 : ℝ) + d * ((h - k : ℕ) : ℝ)) := by  have hc : 2 * ((h + 1) / 2) ≤ k + 1 + 2 * (h - k) := by omega  have hcr : (2 : ℝ) * (((h + 1) / 2 : ℕ) : ℝ) ≤      (k : ℝ) + 1 + 2 * ((h - k : ℕ) : ℝ) := by    exact_mod_cast hc  have harr : 0 ≤ (k : ℝ) + 1 + 2 * ((h - k : ℕ) : ℝ) -      2 * (((h + 1) / 2 : ℕ) : ℝ) := by linarith  have hmul := mul_nonneg hd harr  have hsq : 0 ≤ d * d * ((h - k : ℕ) : ℝ) := by positivity  nlinarithprivate lemma in570_four_type_counts (a b c d : ℕ) :    ∃ w x y z : ℕ,      w ≤ a ∧ x ≤ b ∧ y ≤ c ∧ z ≤ d ∧      w+x+y+z ≤ (a+b+c+d+1)/2 ∧      (a-w)+(b-x)+(c-y)+(d-z) ≤ (a+b+c+d+1)/2 ∧      x+z ≤ (b+d+1)/2 ∧ (b-x)+(d-z) ≤ (b+d+1)/2 ∧      y+z ≤ (c+d+1)/2 ∧ (c-y)+(d-z) ≤ (c+d+1)/2 := by  have ha : a % 2 < 2 := Nat.mod_lt _ (by omega)  have hb : b % 2 < 2 := Nat.mod_lt _ (by omega)  have hc : c % 2 < 2 := Nat.mod_lt _ (by omega)  have hd : d % 2 < 2 := Nat.mod_lt _ (by omega)  interval_cases hma : a % 2 <;> interval_cases hmb : b % 2 <;>    interval_cases hmc : c % 2 <;> interval_cases hmd : d % 2 <;>    first    | refine ⟨a / 2, b / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨a / 2, b / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨a / 2, b / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨a / 2, b / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨a / 2, (b + 1) / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨a / 2, (b + 1) / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨a / 2, (b + 1) / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨a / 2, (b + 1) / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨(a + 1) / 2, b / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨(a + 1) / 2, b / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨(a + 1) / 2, b / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨(a + 1) / 2, b / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨(a + 1) / 2, (b + 1) / 2, c / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨(a + 1) / 2, (b + 1) / 2, c / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨(a + 1) / 2, (b + 1) / 2, (c + 1) / 2, d / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omega    | refine ⟨(a + 1) / 2, (b + 1) / 2, (c + 1) / 2, (d + 1) / 2, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ <;> omegaprivate lemma in570_balance_two_subsets (m : ℕ) (A B : Finset (Fin m)) :    ∃ S : Finset (Fin m),      S.card ≤ (m + 1) / 2 ∧      (Finset.univ \ S).card ≤ (m + 1) / 2 ∧      (S ∩ A).card ≤ (A.card + 1) / 2 ∧      (A \ S).card ≤ (A.card + 1) / 2 ∧      (S ∩ B).card ≤ (B.card + 1) / 2 ∧      (B \ S).card ≤ (B.card + 1) / 2 := by  classical  let R0 : Finset (Fin m) := (Finset.univ \ A) \ B  let R1 : Finset (Fin m) := (Finset.univ \ A) ∩ B  let R2 : Finset (Fin m) := A \ B  let R3 : Finset (Fin m) := A ∩ B  have d01 : Disjoint R0 R1 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hi hj    tauto  have d02 : Disjoint R0 R2 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hi hj    tauto  have d03 : Disjoint R0 R3 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hi hj    tauto  have d12 : Disjoint R1 R2 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hi hj    tauto  have d13 : Disjoint R1 R3 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hi hj    tauto  have d23 : Disjoint R2 R3 := by    apply Finset.disjoint_left.mpr    intro t hi hj    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hi hj    tauto  obtain ⟨w, x, y, z, hw, hx, hy, hz, htot, htotc, hB, hBc, hA, hAc⟩ :=    in570_four_type_counts R0.card R1.card R2.card R3.card  obtain ⟨W, hW, hWc⟩ := Finset.exists_subset_card_eq hw  obtain ⟨X, hX, hXc⟩ := Finset.exists_subset_card_eq hx  obtain ⟨Y, hY, hYc⟩ := Finset.exists_subset_card_eq hy  obtain ⟨Z, hZ, hZc⟩ := Finset.exists_subset_card_eq hz  have dWX : Disjoint W X := d01.mono hW hX  have dWY : Disjoint W Y := d02.mono hW hY  have dWZ : Disjoint W Z := d03.mono hW hZ  have dXY : Disjoint X Y := d12.mono hX hY  have dXZ : Disjoint X Z := d13.mono hX hZ  have dYZ : Disjoint Y Z := d23.mono hY hZ  let S := W ∪ X ∪ Y ∪ Z  have hSc : S.card = w+x+y+z := by    simp [S, Finset.card_union_of_disjoint, Finset.disjoint_union_left,      dWX, dWY, dWZ, dXY, dXZ, dYZ, hWc, hXc, hYc, hZc, Nat.add_assoc]  have hR : R0 ∪ R1 ∪ R2 ∪ R3 = Finset.univ := by    ext t    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_union, Finset.mem_univ, true_and, iff_true]    tauto  have hRc : R0.card + R1.card + R2.card + R3.card = m := by    have hc := congrArg Finset.card hR    simp [Finset.card_union_of_disjoint, Finset.disjoint_union_left,      d01, d02, d03, d12, d13, d23] at hc    simpa [Nat.add_assoc] using hc  have hAR : A = R2 ∪ R3 := by    ext t    simp only [R2, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_union]    tauto  have hBR : B = R1 ∪ R3 := by    ext t    simp only [R1, R3, Finset.mem_sdiff, Finset.mem_inter, Finset.mem_univ,      Finset.mem_union, true_and]    tauto  have hAc' : A.card = R2.card + R3.card := by rw [hAR, Finset.card_union_of_disjoint d23]  have hBc' : B.card = R1.card + R3.card := by rw [hBR, Finset.card_union_of_disjoint d13]  have hSA : S ∩ A = Y ∪ Z := by    ext t    have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht    have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht    have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht    have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hw' hx' hy' hz'    simp only [S, Finset.mem_inter, Finset.mem_union]    tauto  have hSB : S ∩ B = X ∪ Z := by    ext t    have hw' : t ∈ W → t ∈ R0 := fun ht => hW ht    have hx' : t ∈ X → t ∈ R1 := fun ht => hX ht    have hy' : t ∈ Y → t ∈ R2 := fun ht => hY ht    have hz' : t ∈ Z → t ∈ R3 := fun ht => hZ ht    simp only [R0, R1, R2, R3, Finset.mem_sdiff, Finset.mem_inter,      Finset.mem_univ, true_and] at hw' hx' hy' hz'    simp only [S, Finset.mem_inter, Finset.mem_union]    tauto  have hSAc : (S ∩ A).card = y + z := by    rw [hSA, Finset.card_union_of_disjoint dYZ, hYc, hZc]  have hSBc : (S ∩ B).card = x + z := by    rw [hSB, Finset.card_union_of_disjoint dXZ, hXc, hZc]  refine ⟨S, ?_, ?_, ?_, ?_, ?_, ?_⟩  · omega  · rw [Finset.card_sdiff]    simp only [Finset.inter_univ, Finset.card_univ, Fintype.card_fin, hSc]    omega  · omega  · rw [Finset.card_sdiff, hSAc, hAc']    omega  · omega  · rw [Finset.card_sdiff, hSBc, hBc']    omegaprivate lemma in570_bivalued_sum (m : ℕ) (r a : ℝ) (u : Fin m → ℝ)    (H S : Finset (Fin m)) (hu : ∀ g, u g = if g ∈ H then r * a else a) :    additive_valuation u S =      a * ((S.card : ℝ) + (r - 1) * ((S ∩ H).card : ℝ)) := by  classical  have hc : ((S \ H).card : ℝ) + ((S ∩ H).card : ℝ) = (S.card : ℝ) := by    exact_mod_cast Finset.card_sdiff_add_card_inter S H  simp only [additive_valuation, hu, Finset.sum_ite, Finset.sum_const,    Finset.filter_mem_eq_inter, Finset.filter_notMem_eq_sdiff, nsmul_eq_mul]  rw [← hc]  ringprivate lemma in570_total_half_le_mms (m : ℕ) (u : Fin m → ℝ) :    (∑ g : Fin m, u g) / 2 ≤ chore_maximin_share 2 u := by  simp only [chore_maximin_share]  refine le_ciInf fun P => ?_  have hbdd : BddAbove (Set.range fun k : Fin 2 => additive_valuation u (bundle_of P k)) :=    (Set.finite_range _).bddAbove  have hsum : ∑ k : Fin 2, additive_valuation u (bundle_of P k) = ∑ g : Fin m, u g := by    have h := Finset.sum_fiberwise (Finset.univ : Finset (Fin m)) P u    simpa [bundle_of, additive_valuation] using h  have h0 := le_ciSup hbdd (0 : Fin 2)  have h1 := le_ciSup hbdd (1 : Fin 2)  rw [Fin.sum_univ_two] at hsum  linarithprivate lemma in570_odd_mms_lower (k : ℕ) (r a : ℝ) (hr : 1 ≤ r) (ha : 0 < a)    (u : Fin (2*k+1) → ℝ) (H : Finset (Fin (2*k+1)))    (hu : ∀ g, u g = if g ∈ H then r * a else a) :    a * ((k + 1 : ℝ) + (r - 1) * ((H.card - k : ℕ) : ℝ)) ≤      chore_maximin_share 2 u := by  classical  have hlarge (S : Finset (Fin (2*k+1))) (hbig : k + 1 ≤ S.card) :      a * ((k + 1 : ℝ) + (r - 1) * ((H.card - k : ℕ) : ℝ)) ≤        additive_valuation u S := by    have hcomp : ((Finset.univ : Finset (Fin (2*k+1))) \ S).card ≤ k := by      rw [Finset.card_sdiff]      simp only [Finset.inter_univ, Finset.card_univ, Fintype.card_fin]      omega    have hsub : H \ S ⊆ (Finset.univ : Finset (Fin (2*k+1))) \ S := by      intro g hg      simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] at hg ⊢      exact hg.2    have hle := Finset.card_le_card hsub    have hc : (H \ S).card + (S ∩ H).card = H.card := by      simpa [Finset.inter_comm] using Finset.card_sdiff_add_card_inter H S    have hh : H.card - k ≤ (S ∩ H).card := by omega    have hbig' : (k + 1 : ℝ) ≤ (S.card : ℝ) := by exact_mod_cast hbig    have hh' : ((H.card - k : ℕ) : ℝ) ≤ ((S ∩ H).card : ℝ) := by exact_mod_cast hh    have hval : (k + 1 : ℝ) + (r - 1) * ((H.card - k : ℕ) : ℝ) ≤        (S.card : ℝ) + (r - 1) * ((S ∩ H).card : ℝ) := by      gcongr    rw [in570_bivalued_sum (2*k+1) r a u H S hu]    exact mul_le_mul_of_nonneg_left hval (le_of_lt ha)  simp only [chore_maximin_share]  refine le_ciInf fun P => ?_  have hsum : (bundle_of P 0).card + (bundle_of P 1).card = 2*k+1 := by    have hh := Finset.sum_fiberwise (Finset.univ : Finset (Fin (2*k+1))) P (fun _ => (1 : ℕ))    simpa [bundle_of, Fin.sum_univ_two] using hh  have hex : ∃ i : Fin 2, k + 1 ≤ (bundle_of P i).card := by    by_cases h0 : k + 1 ≤ (bundle_of P 0).card    · exact ⟨0, h0⟩    · exact ⟨1, by omega⟩  obtain ⟨i, hi⟩ := hex  have hbdd : BddAbove (Set.range fun i : Fin 2 => additive_valuation u (bundle_of P i)) :=    (Set.finite_range _).bddAbove  exact le_trans (hlarge (bundle_of P i) hi) (le_ciSup hbdd i)private lemma in570_balanced_cost_upper (m : ℕ) (r a : ℝ) (hr : 1 ≤ r) (ha : 0 < a)    (u : Fin m → ℝ) (H S : Finset (Fin m))    (hu : ∀ g, u g = if g ∈ H then r * a else a)    (hs : S.card ≤ (m + 1) / 2)    (hh : (S ∩ H).card ≤ (H.card + 1) / 2) :    additive_valuation u S ≤ a * ((((m + 1) / 2 : ℕ) : ℝ) +      (r - 1) * (((H.card + 1) / 2 : ℕ) : ℝ)) := by  have hs' : (S.card : ℝ) ≤ (((m + 1) / 2 : ℕ) : ℝ) := by exact_mod_cast hs  have hh' : ((S ∩ H).card : ℝ) ≤ (((H.card + 1) / 2 : ℕ) : ℝ) := by exact_mod_cast hh  rw [in570_bivalued_sum m r a u H S hu]  apply mul_le_mul_of_nonneg_left _ (le_of_lt ha)  have hh'' := mul_le_mul_of_nonneg_left hh' (sub_nonneg.mpr hr)  linarithprivate lemma in570_balanced_upper_le_mms (m : ℕ) (r a : ℝ) (hr : 1 ≤ r) (ha : 0 < a)    (u : Fin m → ℝ) (H : Finset (Fin m))    (hu : ∀ g, u g = if g ∈ H then r * a else a) :    a * ((((m + 1) / 2 : ℕ) : ℝ) +      (r - 1) * (((H.card + 1) / 2 : ℕ) : ℝ)) ≤      ((r + 1) / 2) * chore_maximin_share 2 u := by  classical  have hd : 0 ≤ r - 1 := by linarith  have halpha : 0 ≤ (r + 1) / 2 := by linarith  have hu0 : ∀ g, 0 ≤ u g := by    intro g    rw [hu g]    split_ifs <;> positivity  have hmms : 0 ≤ chore_maximin_share 2 u := by    have ht := in570_total_half_le_mms m u    have hn : 0 ≤ ∑ g : Fin m, u g := Finset.sum_nonneg (fun g _ => hu0 g)    linarith  by_cases hz : m = 0  · have hc : H.card = 0 := by      have hh := Finset.card_le_univ H      simp only [Fintype.card_fin, hz] at hh      omega    simp only [hz, hc, Nat.zero_add, Nat.reduceDiv, Nat.cast_zero, mul_zero, add_zero]    exact mul_nonneg halpha hmms  obtain ⟨k, hke | hko⟩ : ∃ k : ℕ, m = 2*k ∨ m = 2*k+1 := ⟨m/2, by omega⟩  · subst m    have hk : 1 ≤ k := by omega    have hceil : (2*k+1)/2 = k := by omega    have hsum : (∑ g : Fin (2*k), u g) =        a * (2 * (k : ℝ) + (r - 1) * (H.card : ℝ)) := by      have hs := in570_bivalued_sum (2*k) r a u H Finset.univ hu      simpa [additive_valuation, Finset.card_univ, Fintype.card_fin,        Nat.cast_mul] using hs    have hhalf : a * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2) ≤        chore_maximin_share 2 u := by      calc        a * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2) =            (a * (2 * (k : ℝ) + (r - 1) * (H.card : ℝ))) / 2 := by ring        _ = (∑ g : Fin (2*k), u g) / 2 := by rw [hsum]        _ ≤ chore_maximin_share 2 u := in570_total_half_le_mms (2*k) u    have hround := in570_even_arithmetic k H.card (r - 1) hk hd    rw [hceil]    calc      a * ((k : ℝ) + (r - 1) * (((H.card + 1) / 2 : ℕ) : ℝ)) ≤          a * ((1 + (r - 1) / 2) * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2)) :=            mul_le_mul_of_nonneg_left hround (le_of_lt ha)      _ = ((r + 1) / 2) * (a * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2)) := by ring      _ ≤ ((r + 1) / 2) * chore_maximin_share 2 u :=        mul_le_mul_of_nonneg_left hhalf halpha  · subst m    have hceil : (2*k+1+1)/2 = k+1 := by omega    have hround := in570_odd_arithmetic k H.card (r - 1) hd    have hlower := in570_odd_mms_lower k r a hr ha u H hu    rw [hceil]    simp only [Nat.cast_add, Nat.cast_one]    calc      a * ((k + 1 : ℝ) + (r - 1) * (((H.card + 1) / 2 : ℕ) : ℝ)) ≤          a * ((1 + (r - 1) / 2) * ((k + 1 : ℝ) + (r - 1) * ((H.card - k : ℕ) : ℝ))) :=            mul_le_mul_of_nonneg_left hround (le_of_lt ha)      _ = ((r + 1) / 2) * (a * ((k + 1 : ℝ) + (r - 1) * ((H.card - k : ℕ) : ℝ))) := by ring      _ ≤ ((r + 1) / 2) * chore_maximin_share 2 u :=        mul_le_mul_of_nonneg_left hlower halphaprivate lemma in570_one_agent_balanced (m : ℕ) (r a : ℝ) (hr : 1 ≤ r) (ha : 0 < a)    (u : Fin m → ℝ) (H S : Finset (Fin m))    (hu : ∀ g, u g = if g ∈ H then r * a else a)    (hs : S.card ≤ (m + 1) / 2)    (hsc : (Finset.univ \ S).card ≤ (m + 1) / 2)    (hh : (S ∩ H).card ≤ (H.card + 1) / 2)    (hhc : (H \ S).card ≤ (H.card + 1) / 2) :    additive_valuation u S ≤ ((r + 1) / 2) * chore_maximin_share 2 u ∧    additive_valuation u (Finset.univ \ S) ≤      ((r + 1) / 2) * chore_maximin_share 2 u := by  have hupp := in570_balanced_upper_le_mms m r a hr ha u H hu  refine ⟨le_trans (in570_balanced_cost_upper m r a hr ha u H S hu hs hh) hupp, ?_⟩  have hint : ((Finset.univ \ S) ∩ H) = H \ S := by    ext g    simp only [Finset.mem_inter, Finset.mem_sdiff, Finset.mem_univ, true_and]    tauto  have hhh : ((Finset.univ \ S) ∩ H).card ≤ (H.card + 1) / 2 := by rw [hint]; exact hhc  exact le_trans (in570_balanced_cost_upper m r a hr ha u H (Finset.univ \ S) hu hsc hhh) huppprivate lemma in570_swap_lottery (m : ℕ) (α : ℝ) (c : Fin 2 → Fin m → ℝ) (S : Finset (Fin m))    (hS : ∀ i, additive_valuation (c i) S ≤ α * chore_maximin_share 2 (c i))    (hSc : ∀ i, additive_valuation (c i) (Finset.univ \ S) ≤      α * chore_maximin_share 2 (c i)) :    ∃ p ∈ stdSimplex ℝ (Fin m → Fin 2),      is_equal_marginal_lottery p ∧ is_ex_post_alpha_mms_chores α c p := by  classical  let σ : Fin m → Fin 2 := fun g => if g ∈ S then 0 else 1  let τ : Fin m → Fin 2 := fun g => if g ∈ S then 1 else 0  let p : (Fin m → Fin 2) → ℝ := fun t =>    (if t = σ then 1 / 2 else 0) + (if t = τ then 1 / 2 else 0)  have bσ0 : bundle_of σ 0 = S := by    ext g    simp [bundle_of, σ]  have bσ1 : bundle_of σ 1 = Finset.univ \ S := by    ext g    simp [bundle_of, σ]  have bτ0 : bundle_of τ 0 = Finset.univ \ S := by    ext g    simp [bundle_of, τ]  have bτ1 : bundle_of τ 1 = S := by    ext g    simp [bundle_of, τ]  refine ⟨p, ?_, ?_, ?_⟩  · constructor    · intro t      dsimp [p]      positivity    · dsimp [p]      rw [Finset.sum_add_distrib]      simp <;> norm_num  · intro g i    change (∑ t : Fin m → Fin 2, if t g = i then p t else 0) = 1 / (2 : ℝ)    have hστ : σ ≠ τ := by      intro h      have hv := congrFun h g      by_cases hg : g ∈ S <;> simp [σ, τ, hg] at hv    have hexpand (t : Fin m → Fin 2) :        (if t g = i then p t else 0) =          (if t = σ then (if σ g = i then (1 / 2 : ℝ) else 0) else 0) +          (if t = τ then (if τ g = i then (1 / 2 : ℝ) else 0) else 0) := by      by_cases hσ : t = σ      · subst t        simp [p, hστ]      · by_cases hτ : t = τ        · subst t          simp [p, Ne.symm hστ]        · simp [p, hσ, hτ]    simp only [hexpand, Finset.sum_add_distrib]    simp only [Finset.sum_ite_eq', Finset.mem_univ, if_true]    fin_cases i <;> by_cases hg : g ∈ S <;> simp [σ, τ, hg]  · intro t hp i    change additive_valuation (c i) (bundle_of t i) ≤ α * chore_maximin_share 2 (c i)    have ht : t = σ ∨ t = τ := by      by_contra hh      push_neg at hh      simp [p, hh.1, hh.2] at hp    rcases ht with rfl | rfl <;> fin_cases i    · simpa [bσ0] using hS 0    · simpa [bσ1] using hSc 1    · simpa [bτ0] using hSc 0    · simpa [bτ1] using hS 1/-- Two-agent case: every scaled bivalued chore profile admits an equal-marginal ex-post ((r+1)/2)-MMS lottery. -/theorem two_agent_bivalued_equal_marginal_sharp_mms    (r : ℝ) (hr1 : 1 ≤ r) (hr2 : r ≤ 2)    (m : ℕ) (c : Fin 2 → Fin m → ℝ)    (hc : is_scaled_bivalued_chores r c) :    ∃ p ∈ stdSimplex ℝ (Fin m → Fin 2),      is_equal_marginal_lottery p ∧      is_ex_post_alpha_mms_chores ((r + 1) / 2) c p := by  classical  obtain ⟨a, ha, hv⟩ := hc  let H : Fin 2 → Finset (Fin m) := fun i => Finset.univ.filter (fun g => c i g = r * a i)  have hval (i : Fin 2) (g : Fin m) : c i g = if g ∈ H i then r * a i else a i := by    by_cases h : c i g = r * a i    · simp [H, h]    · have hg := hv i g      simp only [H, Finset.mem_filter, Finset.mem_univ, true_and, h, if_false]      exact hg.resolve_right h  obtain ⟨S, hs, hsc, h0, h0c, h1, h1c⟩ := in570_balance_two_subsets m (H 0) (H 1)  have hboth (i : Fin 2) :      additive_valuation (c i) S ≤ ((r + 1) / 2) * chore_maximin_share 2 (c i) ∧      additive_valuation (c i) (Finset.univ \ S) ≤ ((r + 1) / 2) * chore_maximin_share 2 (c i) := by    fin_cases i    · exact in570_one_agent_balanced m r (a 0) hr1 (ha 0) (c 0) (H 0) S (hval 0) hs hsc h0 h0c    · exact in570_one_agent_balanced m r (a 1) hr1 (ha 1) (c 1) (H 1) S (hval 1) hs hsc h1 h1c  exact in570_swap_lottery m ((r + 1) / 2) c S (fun i => (hboth i).1) (fun i => (hboth i).2)
See it in the graphDiscuss this resultChallenge it