persuasion_slice_sender_le
lemmaverified
Sender value of the slice prior. No obedient scheme gives the sender more than C(2m+1,m) - C(2m-1,m).
Statement
open Finset in lemma persuasion_slice_sender_le (m : ℕ) (hm : 1 ≤ m) (q : (persuasion_slice_coord m → Bool) → (persuasion_slice_coord m → Bool) → ℝ) (hq : is_obedient_direct_scheme (persuasion_slice_prior m) q) : persuasion_sender_utility q ≤ ((2 * m + 1).choose m : ℝ) - (2 * m - 1).choose m
- Source
- step towards persuasion_receiver_ratio_optimal_constant (optimal receiver-utility constant 3/2, open in arXiv:2606.22226 v1, Sec. 5)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- persuasion_slice_stateState number s of the slice prior: coordinate i is 1 iff s ∈ i.
- persuasion_slice_coordCoordinates of the slice prior: the m-subsets of Fin (2m+1).
- is_obedient_direct_schemeAn obedient direct scheme for the prior μ on {0,1}^ι.
- persuasion_slice_priorThe slice prior: uniform over the 2m+1 states persuasion_slice_state m s.
- persuasion_sender_utilitySender utility S(q): expected number of coordinates recommended as 1.
- persuasion_obedience_costObedience cost C_i(x, a): 1/2 - x_i if a_i = 1, x_i - 1/2 if a_i = 0.
- persuasion_slice_card_filterCounting coordinates of the slice prior with a property of the underlying m-subset is counting m-subsets of Fin (2m+1) with that property.
- persuasion_heavy_sets_card_leMain counting lemma. For nonnegative weights w on Fin (2m+1) with positive total W, at most C(2m+1, m) - C(2m-1, m) of the m-subsets have…
- persuasion_slice_prior_is_bit_priorThe slice prior is a probability distribution on {0,1}^ι.
- Used by 1
- persuasion_slice_valuesR_max and R_0 for the slice prior.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finset in/-- For `m ≥ 1` the `2m+1` states of the slice prior are distinct. -/lemma persuasion_slice_state_injective (m : ℕ) (hm : 1 ≤ m) : Function.Injective (persuasion_slice_state m) := by intro s t h by_contra hst obtain ⟨i, hsi, hit, hic⟩ := exists_subsuperset_card_eq (show ({s} : Finset (Fin (2 * m + 1))) ⊆ Finset.univ.erase t by intro x hx; rw [Finset.mem_singleton] at hx; subst hx; exact mem_erase.mpr ⟨hst, Finset.mem_univ _⟩) (show ({s} : Finset (Fin (2 * m + 1))).card ≤ m by simpa using hm) (show m ≤ (Finset.univ.erase t).card by rw [card_erase_of_mem (Finset.mem_univ t), card_univ, Fintype.card_fin]; omega) have := congrFun h ⟨i, hic⟩ simp only [persuasion_slice_state] at this have h1 : s ∈ i := hsi (Finset.mem_singleton_self s) have h2 : t ∉ i := fun ht => by simpa using hit ht simp [h1, h2] at thisopen Finset in/-- **Sender value of the slice prior.** No obedient scheme gives the sender more than`C(2m+1,m) - C(2m-1,m)`. -/lemma persuasion_slice_sender_le (m : ℕ) (hm : 1 ≤ m) (q : (persuasion_slice_coord m → Bool) → (persuasion_slice_coord m → Bool) → ℝ) (hq : is_obedient_direct_scheme (persuasion_slice_prior m) q) : persuasion_sender_utility q ≤ ((2 * m + 1).choose m : ℝ) - (2 * m - 1).choose m := by classical set B : ℝ := ((2 * m + 1).choose m : ℝ) - (2 * m - 1).choose m set v := persuasion_slice_state m have hinj := persuasion_slice_state_injective m hm obtain ⟨hq0, hqμ, hqob⟩ := hq -- `q` vanishes off the support have hsupp : ∀ x a, (∀ s, v s ≠ x) → q x a = 0 := by intro x a hx have hμ0 : persuasion_slice_prior m x = 0 := by unfold persuasion_slice_prior apply sum_eq_zero; intro s _; rw [if_neg (hx s)] apply le_antisymm _ (hq0 x a) rw [← hμ0, ← hqμ x] exact single_le_sum (fun a' _ => hq0 x a') (Finset.mem_univ a) have hsum : ∀ a (g : (persuasion_slice_coord m → Bool) → ℝ), ∑ x, q x a * g x = ∑ s, q (v s) a * g (v s) := by intro a g rw [← sum_image (s := (Finset.univ : Finset (Fin (2 * m + 1)))) (g := v) (f := fun x => q x a * g x) (fun s _ t _ h => hinj h)] symm apply sum_subset (Finset.subset_univ _) intro x _ hx rw [hsupp x a (fun s hs => hx (Finset.mem_image.mpr ⟨s, Finset.mem_univ s, hs⟩)), zero_mul] -- per action have hact : ∀ a, ∑ x, q x a * ((Finset.univ.filter (fun i => a i = true)).card : ℝ) ≤ ∑ x, q x a * B := by intro a rw [← sum_mul, ← sum_mul] have hQ : 0 ≤ ∑ x, q x a := sum_nonneg fun x _ => hq0 x a rcases hQ.lt_or_eq with hQ | hQ swap · rw [← hQ, zero_mul, zero_mul] apply mul_le_mul_of_nonneg_left _ hQ.le set w : Fin (2 * m + 1) → ℝ := fun s => q (v s) a have hw0 : ∀ s, 0 ≤ w s := fun s => hq0 _ a have hW : ∑ s, w s = ∑ x, q x a := by have := hsum a (fun _ => 1); simp only [mul_one] at this; rw [this] have hWpos : 0 < ∑ s, w s := hW ▸ hQ -- every recommended coordinate is heavy have hheavy : ∀ i : persuasion_slice_coord m, a i = true → ∑ s, w s ≤ 2 * ∑ s ∈ i.1, w s := by intro i hai have h := hqob a i rw [hsum a (fun x => persuasion_obedience_cost i x a)] at h unfold persuasion_obedience_cost at h simp only [hai, if_true] at h have e : ∀ s, q (v s) a * (1 / 2 - if v s i = true then 1 else 0) = w s / 2 - if s ∈ i.1 then w s else 0 := by intro s simp only [w, v, persuasion_slice_state, decide_eq_true_eq] split_ifs <;> ring rw [sum_congr rfl (fun s _ => e s), sum_sub_distrib, sum_ite_mem, Finset.univ_inter, ← sum_div] at h linarith have hcard : (Finset.univ.filter (fun i : persuasion_slice_coord m => a i = true)).card ≤ ((powersetCard m (Finset.univ : Finset (Fin (2 * m + 1)))).filter (fun j => ∑ s, w s ≤ 2 * ∑ s ∈ j, w s)).card := by rw [← persuasion_slice_card_filter m (fun j => ∑ s, w s ≤ 2 * ∑ s ∈ j, w s)] exact Finset.card_le_card (fun i hi => by rw [Finset.mem_filter] at hi ⊢; exact ⟨hi.1, hheavy i hi.2⟩) have hmain := persuasion_heavy_sets_card_le m hm w hw0 hWpos have : (Finset.univ.filter (fun i : persuasion_slice_coord m => a i = true)).card + (2 * m - 1).choose m ≤ (2 * m + 1).choose m := by omega simp only [B] have : ((Finset.univ.filter (fun i : persuasion_slice_coord m => a i = true)).card : ℝ) + (2 * m - 1).choose m ≤ (2 * m + 1).choose m := by exact_mod_cast this linarith unfold persuasion_sender_utility rw [sum_comm] calc ∑ a, ∑ x, q x a * ((Finset.univ.filter (fun i => a i = true)).card : ℝ) ≤ ∑ a, ∑ x, q x a * B := sum_le_sum fun a _ => hact a _ = ∑ x, persuasion_slice_prior m x * B := by rw [sum_comm]; apply sum_congr rfl; intro x _; rw [← sum_mul, hqμ x] _ = B := by rw [← sum_mul, (persuasion_slice_prior_is_bit_prior m).2, one_mul]