persuasion_slice_values
theoremverified
R_max and R_0 for the slice prior.
Statement
open Finset in theorem persuasion_slice_values (m : ℕ) (hm : 1 ≤ m) : persuasion_max_receiver_utility (persuasion_slice_prior m) = (2 * m - 1).choose m + (2 * m + 1).choose m * (m / (2 * m + 1 : ℝ)) ∧ persuasion_prior_utility (persuasion_slice_prior m) = (2 * m + 1).choose m * ((m + 1) / (2 * m + 1 : ℝ))
- 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 18
- persuasion_slice_coordCoordinates of the slice prior: the m-subsets of Fin (2m+1).
- persuasion_marginalThe marginal p_i(μ) = Pr_μ[X_i = 1].
- persuasion_slice_priorThe slice prior: uniform over the 2m+1 states persuasion_slice_state m s.
- persuasion_slice_stateState number s of the slice prior: coordinate i is 1 iff s ∈ i.
- persuasion_max_receiver_utilityR_max(μ): the largest receiver utility among sender-optimal obedient schemes.
- persuasion_prior_utilityThe receiver's prior-only utility R_0(μ) = ∑_i max(p_i, 1 - p_i).
- persuasion_slice_card_coordThe slice prior has C(2m+1, m) coordinates.
- persuasion_slice_prior_is_bit_priorThe slice prior is a probability distribution on {0,1}^ι.
- persuasion_slice_scheme_obedientThe slice scheme (pair the realised state with a uniformly random other state and recommend the coordinatewise OR) is an obedient direct…
- persuasion_slice_scheme_sender_utilityThe slice scheme gives the sender C(2m+1,m) - C(2m-1,m): a coordinate is recommended 1 iff its m-subset meets the two paired states.
- persuasion_pair_or_receiver_add_senderA pair-OR scheme never recommends 0 on a coordinate equal to 1, so the trade-off of Lemma 4.2 is an equality for it.
- persuasion_slice_couplingThe coupling that pairs the realised state with a uniformly random different state.
- persuasion_slice_coupling_marginalThe first marginal of the slice coupling is the slice prior.
- persuasion_receiver_utilityReceiver utility R(q): expected number of correctly guessed coordinates.
- persuasion_slice_schemeThe optimal scheme for the slice prior.
- is_sender_optimal_schemeq is obedient and maximises the sender's utility among obedient schemes.
- persuasion_slice_sender_leSender value of the slice prior. No obedient scheme gives the sender more than C(2m+1,m) - C(2m-1,m).
- persuasion_receiver_add_sender_leSender–receiver trade-off (Lemma 4.2). R(q) + S(q) ≤ n + ∑_i p_i(μ).
- Used by 1
- persuasion_slice_ratioThe slice prior attains ratio (3m+1)/(2m+2). For the prior uniform over the 2m+1 states of persuasion_slice_prior m (coordinates =…
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/-- Every coordinate of the slice prior has marginal `m/(2m+1)`. -/lemma persuasion_slice_marginal (m : ℕ) (i : persuasion_slice_coord m) : persuasion_marginal (persuasion_slice_prior m) i = m / (2 * m + 1 : ℝ) := by classical unfold persuasion_marginal persuasion_slice_prior have e : ∀ x : persuasion_slice_coord m → Bool, (if x i = true then ∑ s, (if persuasion_slice_state m s = x then 1 / (2 * m + 1 : ℝ) else 0) else 0) = ∑ s, if persuasion_slice_state m s = x then (if persuasion_slice_state m s i = true then 1 / (2 * m + 1 : ℝ) else 0) else 0 := by intro x by_cases hx : x i = true · rw [if_pos hx] apply sum_congr rfl; intro s _ by_cases h : persuasion_slice_state m s = x · rw [if_pos h, if_pos h, h, if_pos hx] · rw [if_neg h, if_neg h] · rw [if_neg hx] symm apply sum_eq_zero; intro s _ by_cases h : persuasion_slice_state m s = x · rw [if_pos h, h, if_neg hx] · rw [if_neg h] rw [sum_congr rfl (fun x _ => e x), sum_comm] simp only [sum_ite_eq, Finset.mem_univ, if_true] rw [← sum_filter, Finset.sum_const, nsmul_eq_mul] have : (Finset.univ.filter (fun s => persuasion_slice_state m s i = true)) = i.1 := by ext s; simp [persuasion_slice_state] rw [this, i.2] ringopen Finset in/-- `R_max` and `R_0` for the slice prior. -/theorem persuasion_slice_values (m : ℕ) (hm : 1 ≤ m) : persuasion_max_receiver_utility (persuasion_slice_prior m) = (2 * m - 1).choose m + (2 * m + 1).choose m * (m / (2 * m + 1 : ℝ)) ∧ persuasion_prior_utility (persuasion_slice_prior m) = (2 * m + 1).choose m * ((m + 1) / (2 * m + 1 : ℝ)) := by classical have hK : (0 : ℝ) < 2 * m + 1 := by positivity have hP : ∑ i, persuasion_marginal (persuasion_slice_prior m) i = (2 * m + 1).choose m * (m / (2 * m + 1 : ℝ)) := by simp only [persuasion_slice_marginal, Finset.sum_const, card_univ, persuasion_slice_card_coord, nsmul_eq_mul] have hμ := (persuasion_slice_prior_is_bit_prior m).2 have hobs := persuasion_slice_scheme_obedient m hm have hS := persuasion_slice_scheme_sender_utility m hm have hRS := persuasion_pair_or_receiver_add_sender (persuasion_slice_prior m) hμ (persuasion_slice_coupling m) (persuasion_slice_coupling_marginal m hm) rw [persuasion_slice_card_coord, hP] at hRS have hR : persuasion_receiver_utility (persuasion_slice_scheme m) = (2 * m - 1).choose m + (2 * m + 1).choose m * (m / (2 * m + 1 : ℝ)) := by unfold persuasion_slice_scheme at hS ⊢ linarith have hopt : is_sender_optimal_scheme (persuasion_slice_prior m) (persuasion_slice_scheme m) := ⟨hobs, fun q' hq' => hS ▸ persuasion_slice_sender_le m hm q' hq'⟩ refine ⟨?_, ?_⟩ · apply IsGreatest.csSup_eq refine ⟨⟨persuasion_slice_scheme m, hopt, hR.symm⟩, ?_⟩ rintro r ⟨q, ⟨hq, hqopt⟩, rfl⟩ have h1 := persuasion_receiver_add_sender_le _ hμ q hq rw [persuasion_slice_card_coord, hP] at h1 have h2 := hqopt _ hobs rw [hS] at h2 linarith · unfold persuasion_prior_utility simp only [persuasion_slice_marginal, Finset.sum_const, card_univ, persuasion_slice_card_coord, nsmul_eq_mul] congr 1 rw [max_eq_right] · field_simp; ring · rw [div_le_iff₀ hK] have : (m : ℝ) / (2 * m + 1) * (2 * m + 1) = m := by field_simp nlinarith