two_agent_common_bivalued_safe_partition
For any ratio r with 1 ≤ r ≤ 2, any number of chores m, and any two-agent chore cost profile c satisfying is_scaled_bivalued_chores r c, there exists a subset S of chores such that for each agent i : Fin 2, both S and its complement Finset.univ \ S have additive cost at most ((r + 1) / 2) * chore_maximin_share 2 (c i).
Statement
theorem two_agent_common_bivalued_safe_partition
(r : ℝ) (hr1 : 1 ≤ r) (hr2 : r ≤ 2)
(m : ℕ) (c : Fin 2 → Fin m → ℝ)
(hc : is_scaled_bivalued_chores r c) :
∃ S : Finset (Fin m),
∀ 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)- Formalizes
- arXiv:2409.13680
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- 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…
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- bivalued_rounding_odd_mms_arithmeticThe odd-count MMS lower bound dominates the cost bound for a balanced bundle.
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- bivalued_rounding_even_mms_arithmeticThe even-count MMS lower bound dominates the cost bound for a balanced bundle.
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
For any real number $r$ with $1 \le r \le 2$, any natural number $m$ (of chores), and any cost function $c : \text{Fin } 2 \to \text{Fin } m \to \mathbb{R}$ that is scaled bivalued with ratio $r$ (meaning there exist positive constants $a_i > 0$ for each agent $i \in \{0, 1\}$ such that every chore's cost to agent $i$ is either $a_i$ or $r \cdot a_i$): There exists a subset of chores $S \subseteq \text{Fin } m$ such that for both agents $i \in \{0, 1\}$, the additive cost of $S$ to agent $i$ and the additive cost of the complement $\text{Fin } m \setminus S$ to agent $i$ are each at most $\frac{r + 1}{2}$ times agent $i$'s 2-agent chore maximin share (the minimum over all 2-partitions of chores of the maximum bundle cost for agent $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
To find a chore partition (S, S^c) ensuring that neither bundle costs either agent more than ((r + 1) / 2) * MMS_i, the chores are first divided into four pairwise disjoint sets based on whether they are high-cost for neither, agent 1 only, agent 0 only, or both agents. A combinatorial counting lemma establishes that sub-bundles can be chosen from each part to simultaneously round the total chore count and each agent's high-chore count to at most half plus one half. Lower bounds on the 2-agent chore maximin share are proved for even and odd chore counts by analyzing the average bundle cost and the pigeonhole principle respectively. Finally, dedicated arithmetic lemmas for even and odd counts show that the rounded bundle costs do not exceed ((r + 1) / 2) times these maximin share lower bounds.
For any four bucket sizes, there exist sub-counts that bisect the total and both marginal sums up to an error of at most 1. automation
Decomposing each n_ij into quotient and remainder modulo 2 yields 16 parity combinations. In each combination, choosing each sub-count as either the quotient or quotient plus one satisfies all ten required linear inequalities, verified by the linear integer arithmetic decision procedure omega.
obtain ⟨u00, e00, he00, rfl⟩ : ∃ u e : ℕ, e ≤ 1 ∧ n00 = 2 * u + e := ⟨n00 / 2, n00 % 2, by omega, by omega⟩ obtain ⟨u01, e01, he01, rfl⟩ : ∃ u e : ℕ, e ≤ 1 ∧ n01 = 2 * u + e := ⟨n01 / 2, n01 % 2, by omega, by omega⟩ obtain ⟨u10, e10, he10, rfl⟩ : ∃ u e : ℕ, e ≤ 1 ∧ n10 = 2 * u + e := ⟨n10 / 2, n10 % 2, by omega, by omega⟩ obtain ⟨u11, e11, he11, rfl⟩ : ∃ u e : ℕ, e ≤ 1 ∧ n11 = 2 * u + e := ⟨n11 / 2, n11 % 2, by omega, by omega⟩ interval_cases e00 <;> interval_cases e01 <;> interval_cases e10 <;> interval_cases e11 all_goals first | exact ⟨u00, u01, u10, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00 + 1, u01, u10, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00, u01 + 1, u10, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00, u01, u10 + 1, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00, u01, u10, u11 + 1, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00 + 1, u01 + 1, u10, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00 + 1, u01, u10 + 1, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00, u01 + 1, u10 + 1, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩
The cardinality of the union of four pairwise disjoint finite sets is the sum of their individual cardinalities.
Disjointness distributes over unions, showing successively that A ∪ B is disjoint from D, A ∪ B is disjoint from C, and (A ∪ B) ∪ C is disjoint from D. Applying the cardinality addition formula for disjoint unions three times establishes the claim.
uses
Finset.disjoint_union_left.mpr,Finset.card_union_of_disjointhave hABD : Disjoint (A ∪ B) D := Finset.disjoint_union_left.mpr ⟨hAD, hBD⟩ have hABC : Disjoint (A ∪ B) C := Finset.disjoint_union_left.mpr ⟨hAC, hBC⟩ have h2 : Disjoint ((A ∪ B) ∪ C) D := Finset.disjoint_union_left.mpr ⟨hABD, hCD⟩ rw [Finset.card_union_of_disjoint h2, Finset.card_union_of_disjoint hABC, Finset.card_union_of_disjoint hAB]
The universe of m chores is partitioned into four pairwise disjoint subsets according to the high-cost status for each agent.
We define A = (H0 ∪ H1)^c, B = H1 \ H0, C = H0 \ H1, and D = H0 ∩ H1. Pointwise logical equivalences confirm that their union is the entire universe, that all pairs are disjoint, and that H0 = C ∪ D while H1 = B ∪ D.
uses
Finset.mem_union,Finset.mem_univ,iff_true,Finset.disjoint_leftclassical obtain ⟨A, B, C, D, hAdef, hBdef, hCdef, hDdef, hpart, dAB, dAC, dAD, dBC, dBD, dCD, hH0, hH1⟩ : ∃ A B C D : Finset (Fin m), A = Finset.univ \ (H0 ∪ H1) ∧ B = H1 \ H0 ∧ C = H0 \ H1 ∧ D = H0 ∩ H1 ∧ A ∪ B ∪ C ∪ D = Finset.univ ∧ Disjoint A B ∧ Disjoint A C ∧ Disjoint A D ∧ Disjoint B C ∧ Disjoint B D ∧ Disjoint C D ∧ H0 = C ∪ D ∧ H1 = B ∪ D := by refine ⟨Finset.univ \ (H0 ∪ H1), H1 \ H0, H0 \ H1, H0 ∩ H1, rfl, rfl, rfl, rfl, ?_⟩ have mA : ∀ x : Fin m, x ∈ (Finset.univ \ (H0 ∪ H1) : Finset (Fin m)) ↔ x ∉ H0 ∧ x ∉ H1 := fun x => by simp have mB : ∀ x : Fin m, x ∈ (H1 \ H0 : Finset (Fin m)) ↔ x ∈ H1 ∧ x ∉ H0 := fun x => by simp have mC : ∀ x : Fin m, x ∈ (H0 \ H1 : Finset (Fin m)) ↔ x ∈ H0 ∧ x ∉ H1 := fun x => by simp have mD : ∀ x : Fin m, x ∈ (H0 ∩ H1 : Finset (Fin m)) ↔ x ∈ H0 ∧ x ∈ H1 := fun x => by simp refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ · ext x have a := mA x; have b := mB x; have c := mC x; have d := mD x simp only [Finset.mem_union, Finset.mem_univ, iff_true] tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mA x).1 hx; have h2 := (mB x).1 hy; tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mA x).1 hx; have h2 := (mC x).1 hy; tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mA x).1 hx; have h2 := (mD x).1 hy; tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mB x).1 hx; have h2 := (mC x).1 hy; tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mB x).1 hx; have h2 := (mD x).1 hy; tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mC x).1 hx; have h2 := (mD x).1 hy; tauto · ext x have c := mC x; have d := mD x simp only [Finset.mem_union] tauto · ext x have b := mB x; have d := mD x simp only [Finset.mem_union] tauto
There exist sub-bundles A' ⊆ A, B' ⊆ B, C' ⊆ C, D' ⊆ D whose cardinalities satisfy the balanced counting inequalities.
We apply the counting lemma to the sizes of A, B, C, and D to obtain integer counts a, b, c, d satisfying the balance bounds. Subsets of these exact sizes exist because each count is bounded by the size of the corresponding set.
uses
two_agent_common_bivalued_safe_partition_counts,Finset.exists_subset_card_eqobtain ⟨a, b, c, d, ha, hb, hc, hd, e1, e2, e3, e4, e5, e6⟩ := two_agent_common_bivalued_safe_partition_counts A.card B.card C.card D.card obtain ⟨A', hA'sub, hA'card⟩ := Finset.exists_subset_card_eq ha obtain ⟨B', hB'sub, hB'card⟩ := Finset.exists_subset_card_eq hb obtain ⟨C', hC'sub, hC'card⟩ := Finset.exists_subset_card_eq hc obtain ⟨D', hD'sub, hD'card⟩ := Finset.exists_subset_card_eq hd
For S = A' ∪ B' ∪ C' ∪ D', the intersections S ∩ H0 and S ∩ H1 have cardinalities c + d and b + d respectively.
Elements of A' and B' do not belong to H0, whereas elements of C' and D' belong to H0, so S ∩ H0 = C' ∪ D'. Since C' and D' are disjoint, its size is c + d. A symmetric argument gives S ∩ H1 = B' ∪ D' of size b + d.
uses
Finset.mem_sdiff,Finset.mem_union,Finset.mem_univ,not_or,true_and,Finset.mem_inter,Finset.card_union_of_disjointhave eA0 : ∀ x, x ∈ A' → x ∉ H0 := by intro x hx have h : x ∈ A := hA'sub hx rw [hAdef] at h simp only [Finset.mem_sdiff, Finset.mem_union, Finset.mem_univ, not_or, true_and] at h exact h.1 have eA1 : ∀ x, x ∈ A' → x ∉ H1 := by intro x hx have h : x ∈ A := hA'sub hx rw [hAdef] at h simp only [Finset.mem_sdiff, Finset.mem_union, Finset.mem_univ, not_or, true_and] at h exact h.2 have eB0 : ∀ x, x ∈ B' → x ∉ H0 := by intro x hx have h : x ∈ B := hB'sub hx rw [hBdef] at h simp only [Finset.mem_sdiff] at h exact h.2 have eB1 : ∀ x, x ∈ B' → x ∈ H1 := by intro x hx have h : x ∈ B := hB'sub hx rw [hBdef] at h simp only [Finset.mem_sdiff] at h exact h.1 have eC0 : ∀ x, x ∈ C' → x ∈ H0 := by intro x hx have h : x ∈ C := hC'sub hx rw [hCdef] at h simp only [Finset.mem_sdiff] at h exact h.1 have eC1 : ∀ x, x ∈ C' → x ∉ H1 := by intro x hx have h : x ∈ C := hC'sub hx rw [hCdef] at h simp only [Finset.mem_sdiff] at h exact h.2 have eD0 : ∀ x, x ∈ D' → x ∈ H0 := by intro x hx have h : x ∈ D := hD'sub hx rw [hDdef] at h simp only [Finset.mem_inter] at h exact h.1 have eD1 : ∀ x, x ∈ D' → x ∈ H1 := by intro x hx have h : x ∈ D := hD'sub hx rw [hDdef] at h simp only [Finset.mem_inter] at h exact h.2 have hS0 : (A' ∪ B' ∪ C' ∪ D') ∩ H0 = C' ∪ D' := by ext x have h1 : x ∈ A' → x ∉ H0 := eA0 x have h2 : x ∈ B' → x ∉ H0 := eB0 x have h3 : x ∈ C' → x ∈ H0 := eC0 x have h4 : x ∈ D' → x ∈ H0 := eD0 x simp only [Finset.mem_inter, Finset.mem_union] tauto have hS1 : (A' ∪ B' ∪ C' ∪ D') ∩ H1 = B' ∪ D' := by ext x have h1 : x ∈ A' → x ∉ H1 := eA1 x have h2 : x ∈ B' → x ∈ H1 := eB1 x have h3 : x ∈ C' → x ∉ H1 := eC1 x have h4 : x ∈ D' → x ∈ H1 := eD1 x simp only [Finset.mem_inter, Finset.mem_union] tauto have hS0card : ((A' ∪ B' ∪ C' ∪ D') ∩ H0).card = c + d := by rw [hS0, Finset.card_union_of_disjoint (dCD.mono hC'sub hD'sub), hC'card, hD'card] have hS1card : ((A' ∪ B' ∪ C' ∪ D') ∩ H1).card = b + d := by rw [hS1, Finset.card_union_of_disjoint (dBD.mono hB'sub hD'sub), hB'card, hD'card]
The complements H0 \ S and H1 \ S have sizes (|C| - c) + (|D| - d) and (|B| - b) + (|D| - d), and |S| = a + b + c + d.
The set difference H0 \ S equals the disjoint union (C \ C') ∪ (D \ D'), and H1 \ S equals (B \ B') ∪ (D \ D'). Since the four sub-bundles are pairwise disjoint, |S| is the sum of their cardinalities, and the total number of chores m is the sum of the cardinalities of A, B, C, D.
uses
Finset.mem_sdiff,Finset.mem_union,Finset.disjoint_left,Finset.card_union_of_disjoint,Disjoint.mono,Finset.sdiff_subset,Finset.card_sdiff_add_card_eq_card,two_agent_common_bivalued_safe_partition_card_union_four,congrArg,Finset.subset_univ,Finset.card_univ,Fintype.card_finhave hH0sdiff : H0 \ (A' ∪ B' ∪ C' ∪ D') = (C \ C') ∪ (D \ D') := by ext x have hx0 : x ∈ H0 ↔ x ∈ C ∨ x ∈ D := by rw [hH0]; exact Finset.mem_union have f1 : x ∈ A' → x ∉ C := fun hx hc => Finset.disjoint_left.1 dAC (hA'sub hx) hc have f2 : x ∈ A' → x ∉ D := fun hx hd => Finset.disjoint_left.1 dAD (hA'sub hx) hd have f3 : x ∈ B' → x ∉ C := fun hx hc => Finset.disjoint_left.1 dBC (hB'sub hx) hc have f4 : x ∈ B' → x ∉ D := fun hx hd => Finset.disjoint_left.1 dBD (hB'sub hx) hd have f5 : x ∈ C → x ∉ D' := fun hc hd => (Finset.disjoint_left.1 dCD hc) (hD'sub hd) have f6 : x ∈ D → x ∉ C' := fun hd hc => (Finset.disjoint_left.1 dCD (hC'sub hc)) hd simp only [Finset.mem_sdiff, Finset.mem_union] tauto have hH1sdiff : H1 \ (A' ∪ B' ∪ C' ∪ D') = (B \ B') ∪ (D \ D') := by ext x have hx0 : x ∈ H1 ↔ x ∈ B ∨ x ∈ D := by rw [hH1]; exact Finset.mem_union have f1 : x ∈ A' → x ∉ B := fun hx hb => Finset.disjoint_left.1 dAB (hA'sub hx) hb have f2 : x ∈ A' → x ∉ D := fun hx hd => Finset.disjoint_left.1 dAD (hA'sub hx) hd have f3 : x ∈ C' → x ∉ B := fun hx hb => (Finset.disjoint_left.1 dBC hb) (hC'sub hx) have f4 : x ∈ C' → x ∉ D := fun hx hd => Finset.disjoint_left.1 dCD (hC'sub hx) hd have f5 : x ∈ B → x ∉ D' := fun hb hd => (Finset.disjoint_left.1 dBD hb) (hD'sub hd) have f6 : x ∈ D → x ∉ B' := fun hd hb => (Finset.disjoint_left.1 dBD (hB'sub hb)) hd simp only [Finset.mem_sdiff, Finset.mem_union] tauto have hH0sdiffcard : (H0 \ (A' ∪ B' ∪ C' ∪ D')).card = (C \ C').card + (D \ D').card := by rw [hH0sdiff, Finset.card_union_of_disjoint (Disjoint.mono (Finset.sdiff_subset : C \ C' ⊆ C) (Finset.sdiff_subset : D \ D' ⊆ D) dCD)] have hH1sdiffcard : (H1 \ (A' ∪ B' ∪ C' ∪ D')).card = (B \ B').card + (D \ D').card := by rw [hH1sdiff, Finset.card_union_of_disjoint (Disjoint.mono (Finset.sdiff_subset : B \ B' ⊆ B) (Finset.sdiff_subset : D \ D' ⊆ D) dBD)] have hdCC' : (C \ C').card + C'.card = C.card := Finset.card_sdiff_add_card_eq_card hC'sub have hdDD' : (D \ D').card + D'.card = D.card := Finset.card_sdiff_add_card_eq_card hD'sub have hdBB' : (B \ B').card + B'.card = B.card := Finset.card_sdiff_add_card_eq_card hB'sub have hScard : (A' ∪ B' ∪ C' ∪ D').card = a + b + c + d := by rw [two_agent_common_bivalued_safe_partition_card_union_four (dAB.mono hA'sub hB'sub) (dAC.mono hA'sub hC'sub) (dAD.mono hA'sub hD'sub) (dBC.mono hB'sub hC'sub) (dBD.mono hB'sub hD'sub) (dCD.mono hC'sub hD'sub), hA'card, hB'card, hC'card, hD'card] have hpartcard : A.card + B.card + C.card + D.card = m := by have h := congrArg Finset.card hpart rw [two_agent_common_bivalued_safe_partition_card_union_four dAB dAC dAD dBC dBD dCD] at h simpa using h have hH0card : H0.card = C.card + D.card := by rw [hH0, Finset.card_union_of_disjoint dCD] have hH1card : H1.card = B.card + D.card := by rw [hH1, Finset.card_union_of_disjoint dBD] have hunivsdiff : (Finset.univ \ (A' ∪ B' ∪ C' ∪ D')).card + (A' ∪ B' ∪ C' ∪ D').card = m := by rw [Finset.card_sdiff_add_card_eq_card (Finset.subset_univ _), Finset.card_univ, Fintype.card_fin] clear eA0 eA1 eB0 eB1 eC0 eC1 eD0 eD1 hAdef hBdef hCdef hDdef hpart hS0 hS1 hH0sdiff hH1sdiff dAB dAC dAD dBC dBD dCD hH0 hH1 ha hb hc hd hA'sub hB'sub hC'sub hD'sub
The bundle S satisfies the balanced cardinality bounds with respect to m, H0, and H1. automation
Substituting the cardinalities of S, its complement, and their intersections into the inequalities established for a, b, c, d in the counting lemma, linear integer arithmetic (omega) closes all six upper bounds.
refine ⟨A' ∪ B' ∪ C' ∪ D', ?_, ?_, ?_, ?_, ?_, ?_⟩ · omega · omega · omega · omega · omega · omega
The additive valuation of any bundle S is given by a * (|S| + (r - 1) * |S ∩ H|).
We rewrite the cost of chore g as a + (r - 1)a * 1_{g ∈ H}. Summing this over S splits into the constant sum of a over S and the sum of (r - 1)a over S ∩ H, which factors into the stated closed form.
uses
additive_valuation,Finset.sum_congr,Finset.sum_add_distrib,Finset.sum_ite_mem,Finset.sum_const,nsmul_eq_mulhave h1 : ∀ g ∈ S, u g = a + (if g ∈ H then (r - 1) * a else 0) := by intro g _ rw [hu g] by_cases h : g ∈ H · simp only [h, if_true]; ring · simp only [h, if_false, add_zero] rw [additive_valuation, Finset.sum_congr rfl h1, Finset.sum_add_distrib, Finset.sum_ite_mem, Finset.sum_const, Finset.sum_const] simp only [nsmul_eq_mul] ring
In any two-bundle partition P, the cardinalities of the two bundles sum to m.
Summing the fiber sizes of P over Fin 2 partitions the universal set Finset.univ, whose cardinality is m.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_univ,Finset.card_univ,Fintype.card_fin,Fin.sum_univ_two,bundle_of(bundle_of P 0).card + (bundle_of P 1).card = m := by have h := Finset.card_eq_sum_card_fiberwise (f := P) (s := (Finset.univ : Finset (Fin m))) (t := (Finset.univ : Finset (Fin 2))) (by intro x _; exact Finset.mem_univ _) simp only [Finset.card_univ, Fintype.card_fin] at h rw [Fin.sum_univ_two] at h simpa [bundle_of] using h.symm
In any two-bundle partition P, the intersections of the two bundles with H sum in cardinality to |H|.
Summing the fiber sizes of P restricted to H partitions H into two disjoint subsets whose sizes sum to |H|.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_univ,Fin.sum_univ_two,bundle_ofhave h := Finset.card_eq_sum_card_fiberwise (f := P) (s := H) (t := (Finset.univ : Finset (Fin 2))) (by intro x _; exact Finset.mem_univ _) rw [Fin.sum_univ_two] at h have e0 : (bundle_of P 0) ∩ H = H.filter (fun x => P x = 0) := by ext x; simp [bundle_of, and_comm] have e1 : (bundle_of P 1) ∩ H = H.filter (fun x => P x = 1) := by ext x; simp [bundle_of, and_comm] rw [e0, e1] exact h.symm
When m = 2k is even, the chore maximin share is bounded below by a * (k + (r - 1) * |H| / 2). automation
For any partition P, the sum of valuations of the two bundles equals a * (m + (r - 1)|H|) = 2a * (k + (r - 1)|H| / 2). Thus the maximum bundle has cost at least this average. Taking the infimum over all partitions yields the MMS lower bound, verified by nlinarith.
uses
chore_maximin_share,le_ciInf,Set.finite_range,le_ciSup,two_agent_common_bivalued_safe_partition_bundle_card_add,two_agent_common_bivalued_safe_partition_bundle_card_inter_add,two_agent_common_bivalued_safe_partition_cost_formularw [chore_maximin_share] refine le_ciInf (fun P => ?_) have hbdd : BddAbove (Set.range fun j : Fin 2 => additive_valuation u (bundle_of P j)) := (Set.finite_range _).bddAbove have h0 : additive_valuation u (bundle_of P 0) ≤ ⨆ j, additive_valuation u (bundle_of P j) := le_ciSup hbdd 0 have h1 : additive_valuation u (bundle_of P 1) ≤ ⨆ j, additive_valuation u (bundle_of P j) := le_ciSup hbdd 1 have hc0 : (((bundle_of P 0).card : ℝ)) + ((bundle_of P 1).card : ℝ) = (m : ℝ) := by have := two_agent_common_bivalued_safe_partition_bundle_card_add m P exact_mod_cast this have hcH : (((bundle_of P 0) ∩ H).card : ℝ) + (((bundle_of P 1) ∩ H).card : ℝ) = (H.card : ℝ) := by have := two_agent_common_bivalued_safe_partition_bundle_card_inter_add m P H exact_mod_cast this have hsum : additive_valuation u (bundle_of P 0) + additive_valuation u (bundle_of P 1) = a * ((m : ℝ) + (r - 1) * (H.card : ℝ)) := by rw [two_agent_common_bivalued_safe_partition_cost_formula u H r a hu, two_agent_common_bivalued_safe_partition_cost_formula u H r a hu] have expand : a * (((bundle_of P 0).card : ℝ) + (r - 1) * (((bundle_of P 0) ∩ H).card : ℝ)) + a * (((bundle_of P 1).card : ℝ) + (r - 1) * (((bundle_of P 1) ∩ H).card : ℝ)) = a * ((((bundle_of P 0).card : ℝ) + ((bundle_of P 1).card : ℝ)) + (r - 1) * ((((bundle_of P 0) ∩ H).card : ℝ) + (((bundle_of P 1) ∩ H).card : ℝ))) := by ring rw [expand, hc0, hcH] have hk : (m : ℝ) = 2 * (k : ℝ) := by rw [hm]; push_cast; ring nlinarith [h0, h1, hsum, ha, hk]
When m = 2k + 1 is odd, the chore maximin share is bounded below by a * ((k + 1) + (r - 1) * (|H| - k)).
By the pigeonhole principle, any partition P has at least one bundle with at least k + 1 chores. Any such bundle must contain at least |H| - k high-cost chores, so its cost is at least a * ((k + 1) + (r - 1)(|H| - k)). Taking the infimum over all partitions establishes the MMS lower bound.
uses
chore_maximin_share,le_ciInf,Set.finite_range,le_ciSup,two_agent_common_bivalued_safe_partition_bundle_card_add,Finset.card_sdiff,Finset.card_le_card,Finset.mem_sdiff,Finset.mem_univ,true_and,Finset.card_sdiff_add_card_eq_card,Finset.subset_univ,Finset.card_univ,Fintype.card_fin,two_agent_common_bivalued_safe_partition_cost_formula,mul_le_mul_of_nonneg_left,Nat.lt_or_gerw [chore_maximin_share] refine le_ciInf (fun P => ?_) have hbdd : BddAbove (Set.range fun j : Fin 2 => additive_valuation u (bundle_of P j)) := (Set.finite_range _).bddAbove have h0 : additive_valuation u (bundle_of P 0) ≤ ⨆ j, additive_valuation u (bundle_of P j) := le_ciSup hbdd 0 have h1 : additive_valuation u (bundle_of P 1) ≤ ⨆ j, additive_valuation u (bundle_of P j) := le_ciSup hbdd 1 have hc0 : (bundle_of P 0).card + (bundle_of P 1).card = m := two_agent_common_bivalued_safe_partition_bundle_card_add m P have hr1 : (0:ℝ) ≤ r - 1 := by linarith have key : ∀ (b : Finset (Fin m)), k + 1 ≤ b.card → a * (((k : ℝ) + 1) + (r - 1) * (((H.card - k : ℕ) : ℝ))) ≤ additive_valuation u b := by intro b hbc have hbh : (H.card - k : ℕ) ≤ (b ∩ H).card := by have hsd : (H \ b).card = H.card - (b ∩ H).card := Finset.card_sdiff have hcomp : (H \ b).card + b.card ≤ m := by have h1 : (H \ b).card ≤ (Finset.univ \ b : Finset (Fin m)).card := Finset.card_le_card (by intro x hx simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] at hx ⊢ exact hx.2) have h2 : (Finset.univ \ b : Finset (Fin m)).card + b.card = m := by rw [Finset.card_sdiff_add_card_eq_card (Finset.subset_univ b), Finset.card_univ, Fintype.card_fin] omega omega rw [two_agent_common_bivalued_safe_partition_cost_formula u H r a hu b] refine mul_le_mul_of_nonneg_left ?_ ha.le have e1 : ((k : ℝ) + 1) ≤ (b.card : ℝ) := by exact_mod_cast hbc have e2 : (((H.card - k : ℕ) : ℝ)) ≤ ((b ∩ H).card : ℝ) := by exact_mod_cast hbh have := mul_le_mul_of_nonneg_left e2 hr1 linarith rcases Nat.lt_or_ge (bundle_of P 0).card (k + 1) with hlt | hge · have hb1 : k + 1 ≤ (bundle_of P 1).card := by omega have := key (bundle_of P 1) hb1 linarith · have hb0 : k + 1 ≤ (bundle_of P 0).card := hge have := key (bundle_of P 0) hb0 linarith
When m = 2k with k ≥ 1, both S and its complement cost at most ((r + 1) / 2) * MMS_i for each agent.
Because |S| and |S^c| are both at most k, they each have size exactly k and at most ⌊(|H| + 1)/2⌋ high chores. By the cost formula and the arithmetic lemma bivalued_rounding_even_mms_arithmetic, the cost of each bundle is at most ((r + 1)/2) times the MMS lower bound for even m.
uses
Finset.card_sdiff,Finset.inter_univ,Finset.card_univ,Fintype.card_fin,two_agent_common_bivalued_safe_partition_mms_even,bivalued_rounding_even_mms_arithmetic,two_agent_common_bivalued_safe_partition_cost_formula,mul_le_mul_of_nonneg_lefthave hr1 : (0:ℝ) ≤ r - 1 := by linarith have h3 : (Finset.univ \ S).card = m - S.card := by rw [Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, Fintype.card_fin] have hScard : S.card = k := by omega have hSccard : (Finset.univ \ S).card = k := by omega have hdel : (Finset.univ \ S) ∩ H = H \ S := by ext x; simp [and_comm] have hmms := two_agent_common_bivalued_safe_partition_mms_even hm r a ha u H hu have harith := bivalued_rounding_even_mms_arithmetic k H.card (r - 1) hk hr1 have hbdd : (0:ℝ) ≤ ((r + 1) / 2) := by linarith have hmain : ∀ (T : Finset (Fin m)) (x y : ℝ), ((T.card : ℝ)) ≤ x → (((T ∩ H).card : ℝ)) ≤ y → additive_valuation u T ≤ a * (x + (r - 1) * y) := by intro T x y hx hy rw [two_agent_common_bivalued_safe_partition_cost_formula u H r a hu T] refine mul_le_mul_of_nonneg_left ?_ ha.le have := mul_le_mul_of_nonneg_left hy hr1 linarith have h4 : ((r + 1) / 2) * (a * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2)) ≤ ((r + 1) / 2) * chore_maximin_share 2 u := mul_le_mul_of_nonneg_left hmms hbdd have h2 : 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 harith ha.le have key : a * ((1 + (r - 1) / 2) * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2)) = ((r + 1) / 2) * (a * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2)) := by ring constructor · have h1 : additive_valuation u S ≤ a * ((k : ℝ) + (r - 1) * ((((H.card + 1) / 2 : ℕ) : ℝ))) := by refine hmain S (k : ℝ) ((((H.card + 1) / 2 : ℕ) : ℝ)) ?_ ?_ · rw [hScard] · exact_mod_cast hh linarith · have h1 : additive_valuation u (Finset.univ \ S) ≤ a * ((k : ℝ) + (r - 1) * ((((H.card + 1) / 2 : ℕ) : ℝ))) := by refine hmain (Finset.univ \ S) (k : ℝ) ((((H.card + 1) / 2 : ℕ) : ℝ)) ?_ ?_ · rw [hSccard] · rw [hdel]; exact_mod_cast hhc linarith
When m = 2k + 1, both S and its complement cost at most ((r + 1) / 2) * MMS_i for each agent.
Both bundles have size at most k + 1 and at most ⌊(|H| + 1)/2⌋ high chores. By the cost formula and the arithmetic lemma bivalued_rounding_odd_mms_arithmetic, the cost of each bundle is at most ((r + 1)/2) times the MMS lower bound for odd m.
uses
two_agent_common_bivalued_safe_partition_mms_odd,bivalued_rounding_odd_mms_arithmetic,two_agent_common_bivalued_safe_partition_cost_formula,mul_le_mul_of_nonneg_left,Finset.card_sdiff,Finset.inter_univ,Finset.card_univ,Fintype.card_finhave hr1 : (0:ℝ) ≤ r - 1 := by linarith have hmms := two_agent_common_bivalued_safe_partition_mms_odd hm r a hr ha u H hu have harith := bivalued_rounding_odd_mms_arithmetic k H.card (r - 1) hr1 have hbdd : (0:ℝ) ≤ ((r + 1) / 2) := by linarith have hdel : (Finset.univ \ S) ∩ H = H \ S := by ext x; simp [and_comm] have hmain : ∀ (T : Finset (Fin m)) (x y : ℝ), ((T.card : ℝ)) ≤ x → (((T ∩ H).card : ℝ)) ≤ y → additive_valuation u T ≤ a * (x + (r - 1) * y) := by intro T x y hx hy rw [two_agent_common_bivalued_safe_partition_cost_formula u H r a hu T] refine mul_le_mul_of_nonneg_left ?_ ha.le have := mul_le_mul_of_nonneg_left hy hr1 linarith have hY : a * ((1 + (r - 1) / 2) * ((k : ℝ) + 1 + (r - 1) * (((H.card - k : ℕ) : ℝ)))) = ((r + 1) / 2) * (a * ((k : ℝ) + 1 + (r - 1) * (((H.card - k : ℕ) : ℝ)))) := by ring have hmid : a * (((k : ℝ) + 1) + (r - 1) * ((((H.card + 1) / 2 : ℕ) : ℝ))) ≤ ((r + 1) / 2) * (a * ((k : ℝ) + 1 + (r - 1) * (((H.card - k : ℕ) : ℝ)))) := by rw [← hY]; exact mul_le_mul_of_nonneg_left harith ha.le have h4 : ((r + 1) / 2) * (a * ((k : ℝ) + 1 + (r - 1) * (((H.card - k : ℕ) : ℝ)))) ≤ ((r + 1) / 2) * chore_maximin_share 2 u := mul_le_mul_of_nonneg_left hmms hbdd constructor · have h1 : additive_valuation u S ≤ a * (((k : ℝ) + 1) + (r - 1) * ((((H.card + 1) / 2 : ℕ) : ℝ))) := by refine hmain S ((k : ℝ) + 1) ((((H.card + 1) / 2 : ℕ) : ℝ)) ?_ ?_ · have : S.card ≤ k + 1 := by omega exact_mod_cast this · exact_mod_cast hh linarith · have h1 : additive_valuation u (Finset.univ \ S) ≤ a * (((k : ℝ) + 1) + (r - 1) * ((((H.card + 1) / 2 : ℕ) : ℝ))) := by refine hmain (Finset.univ \ S) ((k : ℝ) + 1) ((((H.card + 1) / 2 : ℕ) : ℝ)) ?_ ?_ · have h3 : (Finset.univ \ S).card = m - S.card := by rw [Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, Fintype.card_fin] have : (Finset.univ \ S).card ≤ k + 1 := by omega exact_mod_cast this · rw [hdel]; exact_mod_cast hhc linarith
In the base case m = 0, the empty bundle trivially satisfies the safety condition.
When m = 0, all chore sets are empty, so the valuations are identically 0. Since the maximin share is non-negative and (r + 1) / 2 ≥ 0, the bound 0 ≤ ((r + 1)/2) * MMS_i holds immediately.
uses
Nat.eq_zero_or_pos,additive_valuation,Finset.sum_empty,two_agent_common_bivalued_safe_partition_mms_even,mul_nonnegclassical 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 have halpha : (0:ℝ) ≤ (r + 1) / 2 := by linarith rcases Nat.eq_zero_or_pos m with hm0 | hmpos · subst hm0 have hHempty : ∀ i : Fin 2, H i = ∅ := by intro i apply Finset.eq_empty_iff_forall_notMem.mpr intro x exact x.elim0 have hzero : ∀ (i : Fin 2) (T : Finset (Fin 0)), additive_valuation (c i) T = 0 := by intro i T have hT : T = ∅ := by apply Finset.eq_empty_iff_forall_notMem.mpr intro x exact x.elim0 rw [hT, additive_valuation, Finset.sum_empty] have hmms : ∀ i : Fin 2, (0:ℝ) ≤ chore_maximin_share 2 (c i) := by intro i have h := two_agent_common_bivalued_safe_partition_mms_even (k := 0) (m := 0) (rfl : (0:ℕ) = 2 * 0) r (a i) (ha i) (c i) (H i) (hval i) rw [hHempty i] at h simpa using h refine ⟨∅, fun i => ⟨?_, ?_⟩⟩ · rw [hzero i ∅]; exact mul_nonneg halpha (hmms i) · rw [hzero i (Finset.univ \ (∅ : Finset (Fin 0)))] exact mul_nonneg halpha (hmms i)
For m > 0, the balanced partition S guarantees safety for both bundles and both agents.
We obtain a balanced bundle S using the balance lemma. Splitting into cases depending on whether m is even or odd, we apply the even or odd agent lemma to each agent i ∈ {0, 1} to conclude the proof.
uses
two_agent_common_bivalued_safe_partition_balance,Nat.even_or_odd,two_agent_common_bivalued_safe_partition_agent_even,two_agent_common_bivalued_safe_partition_agent_odd· obtain ⟨S, hs, hsc, h0, h0c, h1, h1c⟩ := two_agent_common_bivalued_safe_partition_balance m (H 0) (H 1) refine ⟨S, fun i => ?_⟩ rcases Nat.even_or_odd m with ⟨k, hk⟩ | ⟨k, hk⟩ · have hmk : m = 2 * k := by omega have hk1 : 1 ≤ k := by omega fin_cases i · exact two_agent_common_bivalued_safe_partition_agent_even hmk hk1 r (a 0) hr1 (ha 0) (c 0) (H 0) S (hval 0) hs hsc h0 h0c · exact two_agent_common_bivalued_safe_partition_agent_even hmk hk1 r (a 1) hr1 (ha 1) (c 1) (H 1) S (hval 1) hs hsc h1 h1c · have hmk : m = 2 * k + 1 := by omega fin_cases i · exact two_agent_common_bivalued_safe_partition_agent_odd hmk r (a 0) hr1 (ha 0) (c 0) (H 0) S (hval 0) hs hsc h0 h0c · exact two_agent_common_bivalued_safe_partition_agent_odd hmk r (a 1) hr1 (ha 1) (c 1) (H 1) S (hval 1) hs hsc h1 h1c
additive_valuation- The additive valuation of a set of chores is the sum of their individual costs.
bivalued_rounding_even_mms_arithmetic- Arithmetic inequality for even m bounding k + d * ⌊(h + 1)/2⌋ by (1 + d/2)(k + d * h / 2).
bivalued_rounding_odd_mms_arithmetic- Arithmetic inequality for odd m bounding (k + 1) + d * ⌊(h + 1)/2⌋ by (1 + d/2)((k + 1) + d * (h - k)).
bundle_of- The bundle assigned to agent i under partition P is the set of items mapped to i.
chore_maximin_share- The two-agent chore maximin share is the infimum over all partitions of the maximum bundle cost.
congrArg- Functions preserve equality: if x = y then f(x) = f(y).
Disjoint.mono- Disjointness is preserved when passing to subsets.
Fin.sum_univ_two- A sum of values indexed by Fin 2 equals the sum of the value at 0 and the value at 1.
Finset.card_eq_sum_card_fiberwise- The cardinality of a set equals the sum of the cardinalities of its fibers under a map.
Finset.card_sdiff_add_card_eq_card- For a subset s ⊆ t, the size of t \ s plus the size of s equals the size of t.
Finset.card_sdiff- The size of t \ s equals the size of t minus the size of s ∩ t.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_univ- The cardinality of the universal set Finset.univ equals the cardinality of the underlying finite type.
Finset.disjoint_left- Two sets are disjoint if and only if no element of the first belongs to the second.
Finset.disjoint_union_left.mpr- A union A ∪ B is disjoint from C if both A and B are disjoint from C.
Finset.exists_subset_card_eq- Any finite set has a subset of any specified cardinality less than or equal to its size.
Finset.inter_univ- Intersecting a set with Finset.univ leaves it unchanged.
Finset.mem_inter- An element belongs to s ∩ t if and only if it belongs to both s and t.
Finset.mem_sdiff- An element belongs to s \ t if and only if it belongs to s and not to t.
Finset.mem_union- An element belongs to s ∪ t if and only if it belongs to s or to t.
Finset.mem_univ- Every element of a finite type belongs to Finset.univ.
Finset.sdiff_subset- The set difference s \ t is a subset of s.
Finset.subset_univ- Every finite set is a subset of Finset.univ.
Finset.sum_add_distrib- The sum of a sum of functions equals the sum of the two sums.
Finset.sum_congr- Two sums over the same set are equal if their terms agree on all elements of the set.
Finset.sum_const- Summing a constant b over a set s yields |s| • b.
Finset.sum_empty- The sum of any function over the empty set is zero.
Finset.sum_ite_mem- Summing an if-then-else indicator over s equals summing the term over the intersection with the condition set.
Fintype.card_fin- The cardinality of Fin n is n.
iff_true- A proposition P is logically equivalent to (P ↔ True).
le_ciInf- A lower bound for all values of a family is a lower bound for their infimum.
le_ciSup- Any element of a set bounded above is at most the supremum of the set.
mul_le_mul_of_nonneg_left- Multiplying an inequality by a non-negative number preserves the inequality.
mul_nonneg- The product of two non-negative numbers is non-negative.
Nat.eq_zero_or_pos- Any natural number is either 0 or strictly positive.
Nat.even_or_odd- Any natural number is either even or odd.
Nat.lt_or_ge- For any natural numbers n and m, either n < m or n ≥ m.
not_or- De Morgan's law: ¬(P ∨ Q) ↔ ¬P ∧ ¬Q.
nsmul_eq_mul- Natural number scalar multiplication equals multiplication by the cast of the natural number.
Set.finite_range- The range of a function on a finite domain is finite.
true_and- The proposition True ∧ P simplifies to P.
two_agent_common_bivalued_safe_partition_agent_even- For even m = 2k with k ≥ 1, a balanced bundle satisfies the safety guarantee for both bundles.
two_agent_common_bivalued_safe_partition_agent_odd- For odd m = 2k + 1, a balanced bundle satisfies the safety guarantee for both bundles.
two_agent_common_bivalued_safe_partition_balance- There exists a bundle S that bisects the universe and both agents' high-cost chore sets up to 1.
two_agent_common_bivalued_safe_partition_bundle_card_add- In any 2-partition of m chores, the sizes of the two bundles sum to m.
two_agent_common_bivalued_safe_partition_bundle_card_inter_add- In any 2-partition of m chores, the intersections of the two bundles with H sum in cardinality to |H|.
two_agent_common_bivalued_safe_partition_card_union_four- The cardinality of four pairwise disjoint finite sets is the sum of their cardinalities.
two_agent_common_bivalued_safe_partition_cost_formula- The additive cost of bundle S to an agent with base cost a and high chore set H is a * (|S| + (r - 1) * |S ∩ H|).
two_agent_common_bivalued_safe_partition_counts- Given four integers, there exist sub-counts simultaneously bisecting the total and the two marginal sums up to 1.
two_agent_common_bivalued_safe_partition_mms_even- When m = 2k is even, the chore maximin share is at least a * (k + (r - 1) * |H| / 2).
two_agent_common_bivalued_safe_partition_mms_odd- When m = 2k + 1 is odd, the chore maximin share is at least a * ((k + 1) + (r - 1) * (|H| - k)).
- The lemma two_agent_common_bivalued_safe_partition_counts verifies an existence claim over 16 remainder cases mod 2 using the automated linear integer arithmetic tactic omega.
- The key arithmetic inequalities linking the balanced bundle cost bounds to the maximin share bounds are factored out into the library lemmas bivalued_rounding_even_mms_arithmetic and bivalued_rounding_odd_mms_arithmetic.
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.
Lean’s trace was cut to the first 400 of 803 tactics.
set_option maxHeartbeats 4000000 inlemma two_agent_common_bivalued_safe_partition_counts (n00 n01 n10 n11 : ℕ) : ∃ a b c d : ℕ, a ≤ n00 ∧ b ≤ n01 ∧ c ≤ n10 ∧ d ≤ n11 ∧ 2 * (a + b + c + d) ≤ n00 + n01 + n10 + n11 + 1 ∧ n00 + n01 + n10 + n11 ≤ 2 * (a + b + c + d) + 1 ∧ 2 * (c + d) ≤ n10 + n11 + 1 ∧ n10 + n11 ≤ 2 * (c + d) + 1 ∧ 2 * (b + d) ≤ n01 + n11 + 1 ∧ n01 + n11 ≤ 2 * (b + d) + 1 := by obtain ⟨u00, e00, he00, rfl⟩ : ∃ u e : ℕ, e ≤ 1 ∧ n00 = 2 * u + e := ⟨n00 / 2, n00 % 2, by omega, by omega⟩ obtain ⟨u01, e01, he01, rfl⟩ : ∃ u e : ℕ, e ≤ 1 ∧ n01 = 2 * u + e := ⟨n01 / 2, n01 % 2, by omega, by omega⟩ obtain ⟨u10, e10, he10, rfl⟩ : ∃ u e : ℕ, e ≤ 1 ∧ n10 = 2 * u + e := ⟨n10 / 2, n10 % 2, by omega, by omega⟩ obtain ⟨u11, e11, he11, rfl⟩ : ∃ u e : ℕ, e ≤ 1 ∧ n11 = 2 * u + e := ⟨n11 / 2, n11 % 2, by omega, by omega⟩ interval_cases e00 <;> interval_cases e01 <;> interval_cases e10 <;> interval_cases e11 all_goals first | exact ⟨u00, u01, u10, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00 + 1, u01, u10, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00, u01 + 1, u10, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00, u01, u10 + 1, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00, u01, u10, u11 + 1, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00 + 1, u01 + 1, u10, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00 + 1, u01, u10 + 1, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩ | exact ⟨u00, u01 + 1, u10 + 1, u11, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega, by omega⟩set_option maxHeartbeats 1000000 inlemma two_agent_common_bivalued_safe_partition_card_union_four {α : Type*} [DecidableEq α] {A B C D : Finset α} (hAB : Disjoint A B) (hAC : Disjoint A C) (hAD : Disjoint A D) (hBC : Disjoint B C) (hBD : Disjoint B D) (hCD : Disjoint C D) : (A ∪ B ∪ C ∪ D).card = A.card + B.card + C.card + D.card := by have hABD : Disjoint (A ∪ B) D := Finset.disjoint_union_left.mpr ⟨hAD, hBD⟩ have hABC : Disjoint (A ∪ B) C := Finset.disjoint_union_left.mpr ⟨hAC, hBC⟩ have h2 : Disjoint ((A ∪ B) ∪ C) D := Finset.disjoint_union_left.mpr ⟨hABD, hCD⟩ rw [Finset.card_union_of_disjoint h2, Finset.card_union_of_disjoint hABC, Finset.card_union_of_disjoint hAB]set_option maxHeartbeats 8000000 inlemma two_agent_common_bivalued_safe_partition_balance (m : ℕ) (H0 H1 : Finset (Fin m)) : ∃ S : Finset (Fin m), S.card ≤ (m + 1) / 2 ∧ (Finset.univ \ S).card ≤ (m + 1) / 2 ∧ (S ∩ H0).card ≤ (H0.card + 1) / 2 ∧ (H0 \ S).card ≤ (H0.card + 1) / 2 ∧ (S ∩ H1).card ≤ (H1.card + 1) / 2 ∧ (H1 \ S).card ≤ (H1.card + 1) / 2 := by classical obtain ⟨A, B, C, D, hAdef, hBdef, hCdef, hDdef, hpart, dAB, dAC, dAD, dBC, dBD, dCD, hH0, hH1⟩ : ∃ A B C D : Finset (Fin m), A = Finset.univ \ (H0 ∪ H1) ∧ B = H1 \ H0 ∧ C = H0 \ H1 ∧ D = H0 ∩ H1 ∧ A ∪ B ∪ C ∪ D = Finset.univ ∧ Disjoint A B ∧ Disjoint A C ∧ Disjoint A D ∧ Disjoint B C ∧ Disjoint B D ∧ Disjoint C D ∧ H0 = C ∪ D ∧ H1 = B ∪ D := by refine ⟨Finset.univ \ (H0 ∪ H1), H1 \ H0, H0 \ H1, H0 ∩ H1, rfl, rfl, rfl, rfl, ?_⟩ have mA : ∀ x : Fin m, x ∈ (Finset.univ \ (H0 ∪ H1) : Finset (Fin m)) ↔ x ∉ H0 ∧ x ∉ H1 := fun x => by simp have mB : ∀ x : Fin m, x ∈ (H1 \ H0 : Finset (Fin m)) ↔ x ∈ H1 ∧ x ∉ H0 := fun x => by simp have mC : ∀ x : Fin m, x ∈ (H0 \ H1 : Finset (Fin m)) ↔ x ∈ H0 ∧ x ∉ H1 := fun x => by simp have mD : ∀ x : Fin m, x ∈ (H0 ∩ H1 : Finset (Fin m)) ↔ x ∈ H0 ∧ x ∈ H1 := fun x => by simp refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩ · ext x have a := mA x; have b := mB x; have c := mC x; have d := mD x simp only [Finset.mem_union, Finset.mem_univ, iff_true] tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mA x).1 hx; have h2 := (mB x).1 hy; tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mA x).1 hx; have h2 := (mC x).1 hy; tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mA x).1 hx; have h2 := (mD x).1 hy; tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mB x).1 hx; have h2 := (mC x).1 hy; tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mB x).1 hx; have h2 := (mD x).1 hy; tauto · rw [Finset.disjoint_left]; intro x hx hy have h1 := (mC x).1 hx; have h2 := (mD x).1 hy; tauto · ext x have c := mC x; have d := mD x simp only [Finset.mem_union] tauto · ext x have b := mB x; have d := mD x simp only [Finset.mem_union] tauto obtain ⟨a, b, c, d, ha, hb, hc, hd, e1, e2, e3, e4, e5, e6⟩ := two_agent_common_bivalued_safe_partition_counts A.card B.card C.card D.card obtain ⟨A', hA'sub, hA'card⟩ := Finset.exists_subset_card_eq ha obtain ⟨B', hB'sub, hB'card⟩ := Finset.exists_subset_card_eq hb obtain ⟨C', hC'sub, hC'card⟩ := Finset.exists_subset_card_eq hc obtain ⟨D', hD'sub, hD'card⟩ := Finset.exists_subset_card_eq hd have eA0 : ∀ x, x ∈ A' → x ∉ H0 := by intro x hx have h : x ∈ A := hA'sub hx rw [hAdef] at h simp only [Finset.mem_sdiff, Finset.mem_union, Finset.mem_univ, not_or, true_and] at h exact h.1 have eA1 : ∀ x, x ∈ A' → x ∉ H1 := by intro x hx have h : x ∈ A := hA'sub hx rw [hAdef] at h simp only [Finset.mem_sdiff, Finset.mem_union, Finset.mem_univ, not_or, true_and] at h exact h.2 have eB0 : ∀ x, x ∈ B' → x ∉ H0 := by intro x hx have h : x ∈ B := hB'sub hx rw [hBdef] at h simp only [Finset.mem_sdiff] at h exact h.2 have eB1 : ∀ x, x ∈ B' → x ∈ H1 := by intro x hx have h : x ∈ B := hB'sub hx rw [hBdef] at h simp only [Finset.mem_sdiff] at h exact h.1 have eC0 : ∀ x, x ∈ C' → x ∈ H0 := by intro x hx have h : x ∈ C := hC'sub hx rw [hCdef] at h simp only [Finset.mem_sdiff] at h exact h.1 have eC1 : ∀ x, x ∈ C' → x ∉ H1 := by intro x hx have h : x ∈ C := hC'sub hx rw [hCdef] at h simp only [Finset.mem_sdiff] at h exact h.2 have eD0 : ∀ x, x ∈ D' → x ∈ H0 := by intro x hx have h : x ∈ D := hD'sub hx rw [hDdef] at h simp only [Finset.mem_inter] at h exact h.1 have eD1 : ∀ x, x ∈ D' → x ∈ H1 := by intro x hx have h : x ∈ D := hD'sub hx rw [hDdef] at h simp only [Finset.mem_inter] at h exact h.2 have hS0 : (A' ∪ B' ∪ C' ∪ D') ∩ H0 = C' ∪ D' := by ext x have h1 : x ∈ A' → x ∉ H0 := eA0 x have h2 : x ∈ B' → x ∉ H0 := eB0 x have h3 : x ∈ C' → x ∈ H0 := eC0 x have h4 : x ∈ D' → x ∈ H0 := eD0 x simp only [Finset.mem_inter, Finset.mem_union] tauto have hS1 : (A' ∪ B' ∪ C' ∪ D') ∩ H1 = B' ∪ D' := by ext x have h1 : x ∈ A' → x ∉ H1 := eA1 x have h2 : x ∈ B' → x ∈ H1 := eB1 x have h3 : x ∈ C' → x ∉ H1 := eC1 x have h4 : x ∈ D' → x ∈ H1 := eD1 x simp only [Finset.mem_inter, Finset.mem_union] tauto have hS0card : ((A' ∪ B' ∪ C' ∪ D') ∩ H0).card = c + d := by rw [hS0, Finset.card_union_of_disjoint (dCD.mono hC'sub hD'sub), hC'card, hD'card] have hS1card : ((A' ∪ B' ∪ C' ∪ D') ∩ H1).card = b + d := by rw [hS1, Finset.card_union_of_disjoint (dBD.mono hB'sub hD'sub), hB'card, hD'card] have hH0sdiff : H0 \ (A' ∪ B' ∪ C' ∪ D') = (C \ C') ∪ (D \ D') := by ext x have hx0 : x ∈ H0 ↔ x ∈ C ∨ x ∈ D := by rw [hH0]; exact Finset.mem_union have f1 : x ∈ A' → x ∉ C := fun hx hc => Finset.disjoint_left.1 dAC (hA'sub hx) hc have f2 : x ∈ A' → x ∉ D := fun hx hd => Finset.disjoint_left.1 dAD (hA'sub hx) hd have f3 : x ∈ B' → x ∉ C := fun hx hc => Finset.disjoint_left.1 dBC (hB'sub hx) hc have f4 : x ∈ B' → x ∉ D := fun hx hd => Finset.disjoint_left.1 dBD (hB'sub hx) hd have f5 : x ∈ C → x ∉ D' := fun hc hd => (Finset.disjoint_left.1 dCD hc) (hD'sub hd) have f6 : x ∈ D → x ∉ C' := fun hd hc => (Finset.disjoint_left.1 dCD (hC'sub hc)) hd simp only [Finset.mem_sdiff, Finset.mem_union] tauto have hH1sdiff : H1 \ (A' ∪ B' ∪ C' ∪ D') = (B \ B') ∪ (D \ D') := by ext x have hx0 : x ∈ H1 ↔ x ∈ B ∨ x ∈ D := by rw [hH1]; exact Finset.mem_union have f1 : x ∈ A' → x ∉ B := fun hx hb => Finset.disjoint_left.1 dAB (hA'sub hx) hb have f2 : x ∈ A' → x ∉ D := fun hx hd => Finset.disjoint_left.1 dAD (hA'sub hx) hd have f3 : x ∈ C' → x ∉ B := fun hx hb => (Finset.disjoint_left.1 dBC hb) (hC'sub hx) have f4 : x ∈ C' → x ∉ D := fun hx hd => Finset.disjoint_left.1 dCD (hC'sub hx) hd have f5 : x ∈ B → x ∉ D' := fun hb hd => (Finset.disjoint_left.1 dBD hb) (hD'sub hd) have f6 : x ∈ D → x ∉ B' := fun hd hb => (Finset.disjoint_left.1 dBD (hB'sub hb)) hd simp only [Finset.mem_sdiff, Finset.mem_union] tauto have hH0sdiffcard : (H0 \ (A' ∪ B' ∪ C' ∪ D')).card = (C \ C').card + (D \ D').card := by rw [hH0sdiff, Finset.card_union_of_disjoint (Disjoint.mono (Finset.sdiff_subset : C \ C' ⊆ C) (Finset.sdiff_subset : D \ D' ⊆ D) dCD)] have hH1sdiffcard : (H1 \ (A' ∪ B' ∪ C' ∪ D')).card = (B \ B').card + (D \ D').card := by rw [hH1sdiff, Finset.card_union_of_disjoint (Disjoint.mono (Finset.sdiff_subset : B \ B' ⊆ B) (Finset.sdiff_subset : D \ D' ⊆ D) dBD)] have hdCC' : (C \ C').card + C'.card = C.card := Finset.card_sdiff_add_card_eq_card hC'sub have hdDD' : (D \ D').card + D'.card = D.card := Finset.card_sdiff_add_card_eq_card hD'sub have hdBB' : (B \ B').card + B'.card = B.card := Finset.card_sdiff_add_card_eq_card hB'sub have hScard : (A' ∪ B' ∪ C' ∪ D').card = a + b + c + d := by rw [two_agent_common_bivalued_safe_partition_card_union_four (dAB.mono hA'sub hB'sub) (dAC.mono hA'sub hC'sub) (dAD.mono hA'sub hD'sub) (dBC.mono hB'sub hC'sub) (dBD.mono hB'sub hD'sub) (dCD.mono hC'sub hD'sub), hA'card, hB'card, hC'card, hD'card] have hpartcard : A.card + B.card + C.card + D.card = m := by have h := congrArg Finset.card hpart rw [two_agent_common_bivalued_safe_partition_card_union_four dAB dAC dAD dBC dBD dCD] at h simpa using h have hH0card : H0.card = C.card + D.card := by rw [hH0, Finset.card_union_of_disjoint dCD] have hH1card : H1.card = B.card + D.card := by rw [hH1, Finset.card_union_of_disjoint dBD] have hunivsdiff : (Finset.univ \ (A' ∪ B' ∪ C' ∪ D')).card + (A' ∪ B' ∪ C' ∪ D').card = m := by rw [Finset.card_sdiff_add_card_eq_card (Finset.subset_univ _), Finset.card_univ, Fintype.card_fin] clear eA0 eA1 eB0 eB1 eC0 eC1 eD0 eD1 hAdef hBdef hCdef hDdef hpart hS0 hS1 hH0sdiff hH1sdiff dAB dAC dAD dBC dBD dCD hH0 hH1 ha hb hc hd hA'sub hB'sub hC'sub hD'sub refine ⟨A' ∪ B' ∪ C' ∪ D', ?_, ?_, ?_, ?_, ?_, ?_⟩ · omega · omega · omega · omega · omega · omegaset_option maxHeartbeats 1000000 inlemma two_agent_common_bivalued_safe_partition_cost_formula {m : ℕ} (u : Fin m → ℝ) (H : Finset (Fin m)) (r a : ℝ) (hu : ∀ g, u g = if g ∈ H then r * a else a) (S : Finset (Fin m)) : additive_valuation u S = a * ((S.card : ℝ) + (r - 1) * ((S ∩ H).card : ℝ)) := by have h1 : ∀ g ∈ S, u g = a + (if g ∈ H then (r - 1) * a else 0) := by intro g _ rw [hu g] by_cases h : g ∈ H · simp only [h, if_true]; ring · simp only [h, if_false, add_zero] rw [additive_valuation, Finset.sum_congr rfl h1, Finset.sum_add_distrib, Finset.sum_ite_mem, Finset.sum_const, Finset.sum_const] simp only [nsmul_eq_mul] ringset_option maxHeartbeats 1000000 inlemma two_agent_common_bivalued_safe_partition_bundle_card_add (m : ℕ) (P : Fin m → Fin 2) : (bundle_of P 0).card + (bundle_of P 1).card = m := by have h := Finset.card_eq_sum_card_fiberwise (f := P) (s := (Finset.univ : Finset (Fin m))) (t := (Finset.univ : Finset (Fin 2))) (by intro x _; exact Finset.mem_univ _) simp only [Finset.card_univ, Fintype.card_fin] at h rw [Fin.sum_univ_two] at h simpa [bundle_of] using h.symmset_option maxHeartbeats 1000000 inlemma two_agent_common_bivalued_safe_partition_bundle_card_inter_add (m : ℕ) (P : Fin m → Fin 2) (H : Finset (Fin m)) : ((bundle_of P 0) ∩ H).card + ((bundle_of P 1) ∩ H).card = H.card := by have h := Finset.card_eq_sum_card_fiberwise (f := P) (s := H) (t := (Finset.univ : Finset (Fin 2))) (by intro x _; exact Finset.mem_univ _) rw [Fin.sum_univ_two] at h have e0 : (bundle_of P 0) ∩ H = H.filter (fun x => P x = 0) := by ext x; simp [bundle_of, and_comm] have e1 : (bundle_of P 1) ∩ H = H.filter (fun x => P x = 1) := by ext x; simp [bundle_of, and_comm] rw [e0, e1] exact h.symmset_option maxHeartbeats 2000000 inlemma two_agent_common_bivalued_safe_partition_mms_even {k m : ℕ} (hm : m = 2 * k) (r a : ℝ) (ha : 0 < a) (u : Fin m → ℝ) (H : Finset (Fin m)) (hu : ∀ g, u g = if g ∈ H then r * a else a) : a * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2) ≤ chore_maximin_share 2 u := by rw [chore_maximin_share] refine le_ciInf (fun P => ?_) have hbdd : BddAbove (Set.range fun j : Fin 2 => additive_valuation u (bundle_of P j)) := (Set.finite_range _).bddAbove have h0 : additive_valuation u (bundle_of P 0) ≤ ⨆ j, additive_valuation u (bundle_of P j) := le_ciSup hbdd 0 have h1 : additive_valuation u (bundle_of P 1) ≤ ⨆ j, additive_valuation u (bundle_of P j) := le_ciSup hbdd 1 have hc0 : (((bundle_of P 0).card : ℝ)) + ((bundle_of P 1).card : ℝ) = (m : ℝ) := by have := two_agent_common_bivalued_safe_partition_bundle_card_add m P exact_mod_cast this have hcH : (((bundle_of P 0) ∩ H).card : ℝ) + (((bundle_of P 1) ∩ H).card : ℝ) = (H.card : ℝ) := by have := two_agent_common_bivalued_safe_partition_bundle_card_inter_add m P H exact_mod_cast this have hsum : additive_valuation u (bundle_of P 0) + additive_valuation u (bundle_of P 1) = a * ((m : ℝ) + (r - 1) * (H.card : ℝ)) := by rw [two_agent_common_bivalued_safe_partition_cost_formula u H r a hu, two_agent_common_bivalued_safe_partition_cost_formula u H r a hu] have expand : a * (((bundle_of P 0).card : ℝ) + (r - 1) * (((bundle_of P 0) ∩ H).card : ℝ)) + a * (((bundle_of P 1).card : ℝ) + (r - 1) * (((bundle_of P 1) ∩ H).card : ℝ)) = a * ((((bundle_of P 0).card : ℝ) + ((bundle_of P 1).card : ℝ)) + (r - 1) * ((((bundle_of P 0) ∩ H).card : ℝ) + (((bundle_of P 1) ∩ H).card : ℝ))) := by ring rw [expand, hc0, hcH] have hk : (m : ℝ) = 2 * (k : ℝ) := by rw [hm]; push_cast; ring nlinarith [h0, h1, hsum, ha, hk]set_option maxHeartbeats 2000000 inlemma two_agent_common_bivalued_safe_partition_mms_odd {k m : ℕ} (hm : m = 2 * k + 1) (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 * (((k : ℝ) + 1) + (r - 1) * (((H.card - k : ℕ) : ℝ))) ≤ chore_maximin_share 2 u := by rw [chore_maximin_share] refine le_ciInf (fun P => ?_) have hbdd : BddAbove (Set.range fun j : Fin 2 => additive_valuation u (bundle_of P j)) := (Set.finite_range _).bddAbove have h0 : additive_valuation u (bundle_of P 0) ≤ ⨆ j, additive_valuation u (bundle_of P j) := le_ciSup hbdd 0 have h1 : additive_valuation u (bundle_of P 1) ≤ ⨆ j, additive_valuation u (bundle_of P j) := le_ciSup hbdd 1 have hc0 : (bundle_of P 0).card + (bundle_of P 1).card = m := two_agent_common_bivalued_safe_partition_bundle_card_add m P have hr1 : (0:ℝ) ≤ r - 1 := by linarith have key : ∀ (b : Finset (Fin m)), k + 1 ≤ b.card → a * (((k : ℝ) + 1) + (r - 1) * (((H.card - k : ℕ) : ℝ))) ≤ additive_valuation u b := by intro b hbc have hbh : (H.card - k : ℕ) ≤ (b ∩ H).card := by have hsd : (H \ b).card = H.card - (b ∩ H).card := Finset.card_sdiff have hcomp : (H \ b).card + b.card ≤ m := by have h1 : (H \ b).card ≤ (Finset.univ \ b : Finset (Fin m)).card := Finset.card_le_card (by intro x hx simp only [Finset.mem_sdiff, Finset.mem_univ, true_and] at hx ⊢ exact hx.2) have h2 : (Finset.univ \ b : Finset (Fin m)).card + b.card = m := by rw [Finset.card_sdiff_add_card_eq_card (Finset.subset_univ b), Finset.card_univ, Fintype.card_fin] omega omega rw [two_agent_common_bivalued_safe_partition_cost_formula u H r a hu b] refine mul_le_mul_of_nonneg_left ?_ ha.le have e1 : ((k : ℝ) + 1) ≤ (b.card : ℝ) := by exact_mod_cast hbc have e2 : (((H.card - k : ℕ) : ℝ)) ≤ ((b ∩ H).card : ℝ) := by exact_mod_cast hbh have := mul_le_mul_of_nonneg_left e2 hr1 linarith rcases Nat.lt_or_ge (bundle_of P 0).card (k + 1) with hlt | hge · have hb1 : k + 1 ≤ (bundle_of P 1).card := by omega have := key (bundle_of P 1) hb1 linarith · have hb0 : k + 1 ≤ (bundle_of P 0).card := hge have := key (bundle_of P 0) hb0 linarithset_option maxHeartbeats 3000000 inlemma two_agent_common_bivalued_safe_partition_agent_even {k m : ℕ} (hm : m = 2 * k) (hk : 1 ≤ k) (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 hr1 : (0:ℝ) ≤ r - 1 := by linarith have h3 : (Finset.univ \ S).card = m - S.card := by rw [Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, Fintype.card_fin] have hScard : S.card = k := by omega have hSccard : (Finset.univ \ S).card = k := by omega have hdel : (Finset.univ \ S) ∩ H = H \ S := by ext x; simp [and_comm] have hmms := two_agent_common_bivalued_safe_partition_mms_even hm r a ha u H hu have harith := bivalued_rounding_even_mms_arithmetic k H.card (r - 1) hk hr1 have hbdd : (0:ℝ) ≤ ((r + 1) / 2) := by linarith have hmain : ∀ (T : Finset (Fin m)) (x y : ℝ), ((T.card : ℝ)) ≤ x → (((T ∩ H).card : ℝ)) ≤ y → additive_valuation u T ≤ a * (x + (r - 1) * y) := by intro T x y hx hy rw [two_agent_common_bivalued_safe_partition_cost_formula u H r a hu T] refine mul_le_mul_of_nonneg_left ?_ ha.le have := mul_le_mul_of_nonneg_left hy hr1 linarith have h4 : ((r + 1) / 2) * (a * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2)) ≤ ((r + 1) / 2) * chore_maximin_share 2 u := mul_le_mul_of_nonneg_left hmms hbdd have h2 : 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 harith ha.le have key : a * ((1 + (r - 1) / 2) * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2)) = ((r + 1) / 2) * (a * ((k : ℝ) + (r - 1) * (H.card : ℝ) / 2)) := by ring constructor · have h1 : additive_valuation u S ≤ a * ((k : ℝ) + (r - 1) * ((((H.card + 1) / 2 : ℕ) : ℝ))) := by refine hmain S (k : ℝ) ((((H.card + 1) / 2 : ℕ) : ℝ)) ?_ ?_ · rw [hScard] · exact_mod_cast hh linarith · have h1 : additive_valuation u (Finset.univ \ S) ≤ a * ((k : ℝ) + (r - 1) * ((((H.card + 1) / 2 : ℕ) : ℝ))) := by refine hmain (Finset.univ \ S) (k : ℝ) ((((H.card + 1) / 2 : ℕ) : ℝ)) ?_ ?_ · rw [hSccard] · rw [hdel]; exact_mod_cast hhc linarithset_option maxHeartbeats 3000000 inlemma two_agent_common_bivalued_safe_partition_agent_odd {k m : ℕ} (hm : m = 2 * k + 1) (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 hr1 : (0:ℝ) ≤ r - 1 := by linarith have hmms := two_agent_common_bivalued_safe_partition_mms_odd hm r a hr ha u H hu have harith := bivalued_rounding_odd_mms_arithmetic k H.card (r - 1) hr1 have hbdd : (0:ℝ) ≤ ((r + 1) / 2) := by linarith have hdel : (Finset.univ \ S) ∩ H = H \ S := by ext x; simp [and_comm] have hmain : ∀ (T : Finset (Fin m)) (x y : ℝ), ((T.card : ℝ)) ≤ x → (((T ∩ H).card : ℝ)) ≤ y → additive_valuation u T ≤ a * (x + (r - 1) * y) := by intro T x y hx hy rw [two_agent_common_bivalued_safe_partition_cost_formula u H r a hu T] refine mul_le_mul_of_nonneg_left ?_ ha.le have := mul_le_mul_of_nonneg_left hy hr1 linarith have hY : a * ((1 + (r - 1) / 2) * ((k : ℝ) + 1 + (r - 1) * (((H.card - k : ℕ) : ℝ)))) = ((r + 1) / 2) * (a * ((k : ℝ) + 1 + (r - 1) * (((H.card - k : ℕ) : ℝ)))) := by ring have hmid : a * (((k : ℝ) + 1) + (r - 1) * ((((H.card + 1) / 2 : ℕ) : ℝ))) ≤ ((r + 1) / 2) * (a * ((k : ℝ) + 1 + (r - 1) * (((H.card - k : ℕ) : ℝ)))) := by rw [← hY]; exact mul_le_mul_of_nonneg_left harith ha.le have h4 : ((r + 1) / 2) * (a * ((k : ℝ) + 1 + (r - 1) * (((H.card - k : ℕ) : ℝ)))) ≤ ((r + 1) / 2) * chore_maximin_share 2 u := mul_le_mul_of_nonneg_left hmms hbdd constructor · have h1 : additive_valuation u S ≤ a * (((k : ℝ) + 1) + (r - 1) * ((((H.card + 1) / 2 : ℕ) : ℝ))) := by refine hmain S ((k : ℝ) + 1) ((((H.card + 1) / 2 : ℕ) : ℝ)) ?_ ?_ · have : S.card ≤ k + 1 := by omega exact_mod_cast this · exact_mod_cast hh linarith · have h1 : additive_valuation u (Finset.univ \ S) ≤ a * (((k : ℝ) + 1) + (r - 1) * ((((H.card + 1) / 2 : ℕ) : ℝ))) := by refine hmain (Finset.univ \ S) ((k : ℝ) + 1) ((((H.card + 1) / 2 : ℕ) : ℝ)) ?_ ?_ · have h3 : (Finset.univ \ S).card = m - S.card := by rw [Finset.card_sdiff, Finset.inter_univ, Finset.card_univ, Fintype.card_fin] have : (Finset.univ \ S).card ≤ k + 1 := by omega exact_mod_cast this · rw [hdel]; exact_mod_cast hhc linarith/-- Existence of a safe two-way partition for two agents with common bivalued chore costs, achieving at most ((r+1)/2) * MMS_i for both bundles and both agents. -/theorem two_agent_common_bivalued_safe_partition (r : ℝ) (hr1 : 1 ≤ r) (hr2 : r ≤ 2) (m : ℕ) (c : Fin 2 → Fin m → ℝ) (hc : is_scaled_bivalued_chores r c) : ∃ S : Finset (Fin m), ∀ 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 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 have halpha : (0:ℝ) ≤ (r + 1) / 2 := by linarith rcases Nat.eq_zero_or_pos m with hm0 | hmpos · subst hm0 have hHempty : ∀ i : Fin 2, H i = ∅ := by intro i apply Finset.eq_empty_iff_forall_notMem.mpr intro x exact x.elim0 have hzero : ∀ (i : Fin 2) (T : Finset (Fin 0)), additive_valuation (c i) T = 0 := by intro i T have hT : T = ∅ := by apply Finset.eq_empty_iff_forall_notMem.mpr intro x exact x.elim0 rw [hT, additive_valuation, Finset.sum_empty] have hmms : ∀ i : Fin 2, (0:ℝ) ≤ chore_maximin_share 2 (c i) := by intro i have h := two_agent_common_bivalued_safe_partition_mms_even (k := 0) (m := 0) (rfl : (0:ℕ) = 2 * 0) r (a i) (ha i) (c i) (H i) (hval i) rw [hHempty i] at h simpa using h refine ⟨∅, fun i => ⟨?_, ?_⟩⟩ · rw [hzero i ∅]; exact mul_nonneg halpha (hmms i) · rw [hzero i (Finset.univ \ (∅ : Finset (Fin 0)))] exact mul_nonneg halpha (hmms i) · obtain ⟨S, hs, hsc, h0, h0c, h1, h1c⟩ := two_agent_common_bivalued_safe_partition_balance m (H 0) (H 1) refine ⟨S, fun i => ?_⟩ rcases Nat.even_or_odd m with ⟨k, hk⟩ | ⟨k, hk⟩ · have hmk : m = 2 * k := by omega have hk1 : 1 ≤ k := by omega fin_cases i · exact two_agent_common_bivalued_safe_partition_agent_even hmk hk1 r (a 0) hr1 (ha 0) (c 0) (H 0) S (hval 0) hs hsc h0 h0c · exact two_agent_common_bivalued_safe_partition_agent_even hmk hk1 r (a 1) hr1 (ha 1) (c 1) (H 1) S (hval 1) hs hsc h1 h1c · have hmk : m = 2 * k + 1 := by omega fin_cases i · exact two_agent_common_bivalued_safe_partition_agent_odd hmk r (a 0) hr1 (ha 0) (c 0) (H 0) S (hval 0) hs hsc h0 h0c · exact two_agent_common_bivalued_safe_partition_agent_odd hmk r (a 1) hr1 (ha 1) (c 1) (H 1) S (hval 1) hs hsc h1 h1c