AFTD Auto-Formalizing Theoretical Domains

uniform_bivalued_obstruction_no_equal_marginal_exact_mms

theoremverifiedformalization

For every integer t at least 2 and every real ratio r strictly between 1 + 1/t and 1 + 1/(t-1), the instance with 4t chores where agent 0 assigns cost 1 to all chores and agent 1 assigns cost r to 2t - 1 chores and cost 1 to 2t + 1 chores admits no equal-marginal exact-MMS lottery.

Statement

theorem uniform_bivalued_obstruction_no_equal_marginal_exact_mms
    (t : ℕ) (ht : 2 ≤ t)
    (r : ℝ) (hr_lo : 1 + 1 / (t : ℝ) < r) (hr_hi : r < 1 + 1 / ((t - 1 : ℕ) : ℝ)) :
    ¬ ∃ p ∈ stdSimplex ℝ (Fin (4 * t) → Fin 2),
      is_equal_marginal_lottery p ∧
      is_ex_post_alpha_mms_chores 1 (uniform_bivalued_obstruction_cost t r) p
Formalizes
OP-1697
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • uniform_bivalued_obstruction_costThe two-agent chore cost profile on 4t chores where agent 0 assigns cost 1 to every chore, while agent 1 assigns cost r to 2t - 1 high…
  • 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_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…
  • is_alpha_mms_choresAn allocation σ of m chores among n agents is α-MMS for cost functions c if each agent i's total cost for her assigned bundle bundle_of σ…
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • 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.
  • 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…

Read back from the Lean

Given a natural number $t \ge 2$ and a real number $r$ satisfying $1 + \frac{1}{t} < r < 1 + \frac{1}{t - 1}$, there does not exist a probability distribution $p$ in the standard simplex over allocations $\sigma : \text{Fin}(4t) \to \text{Fin}(2)$ such that simultaneously: 1. $p$ is an equal-marginal lottery: for every chore $g \in \text{Fin}(4t)$ and every agent $i \in \text{Fin}(2)$, the marginal probability $\sum_{\sigma, \sigma(g) = i} p(\sigma)$ equals $1/2$; and 2. $p$ is ex-post $1$-MMS for chores with respect to the cost function $c = \text{uniform\_bivalued\_obstruction\_cost}(t, r)$: every allocation $\sigma$ with $p(\sigma) > 0$ gives each agent $i \in \text{Fin}(2)$ a bundle whose additive cost $\sum_{g, \sigma(g) = i} c(i, g)$ is at most agent $i$'s $2$-agent chore maximin share $\text{chore\_maximin\_share}(2, c(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

The proof proceeds by contradiction, supposing an equal-marginal exact-MMS lottery exists for the 4t-chore instance. Because Agent 0 assigns unit cost to all chores, Agent 0's maximin share is at most 2t, forcing Agent 1 to receive at least 2t chores in every allocation in the support. Testing the partition that separates the 2t - 1 high chores from the 2t + 1 low chores shows that Agent 1's maximin share is strictly less than t * (1 + r); together with receiving at least 2t chores, this cost cap forces Agent 1 to receive at most t - 1 high chores in every supported allocation. But by the equal-marginal property, Agent 1 must receive an expected (2t - 1) / 2 = t - 1/2 high chores, which contradicts the upper bound of t - 1.

  1. The number of elements in Fin n with value at least m is n - min(n, m).

    Partition Fin n into elements strictly less than m and elements at least m. Since the total size is n and the count of elements strictly less than m is min(n, m) (by Fin.card_filter_val_lt), the count of the complement is n - min(n, m).

    lines 6–9

    uses Finset.card_filter_add_card_filter_not, Finset.card_univ, Fintype.card_fin, Fin.card_filter_val_lt

      have h := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin n)))
        (p := fun i : Fin n => (i:ℕ) < m)
      rw [Finset.card_univ, Fintype.card_fin, Fin.card_filter_val_lt] at h
      omega
  2. The chore maximin share for n agents is bounded above by any upper bound C on the bundle costs of a specific partition P.

    The chore maximin share is defined as the infimum over all partitions of the maximum bundle cost. Evaluating at the specific partition P provides an upper bound, as the infimum cannot exceed the maximum bundle cost of P, which is at most C.

    lines 15–16

    uses ciInf_le_of_le, Set.finite_range, ciSup_le

      unfold chore_maximin_share
      exact ciInf_le_of_le (Set.finite_range _).bddBelow P (ciSup_le h)
  3. For a constant unit cost function, the additive valuation of any bundle S is its cardinality |S|.

    By definition, the additive valuation sums the chore costs over S; summing 1 over all elements of S yields |S|.

    line 22

      simp [additive_valuation]
  4. In any 2-agent allocation σ, the cardinalities of the two bundles sum to the total number of chores m.

    The set of all chores is partitioned into those assigned to agent 0 and those not assigned to agent 0. For two agents, every chore not assigned to agent 0 must be assigned to agent 1, so the two bundles partition the universe of size m.

    lines 27–48

    uses Finset.card_filter_add_card_filter_not, Finset.card_univ, Fintype.card_fin, Finset.filter_congr, Fin.isLt, absurd

      have h := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin m)))
        (p := fun g : Fin m => σ g = 0)
      rw [Finset.card_univ, Fintype.card_fin] at h
      have e : Finset.univ.filter (fun g : Fin m => ¬ σ g = 0) = bundle_of σ 1 := by
        simp only [bundle_of]
        apply Finset.filter_congr
        intro g _
        constructor
        · intro hg
          have h2 : σ g = 0 ∨ σ g = 1 := by
            have hv : (σ g : ℕ) < 2 := (σ g).isLt
            omega
          rcases h2 with h' | h'
          · exact absurd h' hg
          · exact h'
        · intro hg h0
          rw [h0] at hg
          simp at hg
      rw [e] at h
      have h0 : bundle_of σ 0 = Finset.univ.filter (fun g : Fin m => σ g = 0) := rfl
      rw [h0]
      omega
  5. In an equal-marginal lottery p, the expected number of chores of any subset A assigned to agent i is |A| / 2.

    Express the intersection size |bundle_of σ i ∩ A| as the sum of indicator variables [σ(g) = i] over chores g ∈ A. Interchanging the order of summation between allocations and chores, the sum over allocations becomes the marginal probability that chore g is given to agent i, which is 1/2 by the equal-marginal hypothesis. Summing 1/2 over all |A| chores yields |A| / 2.

    lines 54–83

    uses Finset.mem_filter, and_comm, Finset.sum_boole, Finset.sum_congr, Finset.mul_sum, Finset.sum_comm, Finset.sum_const, nsmul_eq_mul

      have hcard (σ : Fin m → Fin 2) :
          (∑ g ∈ A, if σ g = i then (1:ℝ) else 0) = (((bundle_of σ i) ∩ A).card : ℝ) := by
        have hset : A.filter (fun g => σ g = i) = (bundle_of σ i) ∩ A := by
          ext g
          simp [bundle_of, Finset.mem_filter, and_comm]
        rw [Finset.sum_boole, hset]
      calc ∑ σ, p σ * (((bundle_of σ i) ∩ A).card : ℝ)
          = ∑ σ, p σ * ∑ g ∈ A, (if σ g = i then (1:ℝ) else 0) := by
            apply Finset.sum_congr rfl
            intro σ _
            rw [hcard σ]
        _ = ∑ σ, ∑ g ∈ A, p σ * (if σ g = i then (1:ℝ) else 0) := by
            apply Finset.sum_congr rfl
            intro σ _
            rw [Finset.mul_sum]
        _ = ∑ g ∈ A, ∑ σ, p σ * (if σ g = i then (1:ℝ) else 0) := Finset.sum_comm
        _ = ∑ g ∈ A, ∑ σ, (if σ g = i then p σ else 0) := by
            apply Finset.sum_congr rfl
            intro g _
            apply Finset.sum_congr rfl
            intro σ _
            by_cases h : σ g = i <;> simp [h]
        _ = ∑ g ∈ A, (1/2 : ℝ) := by
            apply Finset.sum_congr rfl
            intro g _
            rw [hp g i]
            norm_num
        _ = (A.card : ℝ) / 2 := by
            rw [Finset.sum_const, nsmul_eq_mul]
            ring
  6. Agent 1's cost for chore g is r if g < 2t - 1, and 1 otherwise.

    This is the definition of the obstruction cost function for agent 1.

    line 89

      simp [uniform_bivalued_obstruction_cost]
  7. Agent 0's cost for every chore g is 1.

    This is the definition of the obstruction cost function for agent 0.

    line 94

      simp [uniform_bivalued_obstruction_cost]
  8. Agent 1's cost for a bundle equals the bundle's size plus (r - 1) times the number of high chores in the bundle.

    Each chore g has cost 1 + (r - 1) · [g < 2t - 1]. Summing this over all chores in agent 1's bundle, the sum splits into the sum of 1 (the cardinality of the bundle) and (r - 1) times the sum of the indicator for high chores (the cardinality of the intersection with H).

    lines 103–117

    uses uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_apply, Finset.sum_add_distrib, Finset.mul_sum, Finset.sum_const, nsmul_eq_mul, mul_one, Finset.mem_filter, and_comm, Finset.sum_boole

      have hpt : ∀ g : Fin (4*t), uniform_bivalued_obstruction_cost t r 1 g
          = 1 + (r-1) * (if (g:ℕ) < 2*t-1 then (1:ℝ) else 0) := by
        intro g
        rw [uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_apply]
        by_cases h : (g:ℕ) < 2*t-1 <;> simp [h]
      rw [additive_valuation]
      simp_rw [hpt]
      rw [Finset.sum_add_distrib, ← Finset.mul_sum, Finset.sum_const, nsmul_eq_mul, mul_one]
      congr 1
      have hset : (bundle_of σ 1).filter (fun g : Fin (4*t) => (g:ℕ) < 2*t-1)
          = (bundle_of σ 1) ∩ H := by
        rw [hH]
        ext g
        simp [Finset.mem_filter, and_comm]
      rw [← hset, ← Finset.sum_boole]
  9. For 4t unit-cost chores and 2 agents, the chore maximin share is at most 2t.

    Consider the partition P dividing the 4t chores into the first 2t chores and the remaining 2t chores. Both bundles have size 2t, so their cost is 2t under unit costs. By Lemma 2, the chore maximin share is at most 2t.

    lines 122–149

    uses uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_le_of_partition, Finset.filter_congr, Fin.card_filter_val_lt, min_eq_right, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_filter_fin_not_lt, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_additive_valuation_one

      set P : Fin (4*t) → Fin 2 := fun g => if (g:ℕ) < 2*t then 0 else 1 with hP
      refine uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_le_of_partition
        (fun _ => (1:ℝ)) P (2*t) ?_
      have h0 : (bundle_of P 0).card = 2*t := by
        have : bundle_of P 0 = Finset.univ.filter (fun g : Fin (4*t) => (g:ℕ) < 2*t) := by
          simp only [bundle_of, hP]
          apply Finset.filter_congr
          intro g _
          by_cases h : (g:ℕ) < 2*t <;> simp [h]
        rw [this, Fin.card_filter_val_lt, min_eq_right (by omega)]
      have h1 : (bundle_of P 1).card = 2*t := by
        have : bundle_of P 1 = Finset.univ.filter (fun g : Fin (4*t) => ¬ (g:ℕ) < 2*t) := by
          simp only [bundle_of, hP]
          apply Finset.filter_congr
          intro g _
          by_cases h : (g:ℕ) < 2*t <;> simp [h]
        rw [this, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_filter_fin_not_lt,
          min_eq_right (by omega)]
        omega
      intro k
      rw [uniform_bivalued_obstruction_no_equal_marginal_exact_mms_additive_valuation_one]
      have hb : (bundle_of P k).card = 2*t := by
        fin_cases k
        · simpa using h0
        · simpa using h1
      rw [hb]
      push_cast
      linarith
  10. The bounds on the ratio r imply the arithmetic inequalities (2t - 1) * r < t * (1 + r) and 2t + 1 < t * (1 + r). automation

    From r < 1 + 1/(t - 1), multiplying by t - 1 gives (r - 1)(t - 1) < 1, which rearranges to (2t - 1)r < t(1 + r). From r > 1 + 1/t, multiplying by t gives t(r - 1) > 1, which rearranges to 2t + 1 < t(1 + r).

    lines 156–168

    uses Nat.cast_sub, lt_div_iff₀

      have hcast : ((t - 1 : ℕ) : ℝ) = (t : ℝ) - 1 := by
        rw [Nat.cast_sub (by omega : 1 ≤ t)]
        norm_num
      have htR : (2:ℝ) ≤ (t:ℝ) := by exact_mod_cast ht
      have hpos : (0:ℝ) < (t:ℝ) - 1 := by linarith
      have htpos : (0:ℝ) < (t:ℝ) := by linarith
      have harith1 : (2*(t:ℝ) - 1) * r < t * (1 + r) := by
        have h1 : r - 1 < 1 / ((t:ℝ) - 1) := by rw [← hcast]; linarith
        rw [lt_div_iff₀ hpos] at h1
        nlinarith
      have harith2 : 2*(t:ℝ) + 1 < t * (1 + r) := by
        have h1 : (1/(t:ℝ)) * (t:ℝ) = 1 := by field_simp
        nlinarith [hr_lo, htpos]
  11. Under the partition separating the 2t - 1 high chores from the 2t + 1 low chores, the bundle costs for Agent 1 are (2t - 1) * r and 2t + 1.

    Bundle 0 contains all 2t - 1 high chores, each costing r, totaling (2t - 1) * r. Bundle 1 contains the remaining 4t - (2t - 1) = 2t + 1 chores, each costing 1, totaling 2t + 1.

    lines 169–208

    uses Fin.card_filter_val_lt, min_eq_right, Finset.filter_congr, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_apply, Finset.sum_congr, Finset.sum_const, nsmul_eq_mul, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_filter_fin_not_lt

      set H : Finset (Fin (4*t)) := Finset.univ.filter (fun g : Fin (4*t) => (g:ℕ) < 2*t-1) with hH
      have hHcard : H.card = 2*t-1 := by
        rw [hH, Fin.card_filter_val_lt, min_eq_right (by omega)]
      set P : Fin (4*t) → Fin 2 := fun g => if (g:ℕ) < 2*t-1 then 0 else 1 with hP
      have hb0 : bundle_of P 0 = H := by
        simp only [bundle_of, hP, hH]
        apply Finset.filter_congr
        intro g _
        by_cases h : (g:ℕ) < 2*t-1 <;> simp [h]
      have hb1 : bundle_of P 1 = Finset.univ.filter (fun g : Fin (4*t) => ¬ (g:ℕ) < 2*t-1) := by
        simp only [bundle_of, hP]
        apply Finset.filter_congr
        intro g _
        by_cases h : (g:ℕ) < 2*t-1 <;> simp [h]
      have hc0 : additive_valuation (uniform_bivalued_obstruction_cost t r 1) (bundle_of P 0)
          = ((2*t-1 : ℕ) : ℝ) * r := by
        rw [hb0, additive_valuation]
        have hsum : ∀ g ∈ H, uniform_bivalued_obstruction_cost t r 1 g = r := by
          intro g hg
          rw [uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_apply]
          have : (g:ℕ) < 2*t-1 := by simpa [hH] using hg
          simp [this]
        rw [Finset.sum_congr rfl hsum, Finset.sum_const, hHcard, nsmul_eq_mul]
      have hc1 : additive_valuation (uniform_bivalued_obstruction_cost t r 1) (bundle_of P 1)
          = ((2*t+1 : ℕ) : ℝ) := by
        rw [hb1, additive_valuation]
        have hsum : ∀ g ∈ Finset.univ.filter (fun g : Fin (4*t) => ¬ (g:ℕ) < 2*t-1),
            uniform_bivalued_obstruction_cost t r 1 g = (1:ℝ) := by
          intro g hg
          rw [uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_apply]
          have : ¬ (g:ℕ) < 2*t-1 := by simpa using hg
          simp [this]
        rw [Finset.sum_congr rfl hsum, Finset.sum_const,
          uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_filter_fin_not_lt,
          min_eq_right (by omega)]
        have h4 : 4*t - (2*t-1) = 2*t+1 := by omega
        rw [h4]
        push_cast
        ring
      have hmain : chore_maximin_share 2 (uniform_bivalued_obstruction_cost t r 1)
  12. Agent 1's chore maximin share is strictly less than t * (1 + r).

    By Lemma 2, Agent 1's maximin share is bounded by max((2t - 1) * r, 2t + 1). Both arguments of the maximum are strictly less than t * (1 + r) by the arithmetic inequalities from step 10, so the maximum is strictly less than t * (1 + r).

    lines 209–222

    uses uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_le_of_partition, le_max_left, le_max_right, lt_of_le_of_lt, Nat.cast_sub, max_lt_iff

          ≤ max (((2*t-1 : ℕ) : ℝ) * r) (((2*t+1 : ℕ) : ℝ)) := by
        refine uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_le_of_partition _ P _ ?_
        intro k
        have hb : k = 0 ∨ k = 1 := by fin_cases k <;> simp
        rcases hb with h | h
        · rw [h, hc0]; exact le_max_left _ _
        · rw [h, hc1]; exact le_max_right _ _
      refine lt_of_le_of_lt hmain ?_
      have e0 : (((2*t-1 : ℕ)) : ℝ) = 2*(t:ℝ) - 1 := by
        push_cast [Nat.cast_sub (show 1 ≤ 2*t by omega)]
        ring
      have e1 : (((2*t+1 : ℕ)) : ℝ) = 2*(t:ℝ) + 1 := by push_cast; ring
      rw [max_lt_iff]
      exact ⟨by rw [e0]; exact harith1, by rw [e1]; exact harith2⟩
  13. Assuming an equal-marginal exact-MMS lottery exists, Agent 0's maximin share is at most 2t, Agent 1's maximin share is strictly less than t * (1 + r), and there are 2t - 1 high chores.

    Unpack the lottery hypotheses p. Agent 0 faces unit costs on all chores, so Agent 0's MMS is at most 2t by Lemma 9. Agent 1's MMS is strictly less than t * (1 + r) by Lemma 10. The set H of high chores has size 2t - 1.

    lines 231–250

    uses uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_zero_apply, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_const_one_four_mul, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_cost_one_le, Fin.card_filter_val_lt, min_eq_right

      rintro ⟨p, hp_simplex, hp_eq, hp_mms⟩
      obtain ⟨hp_nonneg, hp_sum⟩ := hp_simplex
      set H : Finset (Fin (4*t)) := Finset.univ.filter (fun g : Fin (4*t) => (g:ℕ) < 2*t-1) with hH
      have htpos : (0:ℝ) < (t:ℝ) := by
        have h : (2:ℝ) ≤ (t:ℝ) := by exact_mod_cast ht
        linarith
      have hr1 : 1 < r := by
        have h : (0:ℝ) < 1/(t:ℝ) := by positivity
        linarith
      have hrm1 : 0 < r - 1 := by linarith
      have hc0fun : uniform_bivalued_obstruction_cost t r 0 = fun _ : Fin (4*t) => (1:ℝ) := by
        funext g; exact uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_zero_apply t r g
      have hmms0 : chore_maximin_share 2 (uniform_bivalued_obstruction_cost t r 0) ≤ 2*(t:ℝ) := by
        rw [hc0fun]
        exact uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_const_one_four_mul t ht
      have hmms1 : chore_maximin_share 2 (uniform_bivalued_obstruction_cost t r 1) < (t:ℝ)*(1+r) :=
        uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_cost_one_le t ht r hr_lo hr_hi
      have hHcard : H.card = 2*t-1 := by
        rw [hH, Fin.card_filter_val_lt, min_eq_right (by omega)]
      have hkey : ∀ σ : Fin (4*t) → Fin 2, 0 < p σ →
  14. For every allocation σ in the support of p, Agent 1 receives at most t - 1 high chores.

    Because σ is exact-MMS, Agent 0's cost is at most 2t, so Agent 0 receives at most 2t chores. Since there are 4t chores in total, Agent 1 must receive at least 2t chores. Agent 1's cost is |bundle_of σ 1| + (r - 1) * |bundle_of σ 1 ∩ H|, which is strictly less than t * (1 + r). Combining this with |bundle_of σ 1| ≥ 2t yields (r - 1) * |bundle_of σ 1 ∩ H| < (r - 1) * t. Dividing by r - 1 > 0 gives |bundle_of σ 1 ∩ H| < t, and since cardinality is an integer, this count is at most t - 1.

    lines 251–285

    uses one_mul, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_additive_valuation_one, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_bundle_zero_add_one, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_decomp, lt_of_mul_lt_mul_left, le_of_lt, Nat.cast_sub

          (((bundle_of σ 1) ∩ H).card : ℝ) ≤ (t:ℝ) - 1 := by
        intro σ hσ
        have hσmms : is_alpha_mms_chores 1 (uniform_bivalued_obstruction_cost t r) σ := hp_mms σ hσ
        have h0 : additive_valuation (uniform_bivalued_obstruction_cost t r 0) (bundle_of σ 0)
            ≤ 2*(t:ℝ) := by
          have h := hσmms 0
          simp only [one_mul] at h
          linarith
        rw [hc0fun, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_additive_valuation_one] at h0
        have hb0 : (bundle_of σ 0).card ≤ 2*t := by
          have hcast : ((bundle_of σ 0).card : ℝ) ≤ ((2*t : ℕ) : ℝ) := by push_cast; linarith
          exact_mod_cast hcast
        have hb1 : 2*t ≤ (bundle_of σ 1).card := by
          have hsum := uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_bundle_zero_add_one σ
          omega
        have hb1R : 2*(t:ℝ) ≤ ((bundle_of σ 1).card : ℝ) := by
          have hcast : ((2*t : ℕ) : ℝ) ≤ ((bundle_of σ 1).card : ℝ) := by exact_mod_cast hb1
          push_cast at hcast
          linarith
        have h1 : additive_valuation (uniform_bivalued_obstruction_cost t r 1) (bundle_of σ 1)
            < (t:ℝ)*(1+r) := by
          have h := hσmms 1
          simp only [one_mul] at h
          linarith
        have hdec := uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_decomp r σ H hH
        rw [hdec] at h1
        have hstep : (r-1) * (((bundle_of σ 1) ∩ H).card : ℝ) < (r-1) * (t:ℝ) := by nlinarith
        have hlt : (((bundle_of σ 1) ∩ H).card : ℝ) < (t:ℝ) :=
          lt_of_mul_lt_mul_left hstep (le_of_lt hrm1)
        have hnatlt : ((bundle_of σ 1) ∩ H).card < t := by exact_mod_cast hlt
        have hnat : ((bundle_of σ 1) ∩ H).card ≤ t - 1 := by omega
        have hcast2 : ((t-1 : ℕ) : ℝ) = (t:ℝ) - 1 := by
          rw [Nat.cast_sub (by omega : 1 ≤ t)]; norm_num
        calc (((bundle_of σ 1) ∩ H).card : ℝ) ≤ ((t-1 : ℕ) : ℝ) := by exact_mod_cast hnat
          _ = (t:ℝ) - 1 := hcast2
  15. The expected number of high chores received by Agent 1 under lottery p is at most t - 1.

    Weight each allocation σ by its probability p(σ). For each σ with positive probability, Agent 1 receives at most t - 1 high chores, and allocations with zero probability contribute 0. Summing over all σ and factoring out t - 1, the probabilities sum to 1, bounding the expectation by t - 1.

    lines 286–300

    uses mul_le_mul_of_nonneg_left, le_of_lt, Finset.sum_le_sum, Finset.sum_mul

      have hsum_le : ∑ σ : Fin (4*t) → Fin 2, p σ * (((bundle_of σ 1) ∩ H).card : ℝ)
          ≤ (t:ℝ) - 1 := by
        have hterm : ∀ σ : Fin (4*t) → Fin 2,
            p σ * (((bundle_of σ 1) ∩ H).card : ℝ) ≤ p σ * ((t:ℝ) - 1) := by
          intro σ
          by_cases h : 0 < p σ
          · exact mul_le_mul_of_nonneg_left (hkey σ h) (le_of_lt h)
          · have hpz : p σ = 0 := by
              have hle : p σ ≤ 0 := by linarith [not_lt.mp h, hp_nonneg σ]
              linarith [hp_nonneg σ]
            simp [hpz]
        calc ∑ σ : Fin (4*t) → Fin 2, p σ * (((bundle_of σ 1) ∩ H).card : ℝ)
            ≤ ∑ σ : Fin (4*t) → Fin 2, p σ * ((t:ℝ) - 1) := Finset.sum_le_sum (fun σ _ => hterm σ)
          _ = (∑ σ : Fin (4*t) → Fin 2, p σ) * ((t:ℝ) - 1) := by rw [Finset.sum_mul]
          _ = (t:ℝ) - 1 := by rw [hp_sum]; ring
  16. The expected count of high chores contradicts the equal-marginal property, so no such lottery can exist.

    By Lemma 5, the equal-marginal property implies the expected number of high chores given to Agent 1 is |H| / 2 = (2t - 1) / 2 = t - 1/2. But step 15 proved this expectation is at most t - 1, which implies t - 1/2 ≤ t - 1, an arithmetic contradiction.

    lines 301–311

    uses uniform_bivalued_obstruction_no_equal_marginal_exact_mms_sum_p_mul_card_inter, Nat.cast_sub

      have heq : ∑ σ : Fin (4*t) → Fin 2, p σ * (((bundle_of σ 1) ∩ H).card : ℝ)
          = ((2*t-1 : ℕ) : ℝ) / 2 := by
        rw [uniform_bivalued_obstruction_no_equal_marginal_exact_mms_sum_p_mul_card_inter p hp_eq 1 H,
          hHcard]
      have hcontra : ((2*t-1 : ℕ) : ℝ) / 2 ≤ (t:ℝ) - 1 := by
        rw [← heq]; exact hsum_le
      have e0 : (((2*t-1 : ℕ)) : ℝ) = 2*(t:ℝ) - 1 := by
        push_cast [Nat.cast_sub (show 1 ≤ 2*t by omega)]
        ring
      rw [e0] at hcontra
      linarith
and_comm
Logical conjunction is commutative: a ∧ b ↔ b ∧ a.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.card_univ
The cardinality of the universal set of a finite type is the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
Fin.card_filter_val_lt
The number of elements of Fin n with value strictly less than m is min(n, m).
Finset.card_filter_add_card_filter_not
For any finite set and predicate, the number of elements satisfying the predicate plus the number of elements not satisfying it equals the size of the set.
Finset.filter_congr
Two filterings of the same set are equal if their predicates are equivalent on all elements of the set.
Fin.isLt
For any element i of Fin n, its numerical value satisfies i < n.
absurd
A false hypothesis implies any conclusion.
ciInf_le_of_le
In a conditionally complete lattice, an infimum is bounded above by a value if the range is bounded below and some witness achieves at most that value.
Set.finite_range
The range of a function from a finite type is a finite set.
ciSup_le
In a conditionally complete lattice, a supremum is bounded above by c if every element is bounded above by c.
Finset.sum_boole
The sum of an indicator function over a finite set equals the cardinality of the subset of elements satisfying the condition.
Finset.sum_congr
Two finite sums are equal if their index sets agree and their summands agree on every element.
Finset.mul_sum
Multiplication by a scalar distributes over a finite sum from the left.
Finset.sum_comm
The order of summation in a double finite sum may be exchanged.
Finset.sum_const
The sum of a constant value b over a finite set s equals |s| • b.
nsmul_eq_mul
Scalar multiplication by a natural number n equals standard multiplication by n.
Finset.sum_add_distrib
The sum of a sum of functions over a finite set equals the sum of the individual sums.
mul_one
Multiplying any element by 1 leaves it unchanged.
uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_le_of_partition
If all bundle costs in a partition are at most C, the chore maximin share is at most C.
min_eq_right
If b ≤ a, then min(a, b) = b.
uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_filter_fin_not_lt
The number of elements of Fin n with value at least m is n - min(n, m).
uniform_bivalued_obstruction_no_equal_marginal_exact_mms_additive_valuation_one
For a constant unit cost function, the additive valuation of a bundle is its cardinality.
uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_apply
Agent 1's cost for chore g is r if g < 2t - 1, and 1 otherwise.
uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_zero_apply
Agent 0's cost for any chore is 1.
uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_bundle_zero_add_one
In any 2-agent allocation, the cardinalities of the two bundles sum to the total number of chores.
uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_decomp
Agent 1's cost for a bundle equals its cardinality plus (r - 1) times the number of high-cost chores it contains.
uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_const_one_four_mul
For 4t unit-cost chores, the 2-agent chore maximin share is at most 2t.
uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_cost_one_le
Agent 1's chore maximin share is strictly less than t * (1 + r).
Nat.cast_sub
For natural numbers with m ≤ n, the real cast of n - m equals the real cast of n minus the real cast of m.
lt_div_iff₀
For positive c, a < b / c if and only if a * c < b.
le_max_left
Any element a is at most max(a, b).
le_max_right
Any element b is at most max(a, b).
lt_of_le_of_lt
If a ≤ b and b < c, then a < c.
max_lt_iff
The maximum of two values is strictly less than a if and only if both values are strictly less than a.
one_mul
Multiplying by 1 on the left leaves an element unchanged.
lt_of_mul_lt_mul_left
If a * b < a * c and 0 ≤ a, then b < c.
le_of_lt
If a < b, then a ≤ b.
mul_le_mul_of_nonneg_left
If b ≤ c and 0 ≤ a, then a * b ≤ a * c.
Finset.sum_le_sum
If f(i) ≤ g(i) for all i in a finite set, then the sum of f is at most the sum of g.
Finset.sum_mul
Multiplication by a scalar distributes over a finite sum from the right.
uniform_bivalued_obstruction_no_equal_marginal_exact_mms_sum_p_mul_card_inter
In an equal-marginal lottery, the expected number of chores of any subset assigned to an agent is half the size of the subset.

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

open Finset/-- Complement count of the "first m" elements of `Fin n`. -/lemma uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_filter_fin_not_lt (n m : ℕ) :    (Finset.univ.filter (fun i : Fin n => ¬ (i:ℕ) < m)).card = n - min n m := by  have h := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin n)))    (p := fun i : Fin n => (i:ℕ) < m)  rw [Finset.card_univ, Fintype.card_fin, Fin.card_filter_val_lt] at h  omega/-- The chore maximin share is at most the maximum bundle cost of any fixed partition. -/lemma uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_le_of_partition {m n : ℕ}    [NeZero n] (u : Fin m → ℝ) (P : Fin m → Fin n) (C : ℝ)    (h : ∀ k, additive_valuation u (bundle_of P k) ≤ C) : chore_maximin_share n u ≤ C := by  unfold chore_maximin_share  exact ciInf_le_of_le (Set.finite_range _).bddBelow P (ciSup_le h)/-- For unit costs the additive valuation of a bundle is its cardinality. -/lemma uniform_bivalued_obstruction_no_equal_marginal_exact_mms_additive_valuation_one (m : ℕ)    (S : Finset (Fin m)) :    additive_valuation (fun _ => (1:ℝ)) S = (S.card : ℝ) := by  simp [additive_valuation]/-- The two bundles of a two-agent allocation partition all chores. -/lemma uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_bundle_zero_add_one {m : ℕ}    (σ : Fin m → Fin 2) : (bundle_of σ 0).card + (bundle_of σ 1).card = m := by  have h := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin m)))    (p := fun g : Fin m => σ g = 0)  rw [Finset.card_univ, Fintype.card_fin] at h  have e : Finset.univ.filter (fun g : Fin m => ¬ σ g = 0) = bundle_of σ 1 := by    simp only [bundle_of]    apply Finset.filter_congr    intro g _    constructor    · intro hg      have h2 : σ g = 0 ∨ σ g = 1 := by        have hv : (σ g : ℕ) < 2 := (σ g).isLt        omega      rcases h2 with h' | h'      · exact absurd h' hg      · exact h'    · intro hg h0      rw [h0] at hg      simp at hg  rw [e] at h  have h0 : bundle_of σ 0 = Finset.univ.filter (fun g : Fin m => σ g = 0) := rfl  rw [h0]  omega/-- In an equal-marginal lottery the expected number of chores of `A` given to agent `i` is `|A|/2`. -/lemma uniform_bivalued_obstruction_no_equal_marginal_exact_mms_sum_p_mul_card_inter {m : ℕ}    (p : (Fin m → Fin 2) → ℝ) (hp : is_equal_marginal_lottery p) (i : Fin 2) (A : Finset (Fin m)) :    ∑ σ, p σ * (((bundle_of σ i) ∩ A).card : ℝ) = (A.card : ℝ) / 2 := by  have hcard (σ : Fin m → Fin 2) :      (∑ g ∈ A, if σ g = i then (1:ℝ) else 0) = (((bundle_of σ i) ∩ A).card : ℝ) := by    have hset : A.filter (fun g => σ g = i) = (bundle_of σ i) ∩ A := by      ext g      simp [bundle_of, Finset.mem_filter, and_comm]    rw [Finset.sum_boole, hset]  calc ∑ σ, p σ * (((bundle_of σ i) ∩ A).card : ℝ)      = ∑ σ, p σ * ∑ g ∈ A, (if σ g = i then (1:ℝ) else 0) := by        apply Finset.sum_congr rfl        intro σ _        rw [hcard σ]    _ = ∑ σ, ∑ g ∈ A, p σ * (if σ g = i then (1:ℝ) else 0) := by        apply Finset.sum_congr rfl        intro σ _        rw [Finset.mul_sum]    _ = ∑ g ∈ A, ∑ σ, p σ * (if σ g = i then (1:ℝ) else 0) := Finset.sum_comm    _ = ∑ g ∈ A, ∑ σ, (if σ g = i then p σ else 0) := by        apply Finset.sum_congr rfl        intro g _        apply Finset.sum_congr rfl        intro σ _        by_cases h : σ g = i <;> simp [h]    _ = ∑ g ∈ A, (1/2 : ℝ) := by        apply Finset.sum_congr rfl        intro g _        rw [hp g i]        norm_num    _ = (A.card : ℝ) / 2 := by        rw [Finset.sum_const, nsmul_eq_mul]        ring/-- Agent 1's cost of a chore: `r` on the high chores, `1` elsewhere. -/lemma uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_apply (t : ℕ) (r : ℝ)    (g : Fin (4*t)) :    uniform_bivalued_obstruction_cost t r 1 g = if (g:ℕ) < 2*t-1 then r else 1 := by  simp [uniform_bivalued_obstruction_cost]/-- Agent 0's cost is one on every chore. -/lemma uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_zero_apply (t : ℕ) (r : ℝ)    (g : Fin (4*t)) : uniform_bivalued_obstruction_cost t r 0 g = 1 := by  simp [uniform_bivalued_obstruction_cost]/-- Agent 1's cost of a bundle: its size plus `(r-1)` times its number of high chores. -/lemma uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_decomp {t : ℕ} (r : ℝ)    (σ : Fin (4*t) → Fin 2) (H : Finset (Fin (4*t)))    (hH : H = Finset.univ.filter (fun g : Fin (4*t) => (g:ℕ) < 2*t-1)) :    additive_valuation (uniform_bivalued_obstruction_cost t r 1) (bundle_of σ 1)      = ((bundle_of σ 1).card : ℝ)        + (r - 1) * (((bundle_of σ 1) ∩ H).card : ℝ) := by  have hpt : ∀ g : Fin (4*t), uniform_bivalued_obstruction_cost t r 1 g      = 1 + (r-1) * (if (g:ℕ) < 2*t-1 then (1:ℝ) else 0) := by    intro g    rw [uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_apply]    by_cases h : (g:ℕ) < 2*t-1 <;> simp [h]  rw [additive_valuation]  simp_rw [hpt]  rw [Finset.sum_add_distrib, ← Finset.mul_sum, Finset.sum_const, nsmul_eq_mul, mul_one]  congr 1  have hset : (bundle_of σ 1).filter (fun g : Fin (4*t) => (g:ℕ) < 2*t-1)      = (bundle_of σ 1) ∩ H := by    rw [hH]    ext g    simp [Finset.mem_filter, and_comm]  rw [← hset, ← Finset.sum_boole]/-- For `4t` unit-cost chores and two agents the maximin share is at most `2t`. -/lemma uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_const_one_four_mul (t : ℕ)    (ht : 2 ≤ t) : chore_maximin_share 2 (fun _ : Fin (4*t) => (1:ℝ)) ≤ 2 * t := by  set P : Fin (4*t) → Fin 2 := fun g => if (g:ℕ) < 2*t then 0 else 1 with hP  refine uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_le_of_partition    (fun _ => (1:ℝ)) P (2*t) ?_  have h0 : (bundle_of P 0).card = 2*t := by    have : bundle_of P 0 = Finset.univ.filter (fun g : Fin (4*t) => (g:ℕ) < 2*t) := by      simp only [bundle_of, hP]      apply Finset.filter_congr      intro g _      by_cases h : (g:ℕ) < 2*t <;> simp [h]    rw [this, Fin.card_filter_val_lt, min_eq_right (by omega)]  have h1 : (bundle_of P 1).card = 2*t := by    have : bundle_of P 1 = Finset.univ.filter (fun g : Fin (4*t) => ¬ (g:ℕ) < 2*t) := by      simp only [bundle_of, hP]      apply Finset.filter_congr      intro g _      by_cases h : (g:ℕ) < 2*t <;> simp [h]    rw [this, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_filter_fin_not_lt,      min_eq_right (by omega)]    omega  intro k  rw [uniform_bivalued_obstruction_no_equal_marginal_exact_mms_additive_valuation_one]  have hb : (bundle_of P k).card = 2*t := by    fin_cases k    · simpa using h0    · simpa using h1  rw [hb]  push_cast  linarith/-- Agent 1's maximin share in this instance is at most `t*(1+r)`: put all high chores in onebundle and all low chores in the other. -/lemma uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_cost_one_le (t : ℕ) (ht : 2 ≤ t)    (r : ℝ) (hr_lo : 1 + 1 / (t : ℝ) < r) (hr_hi : r < 1 + 1 / ((t - 1 : ℕ) : ℝ)) :    chore_maximin_share 2 (uniform_bivalued_obstruction_cost t r 1) < t * (1 + r) := by  have hcast : ((t - 1 : ℕ) : ℝ) = (t : ℝ) - 1 := by    rw [Nat.cast_sub (by omega : 1 ≤ t)]    norm_num  have htR : (2:ℝ) ≤ (t:ℝ) := by exact_mod_cast ht  have hpos : (0:ℝ) < (t:ℝ) - 1 := by linarith  have htpos : (0:ℝ) < (t:ℝ) := by linarith  have harith1 : (2*(t:ℝ) - 1) * r < t * (1 + r) := by    have h1 : r - 1 < 1 / ((t:ℝ) - 1) := by rw [← hcast]; linarith    rw [lt_div_iff₀ hpos] at h1    nlinarith  have harith2 : 2*(t:ℝ) + 1 < t * (1 + r) := by    have h1 : (1/(t:ℝ)) * (t:ℝ) = 1 := by field_simp    nlinarith [hr_lo, htpos]  set H : Finset (Fin (4*t)) := Finset.univ.filter (fun g : Fin (4*t) => (g:ℕ) < 2*t-1) with hH  have hHcard : H.card = 2*t-1 := by    rw [hH, Fin.card_filter_val_lt, min_eq_right (by omega)]  set P : Fin (4*t) → Fin 2 := fun g => if (g:ℕ) < 2*t-1 then 0 else 1 with hP  have hb0 : bundle_of P 0 = H := by    simp only [bundle_of, hP, hH]    apply Finset.filter_congr    intro g _    by_cases h : (g:ℕ) < 2*t-1 <;> simp [h]  have hb1 : bundle_of P 1 = Finset.univ.filter (fun g : Fin (4*t) => ¬ (g:ℕ) < 2*t-1) := by    simp only [bundle_of, hP]    apply Finset.filter_congr    intro g _    by_cases h : (g:ℕ) < 2*t-1 <;> simp [h]  have hc0 : additive_valuation (uniform_bivalued_obstruction_cost t r 1) (bundle_of P 0)      = ((2*t-1 : ℕ) : ℝ) * r := by    rw [hb0, additive_valuation]    have hsum : ∀ g ∈ H, uniform_bivalued_obstruction_cost t r 1 g = r := by      intro g hg      rw [uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_apply]      have : (g:ℕ) < 2*t-1 := by simpa [hH] using hg      simp [this]    rw [Finset.sum_congr rfl hsum, Finset.sum_const, hHcard, nsmul_eq_mul]  have hc1 : additive_valuation (uniform_bivalued_obstruction_cost t r 1) (bundle_of P 1)      = ((2*t+1 : ℕ) : ℝ) := by    rw [hb1, additive_valuation]    have hsum : ∀ g ∈ Finset.univ.filter (fun g : Fin (4*t) => ¬ (g:ℕ) < 2*t-1),        uniform_bivalued_obstruction_cost t r 1 g = (1:ℝ) := by      intro g hg      rw [uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_apply]      have : ¬ (g:ℕ) < 2*t-1 := by simpa using hg      simp [this]    rw [Finset.sum_congr rfl hsum, Finset.sum_const,      uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_filter_fin_not_lt,      min_eq_right (by omega)]    have h4 : 4*t - (2*t-1) = 2*t+1 := by omega    rw [h4]    push_cast    ring  have hmain : chore_maximin_share 2 (uniform_bivalued_obstruction_cost t r 1)      ≤ max (((2*t-1 : ℕ) : ℝ) * r) (((2*t+1 : ℕ) : ℝ)) := by    refine uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_le_of_partition _ P _ ?_    intro k    have hb : k = 0 ∨ k = 1 := by fin_cases k <;> simp    rcases hb with h | h    · rw [h, hc0]; exact le_max_left _ _    · rw [h, hc1]; exact le_max_right _ _  refine lt_of_le_of_lt hmain ?_  have e0 : (((2*t-1 : ℕ)) : ℝ) = 2*(t:ℝ) - 1 := by    push_cast [Nat.cast_sub (show 1 ≤ 2*t by omega)]    ring  have e1 : (((2*t+1 : ℕ)) : ℝ) = 2*(t:ℝ) + 1 := by push_cast; ring  rw [max_lt_iff]  exact ⟨by rw [e0]; exact harith1, by rw [e1]; exact harith2⟩/-- For integer t >= 2 and ratio r strictly between 1 + 1/t and 1 + 1/(t-1), the 4t-chore obstruction instance admits no equal-marginal exact-MMS lottery. -/theorem uniform_bivalued_obstruction_no_equal_marginal_exact_mms    (t : ℕ) (ht : 2 ≤ t)    (r : ℝ) (hr_lo : 1 + 1 / (t : ℝ) < r) (hr_hi : r < 1 + 1 / ((t - 1 : ℕ) : ℝ)) :    ¬ ∃ p ∈ stdSimplex ℝ (Fin (4 * t) → Fin 2),      is_equal_marginal_lottery p ∧      is_ex_post_alpha_mms_chores 1 (uniform_bivalued_obstruction_cost t r) p := by  rintro ⟨p, hp_simplex, hp_eq, hp_mms⟩  obtain ⟨hp_nonneg, hp_sum⟩ := hp_simplex  set H : Finset (Fin (4*t)) := Finset.univ.filter (fun g : Fin (4*t) => (g:ℕ) < 2*t-1) with hH  have htpos : (0:ℝ) < (t:ℝ) := by    have h : (2:ℝ) ≤ (t:ℝ) := by exact_mod_cast ht    linarith  have hr1 : 1 < r := by    have h : (0:ℝ) < 1/(t:ℝ) := by positivity    linarith  have hrm1 : 0 < r - 1 := by linarith  have hc0fun : uniform_bivalued_obstruction_cost t r 0 = fun _ : Fin (4*t) => (1:ℝ) := by    funext g; exact uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_zero_apply t r g  have hmms0 : chore_maximin_share 2 (uniform_bivalued_obstruction_cost t r 0) ≤ 2*(t:ℝ) := by    rw [hc0fun]    exact uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_const_one_four_mul t ht  have hmms1 : chore_maximin_share 2 (uniform_bivalued_obstruction_cost t r 1) < (t:ℝ)*(1+r) :=    uniform_bivalued_obstruction_no_equal_marginal_exact_mms_mms_cost_one_le t ht r hr_lo hr_hi  have hHcard : H.card = 2*t-1 := by    rw [hH, Fin.card_filter_val_lt, min_eq_right (by omega)]  have hkey : ∀ σ : Fin (4*t) → Fin 2, 0 < p σ →      (((bundle_of σ 1) ∩ H).card : ℝ) ≤ (t:ℝ) - 1 := by    intro σ hσ    have hσmms : is_alpha_mms_chores 1 (uniform_bivalued_obstruction_cost t r) σ := hp_mms σ hσ    have h0 : additive_valuation (uniform_bivalued_obstruction_cost t r 0) (bundle_of σ 0)        ≤ 2*(t:ℝ) := by      have h := hσmms 0      simp only [one_mul] at h      linarith    rw [hc0fun, uniform_bivalued_obstruction_no_equal_marginal_exact_mms_additive_valuation_one] at h0    have hb0 : (bundle_of σ 0).card ≤ 2*t := by      have hcast : ((bundle_of σ 0).card : ℝ) ≤ ((2*t : ℕ) : ℝ) := by push_cast; linarith      exact_mod_cast hcast    have hb1 : 2*t ≤ (bundle_of σ 1).card := by      have hsum := uniform_bivalued_obstruction_no_equal_marginal_exact_mms_card_bundle_zero_add_one σ      omega    have hb1R : 2*(t:ℝ) ≤ ((bundle_of σ 1).card : ℝ) := by      have hcast : ((2*t : ℕ) : ℝ) ≤ ((bundle_of σ 1).card : ℝ) := by exact_mod_cast hb1      push_cast at hcast      linarith    have h1 : additive_valuation (uniform_bivalued_obstruction_cost t r 1) (bundle_of σ 1)        < (t:ℝ)*(1+r) := by      have h := hσmms 1      simp only [one_mul] at h      linarith    have hdec := uniform_bivalued_obstruction_no_equal_marginal_exact_mms_cost_one_decomp r σ H hH    rw [hdec] at h1    have hstep : (r-1) * (((bundle_of σ 1) ∩ H).card : ℝ) < (r-1) * (t:ℝ) := by nlinarith    have hlt : (((bundle_of σ 1) ∩ H).card : ℝ) < (t:ℝ) :=      lt_of_mul_lt_mul_left hstep (le_of_lt hrm1)    have hnatlt : ((bundle_of σ 1) ∩ H).card < t := by exact_mod_cast hlt    have hnat : ((bundle_of σ 1) ∩ H).card ≤ t - 1 := by omega    have hcast2 : ((t-1 : ℕ) : ℝ) = (t:ℝ) - 1 := by      rw [Nat.cast_sub (by omega : 1 ≤ t)]; norm_num    calc (((bundle_of σ 1) ∩ H).card : ℝ) ≤ ((t-1 : ℕ) : ℝ) := by exact_mod_cast hnat      _ = (t:ℝ) - 1 := hcast2  have hsum_le : ∑ σ : Fin (4*t) → Fin 2, p σ * (((bundle_of σ 1) ∩ H).card : ℝ)      ≤ (t:ℝ) - 1 := by    have hterm : ∀ σ : Fin (4*t) → Fin 2,        p σ * (((bundle_of σ 1) ∩ H).card : ℝ) ≤ p σ * ((t:ℝ) - 1) := by      intro σ      by_cases h : 0 < p σ      · exact mul_le_mul_of_nonneg_left (hkey σ h) (le_of_lt h)      · have hpz : p σ = 0 := by          have hle : p σ ≤ 0 := by linarith [not_lt.mp h, hp_nonneg σ]          linarith [hp_nonneg σ]        simp [hpz]    calc ∑ σ : Fin (4*t) → Fin 2, p σ * (((bundle_of σ 1) ∩ H).card : ℝ)        ≤ ∑ σ : Fin (4*t) → Fin 2, p σ * ((t:ℝ) - 1) := Finset.sum_le_sum (fun σ _ => hterm σ)      _ = (∑ σ : Fin (4*t) → Fin 2, p σ) * ((t:ℝ) - 1) := by rw [Finset.sum_mul]      _ = (t:ℝ) - 1 := by rw [hp_sum]; ring  have heq : ∑ σ : Fin (4*t) → Fin 2, p σ * (((bundle_of σ 1) ∩ H).card : ℝ)      = ((2*t-1 : ℕ) : ℝ) / 2 := by    rw [uniform_bivalued_obstruction_no_equal_marginal_exact_mms_sum_p_mul_card_inter p hp_eq 1 H,      hHcard]  have hcontra : ((2*t-1 : ℕ) : ℝ) / 2 ≤ (t:ℝ) - 1 := by    rw [← heq]; exact hsum_le  have e0 : (((2*t-1 : ℕ)) : ℝ) = 2*(t:ℝ) - 1 := by    push_cast [Nat.cast_sub (show 1 ≤ 2*t by omega)]    ring  rw [e0] at hcontra  linarith
See it in the graphDiscuss this resultChallenge it