uniform_bivalued_obstruction_no_equal_marginal_exact_mms
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.
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).
uses
Finset.card_filter_add_card_filter_not,Finset.card_univ,Fintype.card_fin,Fin.card_filter_val_lthave 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 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.
uses
ciInf_le_of_le,Set.finite_range,ciSup_leunfold chore_maximin_share exact ciInf_le_of_le (Set.finite_range _).bddBelow P (ciSup_le h)
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|.
simp [additive_valuation]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.
uses
Finset.card_filter_add_card_filter_not,Finset.card_univ,Fintype.card_fin,Finset.filter_congr,Fin.isLt,absurdhave 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 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.
uses
Finset.mem_filter,and_comm,Finset.sum_boole,Finset.sum_congr,Finset.mul_sum,Finset.sum_comm,Finset.sum_const,nsmul_eq_mulhave 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 for chore g is r if g < 2t - 1, and 1 otherwise.
This is the definition of the obstruction cost function for agent 1.
simp [uniform_bivalued_obstruction_cost]Agent 0's cost for every chore g is 1.
This is the definition of the obstruction cost function for agent 0.
simp [uniform_bivalued_obstruction_cost]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).
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_boolehave 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 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.
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_oneset 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
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).
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]
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.
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_ltset 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)
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).
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⟩
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.
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_rightrintro ⟨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 σ →
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.
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
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.
uses
mul_le_mul_of_nonneg_left,le_of_lt,Finset.sum_le_sum,Finset.sum_mulhave 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
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.
uses
uniform_bivalued_obstruction_no_equal_marginal_exact_mms_sum_p_mul_card_inter,Nat.cast_subhave 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.
- The algebraic inequalities relating r, t, and bundle costs in Lemma 10 are verified using non-linear arithmetic automation (nlinarith).
- Bundle cardinality accounting and Fin 2 case analyses rely on the omega and fin_cases automation tactics.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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