cooperative_game_direct_sum_calibration
Let (N_1, v_1), ..., (N_m, v_m) (m ≥ 2) be cooperative games with v_j(∅) = 0 and nonnegative values on pairwise disjoint finite player sets, such that W_j = v_j(N_j) > 0 for each j. For each component j, let r_j ∈ (0, 1] be its optimal multiplicative least-core guarantee, meaning there exists a nonnegative vector y on N_j summing to W_j such that y(T) ≥ r_j v_j(T) for all T ⊆ N_j with v_j(T) > 0, and for every nonnegative vector y on N_j summing to W_j there exists T ⊆ N_j with v_j(T) > 0 such that y(T) ≤ r_j v_j(T). Let (N_bar, v_bar) be their direct sum, where N_bar = ⋃_{j=1}^m N_j and v_bar(S) = ∑_{j=1}^m v_j(S ∩ N_j), with grand coalition value W_bar = ∑_{j=1}^m W_j. Then the first-stage optimum of the direct-sum game over all proper coalitions S ⊊ N_bar with v_bar(S) > 0 is α* = W_bar / (∑_{j=1}^m W_j / r_j), meaning there exists a nonnegative vector x on N_bar summing to W_bar such that x(S) ≥ α* v_bar(S) for all proper coalitions S ⊊ N_bar with v_bar(S) > 0, and every nonnegative vector x on N_bar summing to W_bar satisfies x(S) ≤ α* v_bar(S) for some proper coalition S ⊊ N_bar with v_bar(S) > 0. Furthermore, every first-stage optimal imputation x (every nonnegative vector x on N_bar summing to W_bar such that x(S) ≥ α* v_bar(S) for all proper coalitions S ⊊ N_bar with v_bar(S) > 0) assigns component totals ∑_{i ∈ N_j} x(j, i) = α* W_j / r_j for all j. Consequently, α* ≤ 1, with equality if and only if every component has a nonempty core (there exists a nonnegative vector y on N_j summing to W_j such that y(T) ≥ v_j(T) for all T ⊆ N_j).
Statement
theorem cooperative_game_direct_sum_calibration {M : Type*} [DecidableEq M] [Fintype M] {N : M → Type*} [∀ j, DecidableEq (N j)] [∀ j, Fintype (N j)] (v : ∀ j, Finset (N j) → ℝ) (r : M → ℝ) (hm : 2 ≤ Fintype.card M) (hv_empty : ∀ j, v j ∅ = 0) (h_nonneg : ∀ j S, 0 ≤ v j S) (hW : ∀ j, 0 < v j Finset.univ) (hr_bounds : ∀ j, 0 < r j ∧ r j ≤ 1) (hr : ∀ j, (∃ y : N j → ℝ, (∀ i, 0 ≤ y i) ∧ Finset.univ.sum y = v j Finset.univ ∧ ∀ T : Finset (N j), 0 < v j T → r j * v j T ≤ T.sum y) ∧ (∀ y : N j → ℝ, (∀ i, 0 ≤ y i) → Finset.univ.sum y = v j Finset.univ → ∃ T : Finset (N j), 0 < v j T ∧ T.sum y ≤ r j * v j T)) : let W := fun j => v j Finset.univ let W_bar := Finset.univ.sum W let α_star := W_bar / Finset.univ.sum (fun j => W j / r j) let v_bar : Finset (Σ j, N j) → ℝ := fun S => Finset.univ.sum (fun j => v j (Finset.univ.filter (fun (i : N j) => (⟨j, i⟩ : Σ j, N j) ∈ S))) ((∃ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) ∧ Finset.univ.sum x = v_bar Finset.univ ∧ ∀ S : Finset (Σ j, N j), S ≠ Finset.univ → 0 < v_bar S → α_star * v_bar S ≤ S.sum x) ∧ (∀ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) → Finset.univ.sum x = v_bar Finset.univ → ∃ S : Finset (Σ j, N j), S ≠ Finset.univ ∧ 0 < v_bar S ∧ S.sum x ≤ α_star * v_bar S)) ∧ (∀ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) → Finset.univ.sum x = v_bar Finset.univ → (∀ S : Finset (Σ j, N j), S ≠ Finset.univ → 0 < v_bar S → α_star * v_bar S ≤ S.sum x) → ∀ j : M, Finset.univ.sum (fun a => x ⟨j, a⟩) = α_star * W j / r j) ∧ α_star ≤ 1 ∧ (α_star = 1 ↔ ∀ j : M, ∃ y : N j → ℝ, (∀ i, 0 ≤ y i) ∧ Finset.univ.sum y = v j Finset.univ ∧ ∀ T : Finset (N j), v j T ≤ T.sum y)
- Formalizes
- scout/2610-29731-computing-the-nucleon-of-matching-games.md:1148 Lemma 4 (arXiv:2610.29731)
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- cooperative_game_core_nonempty_iff_optimal_guarantee_eq_oneFor a cooperative game v on a finite player set N with nonnegative values and positive grand coalition value v(N) > 0, an optimal…
Read back from the Lean
Let $M$ be a finite type with decidable equality having at least 2 elements (hm : 2 ≤ Fintype.card M).
Let $N : M \to \text{Type*}$ be a family of finite types with decidable equality.
Let $v : \prod_{j \in M} (\text{Finset} (N j) \to \mathbb{R})$ be a family of characteristic functions (cooperative games), and let $r : M \to \mathbb{R}$.
Assume:
1. hv_empty: for all $j \in M$, $v_j(\emptyset) = 0$.
2. h_nonneg: for all $j \in M$ and all $S \subseteq N_j$, $v_j(S) \ge 0$.
3. hW: for all $j \in M$, $v_j(N_j) > 0$ (the grand coalition has strictly positive value).
4. hr_bounds: for all $j \in M$, $0 < r_j \le 1$.
5. hr: for each $j \in M$, $r_j$ is the exact multiplicative core relaxation factor for game $v_j$, in the sense that:
- there exists an imputation $y : N_j \to \mathbb{R}$ ($y \ge 0$ and $\sum_{i \in N_j} y_i = v_j(N_j)$) such that for all $T \subseteq N_j$ with $v_j(T) > 0$, $r_j \cdot v_j(T) \le \sum_{i \in T} y_i$; and
- for every imputation $y : N_j \to \mathbb{R}$ ($y \ge 0$ and $\sum_{i \in N_j} y_i = v_j(N_j)$), there exists some $T \subseteq N_j$ with $v_j(T) > 0$ such that $\sum_{i \in T} y_i \le r_j \cdot v_j(T)$.
Define:
- $W_j = v_j(N_j)$ for each $j \in M$,
- $\bar{W} = \sum_{j \in M} W_j$,
- $\alpha^* = \bar{W} / \sum_{j \in M} (W_j / r_j)$,
- $\bar{v} : \text{Finset} (\Sigma_{j \in M} N_j) \to \mathbb{R}$ as the direct sum game $\bar{v}(S) = \sum_{j \in M} v_j(\{ i \in N_j \mid \langle j, i \rangle \in S \})$.
Then the theorem asserts the conjunction of four statements:
1. **Relaxed core existence and tightness for the direct sum game**:
- There exists an imputation $x : (\Sigma_{j \in M} N_j) \to \mathbb{R}$ ($x \ge 0$ and $\sum_{p} x_p = \bar{v}(\text{univ})$) such that for all proper coalitions $S \subsetneq \Sigma_{j \in M} N_j$ with $\bar{v}(S) > 0$, $\alpha^* \cdot \bar{v}(S) \le \sum_{p \in S} x_p$; and
- For every imputation $x : (\Sigma_{j \in M} N_j) \to \mathbb{R}$ ($x \ge 0$ and $\sum_{p} x_p = \bar{v}(\text{univ})$), there exists a proper coalition $S \subsetneq \Sigma_{j \in M} N_j$ with $\bar{v}(S) > 0$ such that $\sum_{p \in S} x_p \le \alpha^* \cdot \bar{v}(S)$.
2. **Componentwise aggregate allocation**:
For any imputation $x : (\Sigma_{j \in M} N_j) \to \mathbb{R}$ ($x \ge 0$, $\sum_{p} x_p = \bar{v}(\text{univ})$) that satisfies $\alpha^* \cdot \bar{v}(S) \le \sum_{p \in S} x_p$ for all proper coalitions $S \subsetneq \Sigma_{j \in M} N_j$ with $\bar{v}(S) > 0$, the sum of allocations to the players of each game $j \in M$, $\sum_{a \in N_j} x(\langle j, a \rangle)$, is equal to $\alpha^* \cdot W_j / r_j$.
3. **Bound on $\alpha^*$**:
$\alpha^* \le 1$.
4. **Exact core non-emptiness characterization**:
$\alpha^* = 1$ if and only if for every $j \in M$, the game $v_j$ has a non-empty core (i.e., there exists $y : N_j \to \mathbb{R}$ with $y \ge 0$, $\sum_{i \in N_j} y_i = v_j(N_j)$, and $v_j(T) \le \sum_{i \in T} y_i$ for all $T \subseteq N_j$).
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 theorem calibrates the first-stage optimal guarantee α* for the direct sum of m ≥ 2 cooperative games. An optimal imputation x* on the grand coalition is explicitly constructed by scaling each component's optimal guarantee imputation y_j by α* / r_j, which guarantees that x* satisfies the budget constraint ∑ x* = W_bar and achieves x*(S) ≥ α* v_bar(S) for all coalitions S. Tightness and the uniqueness of component totals are proved by observing that the component totals s_j of any valid imputation sum to W_bar = ∑_j α* W_j / r_j; pulling back the component guarantees via single-component embedded subcoalitions forces s_j = α* W_j / r_j for every optimal imputation x. Finally, α* ≤ 1 follows because r_j ≤ 1 implies W_j / r_j ≥ W_j, with equality holding if and only if every r_j = 1, which characterizes every component having a nonempty core.
The sum of a vector x over a coalition S in the direct-sum game partitions into the sum over each component j of the sum of x(j, ·) over S ∩ N_j.
Expressing the sum over S via an indicator function on the grand coalition and applying Fintype.sum_sigma splits the sum over the disjoint union Σ_j N_j into iterated sums ∑_j ∑_{i ∈ N_j}. Rewriting the inner indicator sum with Finset.sum_filter restricts the summation to the component projection S ∩ N_j.
uses
Finset.sum_ite_mem_eq,Fintype.sum_sigma,Finset.sum_filterrw [← Finset.sum_ite_mem_eq S x, Fintype.sum_sigma] congr 1; ext j exact (Finset.sum_filter (fun (i : N j) => (⟨j, i⟩ : Σ j, N j) ∈ S) (fun i => x ⟨j, i⟩)).symm
If two vectors s, t on a finite set satisfy t_j ≤ s_j for all j and have equal totals ∑_j s_j = ∑_j t_j, then s_j = t_j for all j.
The sum of differences ∑_k (s_k - t_k) distributes to ∑ s - ∑ t = 0 by Finset.sum_sub_distrib. Since each term is nonnegative, Finset.sum_eq_zero_iff_of_nonneg implies that each difference s_j - t_j is zero, giving s_j = t_j.
uses
Finset.sum_sub_distrib,Finset.sum_eq_zero_iff_of_nonneghave hdiff : Finset.univ.sum (fun k => s k - t k) = 0 := by rw [Finset.sum_sub_distrib, hsum, sub_self] have hdiff_nonneg : ∀ k ∈ Finset.univ, 0 ≤ s k - t k := fun k _ => sub_nonneg.mpr (hle k) have hzero := (Finset.sum_eq_zero_iff_of_nonneg hdiff_nonneg).mp hdiff j (Finset.mem_univ j) exact sub_eq_zero.mp hzero
If two vectors s, t on a nonempty finite set satisfy ∑_j s_j ≤ ∑_j t_j, then s_j ≤ t_j for some index j.
Assuming for contradiction that s_j > t_j for all j in a nonempty set, Finset.sum_lt_sum_of_nonempty would imply ∑_j t_j < ∑_j s_j, contradicting ∑_j s_j ≤ ∑_j t_j.
uses
Finset.sum_lt_sum_of_nonemptyby_contra! h have : Finset.univ.sum t < Finset.univ.sum s := Finset.sum_lt_sum_of_nonempty Finset.univ_nonempty (fun j _ => h j) linarith
The direct-sum value of a single-component embedded coalition {j} × T equals v_j(T).
The intersection of {j} × T with component k is T when k = j and empty when k ≠ j. Since v_k(∅) = 0 for all k ≠ j, Finset.sum_eq_single_of_mem reduces the sum defining the direct-sum characteristic function to the single term v_j(T).
uses
Finset.sum_eq_single_of_memhave h_filter : ∀ k, (Finset.univ.filter (fun (i : N k) => (⟨k, i⟩ : Σ j, N j) ∈ T.image (fun i => ⟨j, i⟩))) = if h : k = j then h ▸ T else ∅ := by intro k; ext i; simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image] split_ifs with h · subst h; simp · simp only [Sigma.mk.inj_iff, Finset.notMem_empty, iff_false] rintro ⟨a, -, rfl, -⟩; exact h rfl simp_rw [h_filter] rw [Finset.sum_eq_single_of_mem j (Finset.mem_univ j)] · simp · intro k _ hk; simp [hk, hv_empty k]
Any single-component embedded coalition {j} × T is a proper subset of the grand coalition.
Because there are at least two components (|M| ≥ 2), there is some component k ≠ j. Since v_k(N_k) > 0 and v_k(∅) = 0, N_k is nonempty, so any player b ∈ N_k provides an element ⟨k, b⟩ in the grand coalition outside {j} × T.
uses
Fintype.card_eq_one_iffhave : ∃ k : M, k ≠ j := by by_contra! h; have : Fintype.card M = 1 := Fintype.card_eq_one_iff.mpr ⟨j, h⟩; omega obtain ⟨k, hkj⟩ := this have h_ne : Nonempty (N k) := by by_contra h_empty; have h_univ : (Finset.univ : Finset (N k)) = ∅ := by ext x; exact (h_empty ⟨x⟩).elim have := hW k; rw [h_univ, hv_empty] at this; linarith obtain ⟨b⟩ := h_ne; intro h_eq have : (⟨k, b⟩ : Σ j, N j) ∈ Finset.univ := Finset.mem_univ _ rw [← h_eq, Finset.mem_image] at this; obtain ⟨a, -, ha⟩ := this have : k = j := (Sigma.mk.inj_iff.mp ha.symm).1; exact hkj this
The sum of a vector x over the embedded coalition {j} × T equals the sum of x(j, ·) over T.
The embedding i ↦ ⟨j, i⟩ is injective on T, so Finset.sum_image identifies the sum over the embedded image with the sum over T.
uses
Finset.sum_imageapply Finset.sum_image; intro a _ b _ hab; exact (Sigma.mk.inj_iff.mp hab).2.eq
The component grand values W_j and total value W_bar are strictly positive, and α* satisfies 0 < α* ≤ 1.
From W_j > 0 and |M| ≥ 2, Finset.sum_pos yields W_bar > 0. Because r_j ∈ (0, 1], each W_j ≤ W_j / r_j, so Finset.sum_le_sum implies W_bar ≤ ∑_j (W_j / r_j). Thus the denominator of α* is strictly positive, giving α* > 0 and α* ≤ 1 by div_le_one.
uses
Finset.sum_pos,Finset.sum_le_sum,div_le_oneintro W W_bar α_star v_bar have hM_ne : (Finset.univ : Finset M).Nonempty := by rw [Finset.univ_nonempty_iff]; exact Fintype.card_pos_iff.mp (by omega) have h_ne : Nonempty M := Fintype.card_pos_iff.mp (by omega) have hW_pos : ∀ j, 0 < W j := hW have hW_bar_pos : 0 < W_bar := Finset.sum_pos (fun j _ => hW_pos j) hM_ne have h_le : ∀ j ∈ (Finset.univ : Finset M), W j ≤ W j / r j := fun j _ => by have hrj := hr_bounds j have : W j * r j ≤ W j := by nlinarith [hW j] exact (le_div_iff₀ hrj.1).mpr this have h_sum_le : W_bar ≤ Finset.univ.sum (fun j => W j / r j) := Finset.sum_le_sum h_le have h_denom_pos : 0 < Finset.univ.sum (fun j => W j / r j) := by linarith have hα_pos : 0 < α_star := div_pos hW_bar_pos h_denom_pos have hα_le_one : α_star ≤ 1 := (div_le_one h_denom_pos).mpr h_sum_le
The direct sum evaluates to v_bar(N_bar) = W_bar, and each component admits an optimal guarantee vector y_j satisfying y_j(T) ≥ r_j v_j(T) for all T ⊆ N_j.
Evaluating v_bar on the grand coalition gives ∑_j v_j(N_j) = W_bar. For each component j, the hypothesis on r_j provides an imputation y_j summing to W_j with y_j(T) ≥ r_j v_j(T) whenever v_j(T) > 0. When v_j(T) = 0, the inequality holds trivially by Finset.sum_nonneg because y_j ≥ 0.
uses
Finset.sum_nonneghave hv_univ : v_bar Finset.univ = W_bar := by dsimp [v_bar, W_bar, W] congr 1; ext j; congr 1; ext i simp only [Finset.mem_filter, Finset.mem_univ, true_and] choose y hy_nonneg hy_sum hy_core using (fun j => (hr j).1) have hy_core_all : ∀ j T, r j * v j T ≤ T.sum (y j) := by intro j T by_cases hT : 0 < v j T · exact hy_core j T hT · have h0 : v j T = 0 := le_antisymm (not_lt.mp hT) (h_nonneg j T) rw [h0, mul_zero] exact Finset.sum_nonneg (fun i _ => hy_nonneg j i)
There exists an imputation x* on the grand coalition guaranteeing x*(S) ≥ α* v_bar(S) for all coalitions S.
Define x*(j, i) = (α* / r_j) y_j(i). Nonnegativity holds because α*, r_j > 0 and y_j ≥ 0. The sum of x* on component j is (α* / r_j) W_j, and summing over j yields α* ∑_j (W_j / r_j) = W_bar by div_mul_cancel₀. For any coalition S, cooperative_game_direct_sum_calibration_sum_partition splits x*(S) into ∑_j (α* / r_j) y_j(S ∩ N_j) ≥ ∑_j α* v_j(S ∩ N_j) = α* v_bar(S).
uses
cooperative_game_direct_sum_calibration_sum_partition,Finset.mul_sum,div_mul_cancel₀have hx_star : (∃ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) ∧ Finset.univ.sum x = v_bar Finset.univ ∧ ∀ S : Finset (Σ j, N j), S ≠ Finset.univ → 0 < v_bar S → α_star * v_bar S ≤ S.sum x) := by let x : (Σ j, N j) → ℝ := fun ⟨j, i⟩ => (α_star / r j) * y j i refine ⟨x, ?_, ?_, ?_⟩ · rintro ⟨j, i⟩ exact mul_nonneg (le_of_lt (div_pos hα_pos (hr_bounds j).1)) (hy_nonneg j i) · rw [hv_univ, Fintype.sum_sigma] have h1 : ∀ j, Finset.univ.sum (fun i => x ⟨j, i⟩) = (α_star / r j) * W j := by intro j dsimp [x] rw [← Finset.mul_sum, hy_sum] have h2 : (fun j => Finset.univ.sum (fun i => x ⟨j, i⟩)) = (fun j => α_star * (W j / r j)) := by ext j rw [h1] ring rw [h2, ← Finset.mul_sum] exact div_mul_cancel₀ W_bar (ne_of_gt h_denom_pos) · intro S _ _ dsimp [v_bar] rw [cooperative_game_direct_sum_calibration_sum_partition S x, Finset.mul_sum] apply Finset.sum_le_sum intro j _ let Tj := Finset.univ.filter (fun (i : N j) => (⟨j, i⟩ : Σ j, N j) ∈ S) have h_scale : Tj.sum (fun i => x ⟨j, i⟩) = (α_star / r j) * Tj.sum (y j) := by dsimp [x] rw [← Finset.mul_sum] rw [h_scale] have h_c := hy_core_all j Tj have h_pos : 0 ≤ α_star / r j := le_of_lt (div_pos hα_pos (hr_bounds j).1) have h_le := mul_le_mul_of_nonneg_left h_c h_pos have h_id : (α_star / r j) * (r j * v j Tj) = α_star * v j Tj := by rw [← mul_assoc, div_mul_cancel₀ α_star (ne_of_gt (hr_bounds j).1)] rwa [h_id] at h_le
The guarantee α* is tight: every imputation x on the grand coalition satisfies x(S) ≤ α* v_bar(S) for some proper coalition S with v_bar(S) > 0.
Let s_j = ∑_{i ∈ N_j} x(j, i) and t_j = α* W_j / r_j. Both families sum to W_bar, so cooperative_game_direct_sum_calibration_exists_le_of_sum_le provides a component j with s_j ≤ t_j. If s_j = 0, the full component coalition S = {j} × N_j is proper (by cooperative_game_direct_sum_calibration_image_ne_univ), has v_bar(S) = W_j > 0 (by cooperative_game_direct_sum_calibration_v_bar_image), and gives x(S) = 0 ≤ α* W_j. If s_j > 0, scaling x on component j to an imputation y on N_j yields a coalition T with v_j(T) > 0 and y(T) ≤ r_j v_j(T); embedding T as S = {j} × T gives a proper coalition with x(S) ≤ (s_j r_j / W_j) v_j(T) ≤ α* v_bar(S).
uses
cooperative_game_direct_sum_calibration_exists_le_of_sum_le,cooperative_game_direct_sum_calibration_v_bar_image,cooperative_game_direct_sum_calibration_image_ne_univhave h_tight : (∀ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) → Finset.univ.sum x = v_bar Finset.univ → ∃ S : Finset (Σ j, N j), S ≠ Finset.univ ∧ 0 < v_bar S ∧ S.sum x ≤ α_star * v_bar S) := by intro x hx_nonneg hx_sum let s : M → ℝ := fun j => Finset.univ.sum (fun a => x ⟨j, a⟩) let t : M → ℝ := fun j => α_star * W j / r j have hs_sum : Finset.univ.sum s = W_bar := by rw [← Fintype.sum_sigma] exact hx_sum.trans hv_univ have ht_sum : Finset.univ.sum t = W_bar := by have h1 : (fun j => α_star * W j / r j) = (fun j => α_star * (W j / r j)) := by ext j; ring dsimp [t] rw [h1, ← Finset.mul_sum] exact div_mul_cancel₀ W_bar (ne_of_gt h_denom_pos) have h_exist : ∃ j, s j ≤ t j := by apply cooperative_game_direct_sum_calibration_exists_le_of_sum_le h_ne rw [hs_sum, ht_sum] obtain ⟨j, hj_le⟩ := h_exist have hs_nonneg : 0 ≤ s j := Finset.sum_nonneg (fun i _ => hx_nonneg ⟨j, i⟩) by_cases hs_zero : s j = 0 · let S : Finset (Σ j, N j) := Finset.univ.image (fun i => ⟨j, i⟩) have hvS : v_bar S = W j := cooperative_game_direct_sum_calibration_v_bar_image v hv_empty j Finset.univ have hSx : S.sum x = s j := cooperative_game_direct_sum_calibration_sum_image j Finset.univ x refine ⟨S, ?_, ?_, ?_⟩ · exact cooperative_game_direct_sum_calibration_image_ne_univ v hm hv_empty hW j Finset.univ · rw [hvS]; exact hW_pos j · rw [hvS, hSx, hs_zero] exact mul_nonneg (le_of_lt hα_pos) (le_of_lt (hW_pos j)) · have hs_pos : 0 < s j := lt_of_le_of_ne hs_nonneg (Ne.symm hs_zero) let y_scaled : N j → ℝ := fun a => (W j / s j) * x ⟨j, a⟩ have hy_scaled_nonneg : ∀ i, 0 ≤ y_scaled i := fun i => mul_nonneg (div_nonneg (le_of_lt (hW_pos j)) (le_of_lt hs_pos)) (hx_nonneg ⟨j, i⟩) have hy_scaled_sum : Finset.univ.sum y_scaled = v j Finset.univ := by dsimp [y_scaled] rw [← Finset.mul_sum] have : Finset.univ.sum (fun a => x ⟨j, a⟩) = s j := rfl rw [this, div_mul_cancel₀ (W j) (ne_of_gt hs_pos)] obtain ⟨T, hT_pos, hT_le⟩ := (hr j).2 y_scaled hy_scaled_nonneg hy_scaled_sum let S : Finset (Σ j, N j) := T.image (fun i => ⟨j, i⟩) have hvS : v_bar S = v j T := cooperative_game_direct_sum_calibration_v_bar_image v hv_empty j T have hSx : S.sum x = T.sum (fun a => x ⟨j, a⟩) := cooperative_game_direct_sum_calibration_sum_image j T x refine ⟨S, ?_, ?_, ?_⟩ · exact cooperative_game_direct_sum_calibration_image_ne_univ v hm hv_empty hW j T · rw [hvS]; exact hT_pos · rw [hvS, hSx] have h_scale : T.sum (fun a => x ⟨j, a⟩) = (s j / W j) * T.sum y_scaled := by dsimp [y_scaled] rw [← Finset.mul_sum] have h_cancel : (s j / W j) * (W j / s j) = 1 := by rw [div_mul_div_comm, mul_comm (s j), div_self (ne_of_gt (mul_pos (hW_pos j) hs_pos))] rw [← mul_assoc, h_cancel, one_mul] rw [h_scale] have h_step1 : (s j / W j) * T.sum y_scaled ≤ (s j / W j) * (r j * v j T) := mul_le_mul_of_nonneg_left hT_le (div_nonneg (le_of_lt hs_pos) (le_of_lt (hW_pos j))) have h_step2 : (s j / W j) * (r j * v j T) ≤ α_star * v j T := by have hrj := (hr_bounds j).1 have hWj := hW_pos j have : (s j / W j) * (r j * v j T) = (s j * r j / W j) * v j T := by ring rw [this] apply mul_le_mul_of_nonneg_right _ (le_of_lt hT_pos) have hj_le' : s j ≤ α_star * W j / r j := hj_le rw [div_le_iff₀ hWj] have : s j * r j ≤ α_star * W j := by have : s j * r j ≤ (α_star * W j / r j) * r j := mul_le_mul_of_nonneg_right hj_le' (le_of_lt hrj) rwa [div_mul_cancel₀ (α_star * W j) (ne_of_gt hrj)] at this exact this exact le_trans h_step1 h_step2
Every first-stage optimal imputation x satisfies ∑_{i ∈ N_j} x(j, i) = α* W_j / r_j for all components j.
Let s_j = ∑_{i ∈ N_j} x(j, i) and t_j = α* W_j / r_j. The total s_j cannot be zero, as testing the guarantee on {j} × N_j would imply 0 ≥ α* W_j > 0. For s_j > 0, rescaling x on component j and testing against the subcoalition witnessing the optimality of r_j forces α* v_j(T) ≤ x({j} × T) ≤ (s_j r_j / W_j) v_j(T), implying t_j ≤ s_j. Since ∑_j s_j = W_bar = ∑_j t_j and t_j ≤ s_j for all j, cooperative_game_direct_sum_calibration_sum_eq_of_le_all yields s_j = t_j for all j.
uses
cooperative_game_direct_sum_calibration_image_ne_univ,cooperative_game_direct_sum_calibration_v_bar_image,cooperative_game_direct_sum_calibration_sum_image,cooperative_game_direct_sum_calibration_sum_eq_of_le_allhave h_unique : (∀ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) → Finset.univ.sum x = v_bar Finset.univ → (∀ S : Finset (Σ j, N j), S ≠ Finset.univ → 0 < v_bar S → α_star * v_bar S ≤ S.sum x) → ∀ j : M, Finset.univ.sum (fun a => x ⟨j, a⟩) = α_star * W j / r j) := by intro x hx_nonneg hx_sum h_core let s : M → ℝ := fun j => Finset.univ.sum (fun a => x ⟨j, a⟩) let t : M → ℝ := fun j => α_star * W j / r j have hs_sum : Finset.univ.sum s = W_bar := by rw [← Fintype.sum_sigma] exact hx_sum.trans hv_univ have ht_sum : Finset.univ.sum t = W_bar := by have h1 : (fun j => α_star * W j / r j) = (fun j => α_star * (W j / r j)) := by ext j; ring dsimp [t] rw [h1, ← Finset.mul_sum] exact div_mul_cancel₀ W_bar (ne_of_gt h_denom_pos) have h_le_each : ∀ j, t j ≤ s j := by intro j have hs_nonneg : 0 ≤ s j := Finset.sum_nonneg (fun i _ => hx_nonneg ⟨j, i⟩) by_cases hs_zero : s j = 0 · exfalso let Suniv : Finset (Σ j, N j) := Finset.univ.image (fun i => ⟨j, i⟩) have hS_ne : Suniv ≠ Finset.univ := cooperative_game_direct_sum_calibration_image_ne_univ v hm hv_empty hW j Finset.univ have hvS : v_bar Suniv = W j := cooperative_game_direct_sum_calibration_v_bar_image v hv_empty j Finset.univ have hS_pos : 0 < v_bar Suniv := by rw [hvS]; exact hW_pos j have h_bound := h_core Suniv hS_ne hS_pos have hSx : Suniv.sum x = s j := cooperative_game_direct_sum_calibration_sum_image j Finset.univ x rw [hvS, hSx, hs_zero] at h_bound have : 0 < α_star * W j := mul_pos hα_pos (hW_pos j) linarith · have hs_pos : 0 < s j := lt_of_le_of_ne hs_nonneg (Ne.symm hs_zero) let y_scaled : N j → ℝ := fun a => (W j / s j) * x ⟨j, a⟩ have hy_scaled_nonneg : ∀ i, 0 ≤ y_scaled i := fun i => mul_nonneg (div_nonneg (le_of_lt (hW_pos j)) (le_of_lt hs_pos)) (hx_nonneg ⟨j, i⟩) have hy_scaled_sum : Finset.univ.sum y_scaled = v j Finset.univ := by dsimp [y_scaled] rw [← Finset.mul_sum] have : Finset.univ.sum (fun a => x ⟨j, a⟩) = s j := rfl rw [this, div_mul_cancel₀ (W j) (ne_of_gt hs_pos)] obtain ⟨T, hT_pos, hT_le⟩ := (hr j).2 y_scaled hy_scaled_nonneg hy_scaled_sum let S : Finset (Σ j, N j) := T.image (fun i => ⟨j, i⟩) have hS_ne : S ≠ Finset.univ := cooperative_game_direct_sum_calibration_image_ne_univ v hm hv_empty hW j T have hvS : v_bar S = v j T := cooperative_game_direct_sum_calibration_v_bar_image v hv_empty j T have hS_pos : 0 < v_bar S := by rw [hvS]; exact hT_pos have h_bound := h_core S hS_ne hS_pos have hSx : S.sum x = T.sum (fun a => x ⟨j, a⟩) := cooperative_game_direct_sum_calibration_sum_image j T x rw [hvS, hSx] at h_bound have h_scale : T.sum (fun a => x ⟨j, a⟩) = (s j / W j) * T.sum y_scaled := by dsimp [y_scaled] rw [← Finset.mul_sum] have h_cancel : (s j / W j) * (W j / s j) = 1 := by rw [div_mul_div_comm, mul_comm (s j), div_self (ne_of_gt (mul_pos (hW_pos j) hs_pos))] rw [← mul_assoc, h_cancel, one_mul] have h_step1 : T.sum (fun a => x ⟨j, a⟩) ≤ (s j / W j) * (r j * v j T) := by rw [h_scale] exact mul_le_mul_of_nonneg_left hT_le (div_nonneg (le_of_lt hs_pos) (le_of_lt (hW_pos j))) have h_chain : α_star * v j T ≤ (s j * r j / W j) * v j T := by have : (s j / W j) * (r j * v j T) = (s j * r j / W j) * v j T := by ring linarith have h_div : α_star ≤ s j * r j / W j := (mul_le_mul_iff_of_pos_right hT_pos).mp h_chain dsimp [t] have hrj := (hr_bounds j).1 have hWj := hW_pos j have : α_star * W j ≤ s j * r j := (le_div_iff₀ hWj).mp h_div exact (div_le_iff₀ hrj).mpr (by linarith) intro j exact cooperative_game_direct_sum_calibration_sum_eq_of_le_all s t h_le_each (hs_sum.trans ht_sum.symm) j
α* = 1 if and only if every component game has a nonempty core.
Because r_j ≤ 1, each term W_j / r_j - W_j is nonnegative. The equality α* = 1 means the denominator equals W_bar, so the sum of these nonnegative terms is zero, which holds if and only if each W_j / r_j = W_j, i.e., r_j = 1 for all j. By cooperative_game_core_nonempty_iff_optimal_guarantee_eq_one, r_j = 1 is equivalent to component j having a nonempty core. Combining the optimality of α*, uniqueness of component totals, α* ≤ 1, and this core equivalence completes the proof.
uses
cooperative_game_core_nonempty_iff_optimal_guarantee_eq_one,Finset.sum_eq_zero_iff_of_nonneg,forall_congr'have h_core_iff : ∀ j, (r j = 1 ↔ ∃ y : N j → ℝ, (∀ i, 0 ≤ y i) ∧ Finset.univ.sum y = v j Finset.univ ∧ ∀ T : Finset (N j), v j T ≤ T.sum y) := by intro j exact cooperative_game_core_nonempty_iff_optimal_guarantee_eq_one (v j) (r j) (h_nonneg j) (hW j) (hr_bounds j) (hr j) have h_α_iff : (α_star = 1 ↔ ∀ j, r j = 1) := by have h_diff_nonneg : ∀ j ∈ (Finset.univ : Finset M), 0 ≤ W j / r j - W j := fun j hj => sub_nonneg.mpr (h_le j hj) constructor · intro hα have h_eq : Finset.univ.sum (fun j => W j / r j) = W_bar := ((div_eq_one_iff_eq (ne_of_gt h_denom_pos)).mp hα).symm have h_sum_diff : Finset.univ.sum (fun j => W j / r j - W j) = 0 := by rw [Finset.sum_sub_distrib] change Finset.univ.sum (fun j => W j / r j) - W_bar = 0 rw [h_eq, sub_self] have h_each_zero := (Finset.sum_eq_zero_iff_of_nonneg h_diff_nonneg).mp h_sum_diff intro j have hj := h_each_zero j (Finset.mem_univ j) have : W j / r j = W j := sub_eq_zero.mp hj have hrj := (hr_bounds j).1 have h_mul : W j / r j * r j = W j * r j := by rw [this] rw [div_mul_cancel₀ (W j) (ne_of_gt hrj)] at h_mul nlinarith [hW_pos j] · intro hr_one have h_denom_eq : Finset.univ.sum (fun j => W j / r j) = W_bar := by dsimp [W_bar, W] congr 1; ext j rw [hr_one j, div_one] dsimp [α_star] rw [h_denom_eq] exact div_self (ne_of_gt hW_bar_pos) refine ⟨⟨hx_star, h_tight⟩, h_unique, hα_le_one, ?_⟩ rw [h_α_iff] exact forall_congr' h_core_iff
Finset.sum_ite_mem_eq- Summing an indicator function over all elements of a finite type equals the sum over the specified subset.
Fintype.sum_sigma- A sum over a dependent sum (disjoint union) Σ_j N_j equals the iterated sum ∑_j ∑_{i ∈ N_j}.
Finset.sum_filter- A sum restricted to a filtered subset {i ∈ s | p(i)} equals the sum over s with an indicator function that is zero when p(i) is false.
Finset.sum_sub_distrib- The sum of differences ∑ (f(x) - g(x)) equals the difference of the sums ∑ f(x) - ∑ g(x).
Finset.sum_eq_zero_iff_of_nonneg- A sum of nonnegative terms is zero if and only if every term in the sum is zero.
Finset.sum_lt_sum_of_nonempty- If f(i) < g(i) for all elements i of a nonempty finite set, then ∑ f(i) < ∑ g(i).
Finset.sum_eq_single_of_mem- If all terms in a finite sum except possibly one element a are zero, the sum equals the term at a.
Fintype.card_eq_one_iff- A finite type has cardinality 1 if and only if there exists an element equal to every element in the type.
Finset.sum_image- The sum of a function over the image of a set under an injective mapping equals the sum of the composite function over the original set.
Finset.sum_pos- A sum of strictly positive terms over a nonempty finite set is strictly positive.
Finset.sum_le_sum- If f(i) ≤ g(i) for all i in a finite set, then ∑ f(i) ≤ ∑ g(i).
div_le_one- For b > 0, the quotient a / b ≤ 1 if and only if a ≤ b.
Finset.sum_nonneg- A sum of nonnegative terms is nonnegative.
cooperative_game_direct_sum_calibration_sum_partition- A vector sum over a coalition S in a direct-sum game equals the sum over components j of the sums over the component projections S ∩ N_j.
Finset.mul_sum- Multiplication distributes over finite sums: a · ∑_i f(i) = ∑_i a · f(i).
div_mul_cancel₀- For any non-zero denominator b ≠ 0, (a / b) · b = a.
cooperative_game_direct_sum_calibration_exists_le_of_sum_le- If two vectors on a nonempty finite set satisfy ∑_j s_j ≤ ∑_j t_j, then s_j ≤ t_j for at least one index j.
cooperative_game_direct_sum_calibration_v_bar_image- The characteristic function v_bar of the direct sum evaluated on a single-component embedded coalition {j} × T equals v_j(T).
cooperative_game_direct_sum_calibration_image_ne_univ- When there are at least two components (m ≥ 2) with positive grand coalition values, any single-component embedded coalition {j} × T is a proper subset of the grand coalition.
cooperative_game_direct_sum_calibration_sum_image- The sum of a vector x over the embedded coalition {j} × T in the direct sum equals the sum of x(j, ·) over T ⊆ N_j.
cooperative_game_direct_sum_calibration_sum_eq_of_le_all- If t_j ≤ s_j for all j in a finite set and their totals match (∑ s_j = ∑ t_j), then s_j = t_j for all j.
cooperative_game_core_nonempty_iff_optimal_guarantee_eq_one- In a cooperative game with positive grand coalition value, the optimal multiplicative least-core guarantee r equals 1 if and only if the game has a nonempty core.
forall_congr'- If two predicates are equivalent pointwise (p(a) ↔ q(a) for all a), then (∀ a, p(a)) is equivalent to (∀ a, q(a)).
- The proof is structured around six preliminary lemmas (lines 1–63) establishing partition identities, sum bounds, and coalition embeddings for the direct-sum game before proving the main calibration theorem (lines 65–320).
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.
lemma cooperative_game_direct_sum_calibration_sum_partition {M : Type*} [DecidableEq M] [Fintype M] {N : M → Type*} [∀ j, DecidableEq (N j)] [∀ j, Fintype (N j)] (S : Finset (Σ j, N j)) (x : (Σ j, N j) → ℝ) : S.sum x = Finset.univ.sum (fun j => (Finset.univ.filter (fun (i : N j) => (⟨j, i⟩ : Σ j, N j) ∈ S)).sum (fun i => x ⟨j, i⟩)) := by rw [← Finset.sum_ite_mem_eq S x, Fintype.sum_sigma] congr 1; ext j exact (Finset.sum_filter (fun (i : N j) => (⟨j, i⟩ : Σ j, N j) ∈ S) (fun i => x ⟨j, i⟩)).symmlemma cooperative_game_direct_sum_calibration_sum_eq_of_le_all {M : Type*} [Fintype M] (s t : M → ℝ) (hle : ∀ j, t j ≤ s j) (hsum : Finset.univ.sum s = Finset.univ.sum t) (j : M) : s j = t j := by have hdiff : Finset.univ.sum (fun k => s k - t k) = 0 := by rw [Finset.sum_sub_distrib, hsum, sub_self] have hdiff_nonneg : ∀ k ∈ Finset.univ, 0 ≤ s k - t k := fun k _ => sub_nonneg.mpr (hle k) have hzero := (Finset.sum_eq_zero_iff_of_nonneg hdiff_nonneg).mp hdiff j (Finset.mem_univ j) exact sub_eq_zero.mp hzerolemma cooperative_game_direct_sum_calibration_exists_le_of_sum_le {M : Type*} [Fintype M] (hne : Nonempty M) (s t : M → ℝ) (hsum : Finset.univ.sum s ≤ Finset.univ.sum t) : ∃ j, s j ≤ t j := by by_contra! h have : Finset.univ.sum t < Finset.univ.sum s := Finset.sum_lt_sum_of_nonempty Finset.univ_nonempty (fun j _ => h j) linarithlemma cooperative_game_direct_sum_calibration_v_bar_image {M : Type*} [DecidableEq M] [Fintype M] {N : M → Type*} [∀ j, DecidableEq (N j)] [∀ j, Fintype (N j)] (v : ∀ j, Finset (N j) → ℝ) (hv_empty : ∀ j, v j ∅ = 0) (j : M) (T : Finset (N j)) : (Finset.univ.sum (fun k => v k (Finset.univ.filter (fun (i : N k) => (⟨k, i⟩ : Σ j, N j) ∈ T.image (fun i => ⟨j, i⟩))))) = v j T := by have h_filter : ∀ k, (Finset.univ.filter (fun (i : N k) => (⟨k, i⟩ : Σ j, N j) ∈ T.image (fun i => ⟨j, i⟩))) = if h : k = j then h ▸ T else ∅ := by intro k; ext i; simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image] split_ifs with h · subst h; simp · simp only [Sigma.mk.inj_iff, Finset.notMem_empty, iff_false] rintro ⟨a, -, rfl, -⟩; exact h rfl simp_rw [h_filter] rw [Finset.sum_eq_single_of_mem j (Finset.mem_univ j)] · simp · intro k _ hk; simp [hk, hv_empty k]lemma cooperative_game_direct_sum_calibration_image_ne_univ {M : Type*} [DecidableEq M] [Fintype M] {N : M → Type*} [∀ j, DecidableEq (N j)] [∀ j, Fintype (N j)] (v : ∀ j, Finset (N j) → ℝ) (hm : 2 ≤ Fintype.card M) (hv_empty : ∀ j, v j ∅ = 0) (hW : ∀ j, 0 < v j Finset.univ) (j : M) (T : Finset (N j)) : (T.image (fun i => (⟨j, i⟩ : Σ j, N j))) ≠ Finset.univ := by have : ∃ k : M, k ≠ j := by by_contra! h; have : Fintype.card M = 1 := Fintype.card_eq_one_iff.mpr ⟨j, h⟩; omega obtain ⟨k, hkj⟩ := this have h_ne : Nonempty (N k) := by by_contra h_empty; have h_univ : (Finset.univ : Finset (N k)) = ∅ := by ext x; exact (h_empty ⟨x⟩).elim have := hW k; rw [h_univ, hv_empty] at this; linarith obtain ⟨b⟩ := h_ne; intro h_eq have : (⟨k, b⟩ : Σ j, N j) ∈ Finset.univ := Finset.mem_univ _ rw [← h_eq, Finset.mem_image] at this; obtain ⟨a, -, ha⟩ := this have : k = j := (Sigma.mk.inj_iff.mp ha.symm).1; exact hkj thislemma cooperative_game_direct_sum_calibration_sum_image {M : Type*} [DecidableEq M] {N : M → Type*} [∀ j, DecidableEq (N j)] (j : M) (T : Finset (N j)) (x : (Σ j, N j) → ℝ) : (T.image (fun i => (⟨j, i⟩ : Σ j, N j))).sum x = T.sum (fun i => x ⟨j, i⟩) := by apply Finset.sum_image; intro a _ b _ hab; exact (Sigma.mk.inj_iff.mp hab).2.eq/-- Direct-sum calibration for cooperative games: first-stage optimum and component budgets (arXiv:2610.29731 Lemma 4). -/theorem cooperative_game_direct_sum_calibration {M : Type*} [DecidableEq M] [Fintype M] {N : M → Type*} [∀ j, DecidableEq (N j)] [∀ j, Fintype (N j)] (v : ∀ j, Finset (N j) → ℝ) (r : M → ℝ) (hm : 2 ≤ Fintype.card M) (hv_empty : ∀ j, v j ∅ = 0) (h_nonneg : ∀ j S, 0 ≤ v j S) (hW : ∀ j, 0 < v j Finset.univ) (hr_bounds : ∀ j, 0 < r j ∧ r j ≤ 1) (hr : ∀ j, (∃ y : N j → ℝ, (∀ i, 0 ≤ y i) ∧ Finset.univ.sum y = v j Finset.univ ∧ ∀ T : Finset (N j), 0 < v j T → r j * v j T ≤ T.sum y) ∧ (∀ y : N j → ℝ, (∀ i, 0 ≤ y i) → Finset.univ.sum y = v j Finset.univ → ∃ T : Finset (N j), 0 < v j T ∧ T.sum y ≤ r j * v j T)) : let W := fun j => v j Finset.univ let W_bar := Finset.univ.sum W let α_star := W_bar / Finset.univ.sum (fun j => W j / r j) let v_bar : Finset (Σ j, N j) → ℝ := fun S => Finset.univ.sum (fun j => v j (Finset.univ.filter (fun (i : N j) => (⟨j, i⟩ : Σ j, N j) ∈ S))) ((∃ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) ∧ Finset.univ.sum x = v_bar Finset.univ ∧ ∀ S : Finset (Σ j, N j), S ≠ Finset.univ → 0 < v_bar S → α_star * v_bar S ≤ S.sum x) ∧ (∀ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) → Finset.univ.sum x = v_bar Finset.univ → ∃ S : Finset (Σ j, N j), S ≠ Finset.univ ∧ 0 < v_bar S ∧ S.sum x ≤ α_star * v_bar S)) ∧ (∀ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) → Finset.univ.sum x = v_bar Finset.univ → (∀ S : Finset (Σ j, N j), S ≠ Finset.univ → 0 < v_bar S → α_star * v_bar S ≤ S.sum x) → ∀ j : M, Finset.univ.sum (fun a => x ⟨j, a⟩) = α_star * W j / r j) ∧ α_star ≤ 1 ∧ (α_star = 1 ↔ ∀ j : M, ∃ y : N j → ℝ, (∀ i, 0 ≤ y i) ∧ Finset.univ.sum y = v j Finset.univ ∧ ∀ T : Finset (N j), v j T ≤ T.sum y) := by intro W W_bar α_star v_bar have hM_ne : (Finset.univ : Finset M).Nonempty := by rw [Finset.univ_nonempty_iff]; exact Fintype.card_pos_iff.mp (by omega) have h_ne : Nonempty M := Fintype.card_pos_iff.mp (by omega) have hW_pos : ∀ j, 0 < W j := hW have hW_bar_pos : 0 < W_bar := Finset.sum_pos (fun j _ => hW_pos j) hM_ne have h_le : ∀ j ∈ (Finset.univ : Finset M), W j ≤ W j / r j := fun j _ => by have hrj := hr_bounds j have : W j * r j ≤ W j := by nlinarith [hW j] exact (le_div_iff₀ hrj.1).mpr this have h_sum_le : W_bar ≤ Finset.univ.sum (fun j => W j / r j) := Finset.sum_le_sum h_le have h_denom_pos : 0 < Finset.univ.sum (fun j => W j / r j) := by linarith have hα_pos : 0 < α_star := div_pos hW_bar_pos h_denom_pos have hα_le_one : α_star ≤ 1 := (div_le_one h_denom_pos).mpr h_sum_le have hv_univ : v_bar Finset.univ = W_bar := by dsimp [v_bar, W_bar, W] congr 1; ext j; congr 1; ext i simp only [Finset.mem_filter, Finset.mem_univ, true_and] choose y hy_nonneg hy_sum hy_core using (fun j => (hr j).1) have hy_core_all : ∀ j T, r j * v j T ≤ T.sum (y j) := by intro j T by_cases hT : 0 < v j T · exact hy_core j T hT · have h0 : v j T = 0 := le_antisymm (not_lt.mp hT) (h_nonneg j T) rw [h0, mul_zero] exact Finset.sum_nonneg (fun i _ => hy_nonneg j i) have hx_star : (∃ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) ∧ Finset.univ.sum x = v_bar Finset.univ ∧ ∀ S : Finset (Σ j, N j), S ≠ Finset.univ → 0 < v_bar S → α_star * v_bar S ≤ S.sum x) := by let x : (Σ j, N j) → ℝ := fun ⟨j, i⟩ => (α_star / r j) * y j i refine ⟨x, ?_, ?_, ?_⟩ · rintro ⟨j, i⟩ exact mul_nonneg (le_of_lt (div_pos hα_pos (hr_bounds j).1)) (hy_nonneg j i) · rw [hv_univ, Fintype.sum_sigma] have h1 : ∀ j, Finset.univ.sum (fun i => x ⟨j, i⟩) = (α_star / r j) * W j := by intro j dsimp [x] rw [← Finset.mul_sum, hy_sum] have h2 : (fun j => Finset.univ.sum (fun i => x ⟨j, i⟩)) = (fun j => α_star * (W j / r j)) := by ext j rw [h1] ring rw [h2, ← Finset.mul_sum] exact div_mul_cancel₀ W_bar (ne_of_gt h_denom_pos) · intro S _ _ dsimp [v_bar] rw [cooperative_game_direct_sum_calibration_sum_partition S x, Finset.mul_sum] apply Finset.sum_le_sum intro j _ let Tj := Finset.univ.filter (fun (i : N j) => (⟨j, i⟩ : Σ j, N j) ∈ S) have h_scale : Tj.sum (fun i => x ⟨j, i⟩) = (α_star / r j) * Tj.sum (y j) := by dsimp [x] rw [← Finset.mul_sum] rw [h_scale] have h_c := hy_core_all j Tj have h_pos : 0 ≤ α_star / r j := le_of_lt (div_pos hα_pos (hr_bounds j).1) have h_le := mul_le_mul_of_nonneg_left h_c h_pos have h_id : (α_star / r j) * (r j * v j Tj) = α_star * v j Tj := by rw [← mul_assoc, div_mul_cancel₀ α_star (ne_of_gt (hr_bounds j).1)] rwa [h_id] at h_le have h_tight : (∀ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) → Finset.univ.sum x = v_bar Finset.univ → ∃ S : Finset (Σ j, N j), S ≠ Finset.univ ∧ 0 < v_bar S ∧ S.sum x ≤ α_star * v_bar S) := by intro x hx_nonneg hx_sum let s : M → ℝ := fun j => Finset.univ.sum (fun a => x ⟨j, a⟩) let t : M → ℝ := fun j => α_star * W j / r j have hs_sum : Finset.univ.sum s = W_bar := by rw [← Fintype.sum_sigma] exact hx_sum.trans hv_univ have ht_sum : Finset.univ.sum t = W_bar := by have h1 : (fun j => α_star * W j / r j) = (fun j => α_star * (W j / r j)) := by ext j; ring dsimp [t] rw [h1, ← Finset.mul_sum] exact div_mul_cancel₀ W_bar (ne_of_gt h_denom_pos) have h_exist : ∃ j, s j ≤ t j := by apply cooperative_game_direct_sum_calibration_exists_le_of_sum_le h_ne rw [hs_sum, ht_sum] obtain ⟨j, hj_le⟩ := h_exist have hs_nonneg : 0 ≤ s j := Finset.sum_nonneg (fun i _ => hx_nonneg ⟨j, i⟩) by_cases hs_zero : s j = 0 · let S : Finset (Σ j, N j) := Finset.univ.image (fun i => ⟨j, i⟩) have hvS : v_bar S = W j := cooperative_game_direct_sum_calibration_v_bar_image v hv_empty j Finset.univ have hSx : S.sum x = s j := cooperative_game_direct_sum_calibration_sum_image j Finset.univ x refine ⟨S, ?_, ?_, ?_⟩ · exact cooperative_game_direct_sum_calibration_image_ne_univ v hm hv_empty hW j Finset.univ · rw [hvS]; exact hW_pos j · rw [hvS, hSx, hs_zero] exact mul_nonneg (le_of_lt hα_pos) (le_of_lt (hW_pos j)) · have hs_pos : 0 < s j := lt_of_le_of_ne hs_nonneg (Ne.symm hs_zero) let y_scaled : N j → ℝ := fun a => (W j / s j) * x ⟨j, a⟩ have hy_scaled_nonneg : ∀ i, 0 ≤ y_scaled i := fun i => mul_nonneg (div_nonneg (le_of_lt (hW_pos j)) (le_of_lt hs_pos)) (hx_nonneg ⟨j, i⟩) have hy_scaled_sum : Finset.univ.sum y_scaled = v j Finset.univ := by dsimp [y_scaled] rw [← Finset.mul_sum] have : Finset.univ.sum (fun a => x ⟨j, a⟩) = s j := rfl rw [this, div_mul_cancel₀ (W j) (ne_of_gt hs_pos)] obtain ⟨T, hT_pos, hT_le⟩ := (hr j).2 y_scaled hy_scaled_nonneg hy_scaled_sum let S : Finset (Σ j, N j) := T.image (fun i => ⟨j, i⟩) have hvS : v_bar S = v j T := cooperative_game_direct_sum_calibration_v_bar_image v hv_empty j T have hSx : S.sum x = T.sum (fun a => x ⟨j, a⟩) := cooperative_game_direct_sum_calibration_sum_image j T x refine ⟨S, ?_, ?_, ?_⟩ · exact cooperative_game_direct_sum_calibration_image_ne_univ v hm hv_empty hW j T · rw [hvS]; exact hT_pos · rw [hvS, hSx] have h_scale : T.sum (fun a => x ⟨j, a⟩) = (s j / W j) * T.sum y_scaled := by dsimp [y_scaled] rw [← Finset.mul_sum] have h_cancel : (s j / W j) * (W j / s j) = 1 := by rw [div_mul_div_comm, mul_comm (s j), div_self (ne_of_gt (mul_pos (hW_pos j) hs_pos))] rw [← mul_assoc, h_cancel, one_mul] rw [h_scale] have h_step1 : (s j / W j) * T.sum y_scaled ≤ (s j / W j) * (r j * v j T) := mul_le_mul_of_nonneg_left hT_le (div_nonneg (le_of_lt hs_pos) (le_of_lt (hW_pos j))) have h_step2 : (s j / W j) * (r j * v j T) ≤ α_star * v j T := by have hrj := (hr_bounds j).1 have hWj := hW_pos j have : (s j / W j) * (r j * v j T) = (s j * r j / W j) * v j T := by ring rw [this] apply mul_le_mul_of_nonneg_right _ (le_of_lt hT_pos) have hj_le' : s j ≤ α_star * W j / r j := hj_le rw [div_le_iff₀ hWj] have : s j * r j ≤ α_star * W j := by have : s j * r j ≤ (α_star * W j / r j) * r j := mul_le_mul_of_nonneg_right hj_le' (le_of_lt hrj) rwa [div_mul_cancel₀ (α_star * W j) (ne_of_gt hrj)] at this exact this exact le_trans h_step1 h_step2 have h_unique : (∀ x : (Σ j, N j) → ℝ, (∀ i, 0 ≤ x i) → Finset.univ.sum x = v_bar Finset.univ → (∀ S : Finset (Σ j, N j), S ≠ Finset.univ → 0 < v_bar S → α_star * v_bar S ≤ S.sum x) → ∀ j : M, Finset.univ.sum (fun a => x ⟨j, a⟩) = α_star * W j / r j) := by intro x hx_nonneg hx_sum h_core let s : M → ℝ := fun j => Finset.univ.sum (fun a => x ⟨j, a⟩) let t : M → ℝ := fun j => α_star * W j / r j have hs_sum : Finset.univ.sum s = W_bar := by rw [← Fintype.sum_sigma] exact hx_sum.trans hv_univ have ht_sum : Finset.univ.sum t = W_bar := by have h1 : (fun j => α_star * W j / r j) = (fun j => α_star * (W j / r j)) := by ext j; ring dsimp [t] rw [h1, ← Finset.mul_sum] exact div_mul_cancel₀ W_bar (ne_of_gt h_denom_pos) have h_le_each : ∀ j, t j ≤ s j := by intro j have hs_nonneg : 0 ≤ s j := Finset.sum_nonneg (fun i _ => hx_nonneg ⟨j, i⟩) by_cases hs_zero : s j = 0 · exfalso let Suniv : Finset (Σ j, N j) := Finset.univ.image (fun i => ⟨j, i⟩) have hS_ne : Suniv ≠ Finset.univ := cooperative_game_direct_sum_calibration_image_ne_univ v hm hv_empty hW j Finset.univ have hvS : v_bar Suniv = W j := cooperative_game_direct_sum_calibration_v_bar_image v hv_empty j Finset.univ have hS_pos : 0 < v_bar Suniv := by rw [hvS]; exact hW_pos j have h_bound := h_core Suniv hS_ne hS_pos have hSx : Suniv.sum x = s j := cooperative_game_direct_sum_calibration_sum_image j Finset.univ x rw [hvS, hSx, hs_zero] at h_bound have : 0 < α_star * W j := mul_pos hα_pos (hW_pos j) linarith · have hs_pos : 0 < s j := lt_of_le_of_ne hs_nonneg (Ne.symm hs_zero) let y_scaled : N j → ℝ := fun a => (W j / s j) * x ⟨j, a⟩ have hy_scaled_nonneg : ∀ i, 0 ≤ y_scaled i := fun i => mul_nonneg (div_nonneg (le_of_lt (hW_pos j)) (le_of_lt hs_pos)) (hx_nonneg ⟨j, i⟩) have hy_scaled_sum : Finset.univ.sum y_scaled = v j Finset.univ := by dsimp [y_scaled] rw [← Finset.mul_sum] have : Finset.univ.sum (fun a => x ⟨j, a⟩) = s j := rfl rw [this, div_mul_cancel₀ (W j) (ne_of_gt hs_pos)] obtain ⟨T, hT_pos, hT_le⟩ := (hr j).2 y_scaled hy_scaled_nonneg hy_scaled_sum let S : Finset (Σ j, N j) := T.image (fun i => ⟨j, i⟩) have hS_ne : S ≠ Finset.univ := cooperative_game_direct_sum_calibration_image_ne_univ v hm hv_empty hW j T have hvS : v_bar S = v j T := cooperative_game_direct_sum_calibration_v_bar_image v hv_empty j T have hS_pos : 0 < v_bar S := by rw [hvS]; exact hT_pos have h_bound := h_core S hS_ne hS_pos have hSx : S.sum x = T.sum (fun a => x ⟨j, a⟩) := cooperative_game_direct_sum_calibration_sum_image j T x rw [hvS, hSx] at h_bound have h_scale : T.sum (fun a => x ⟨j, a⟩) = (s j / W j) * T.sum y_scaled := by dsimp [y_scaled] rw [← Finset.mul_sum] have h_cancel : (s j / W j) * (W j / s j) = 1 := by rw [div_mul_div_comm, mul_comm (s j), div_self (ne_of_gt (mul_pos (hW_pos j) hs_pos))] rw [← mul_assoc, h_cancel, one_mul] have h_step1 : T.sum (fun a => x ⟨j, a⟩) ≤ (s j / W j) * (r j * v j T) := by rw [h_scale] exact mul_le_mul_of_nonneg_left hT_le (div_nonneg (le_of_lt hs_pos) (le_of_lt (hW_pos j))) have h_chain : α_star * v j T ≤ (s j * r j / W j) * v j T := by have : (s j / W j) * (r j * v j T) = (s j * r j / W j) * v j T := by ring linarith have h_div : α_star ≤ s j * r j / W j := (mul_le_mul_iff_of_pos_right hT_pos).mp h_chain dsimp [t] have hrj := (hr_bounds j).1 have hWj := hW_pos j have : α_star * W j ≤ s j * r j := (le_div_iff₀ hWj).mp h_div exact (div_le_iff₀ hrj).mpr (by linarith) intro j exact cooperative_game_direct_sum_calibration_sum_eq_of_le_all s t h_le_each (hs_sum.trans ht_sum.symm) j have h_core_iff : ∀ j, (r j = 1 ↔ ∃ y : N j → ℝ, (∀ i, 0 ≤ y i) ∧ Finset.univ.sum y = v j Finset.univ ∧ ∀ T : Finset (N j), v j T ≤ T.sum y) := by intro j exact cooperative_game_core_nonempty_iff_optimal_guarantee_eq_one (v j) (r j) (h_nonneg j) (hW j) (hr_bounds j) (hr j) have h_α_iff : (α_star = 1 ↔ ∀ j, r j = 1) := by have h_diff_nonneg : ∀ j ∈ (Finset.univ : Finset M), 0 ≤ W j / r j - W j := fun j hj => sub_nonneg.mpr (h_le j hj) constructor · intro hα have h_eq : Finset.univ.sum (fun j => W j / r j) = W_bar := ((div_eq_one_iff_eq (ne_of_gt h_denom_pos)).mp hα).symm have h_sum_diff : Finset.univ.sum (fun j => W j / r j - W j) = 0 := by rw [Finset.sum_sub_distrib] change Finset.univ.sum (fun j => W j / r j) - W_bar = 0 rw [h_eq, sub_self] have h_each_zero := (Finset.sum_eq_zero_iff_of_nonneg h_diff_nonneg).mp h_sum_diff intro j have hj := h_each_zero j (Finset.mem_univ j) have : W j / r j = W j := sub_eq_zero.mp hj have hrj := (hr_bounds j).1 have h_mul : W j / r j * r j = W j * r j := by rw [this] rw [div_mul_cancel₀ (W j) (ne_of_gt hrj)] at h_mul nlinarith [hW_pos j] · intro hr_one have h_denom_eq : Finset.univ.sum (fun j => W j / r j) = W_bar := by dsimp [W_bar, W] congr 1; ext j rw [hr_one j, div_one] dsimp [α_star] rw [h_denom_eq] exact div_self (ne_of_gt hW_bar_pos) refine ⟨⟨hx_star, h_tight⟩, h_unique, hα_le_one, ?_⟩ rw [h_α_iff] exact forall_congr' h_core_iff