persuasion_max_receiver_utility_le
theoremverifiedformalization
arXiv:2606.22226, Theorem 4.5 (ratio form). For every prior, R_max(μ) ≤ (3/2) R_0(μ).
Statement
open Finset in theorem persuasion_max_receiver_utility_le {ι : Type*} [Fintype ι] [DecidableEq ι] (μ : (ι → Bool) → ℝ) (hμ : is_bit_prior μ) : persuasion_max_receiver_utility μ ≤ 3 / 2 * persuasion_prior_utility μ
- Formalizes
- Quantifying Theoretical AI Alignment Guarantees: Receiver-Utility Bounds in Bayesian Persuasion, arXiv:2606.22226 v1, Lemma 4.4 and Theorem 4.5 (OR scheme; R_max <= (3/2) R_0); formalized by the operator (Claude), 2026-10-03
- Verified
- 03 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 11
- is_bit_priorA probability distribution on {0,1}^ι.
- persuasion_marginalThe marginal p_i(μ) = Pr_μ[X_i = 1].
- persuasion_sender_utilitySender utility S(q): expected number of coordinates recommended as 1.
- persuasion_pair_or_schemeThe pair-OR scheme of a symmetric coupling ν: draw (X, Y) ∼ ν and recommend X ∨ Y.
- persuasion_pair_or_sender_utilitySender utility of a pair-OR scheme.
- 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_pair_or_scheme_obedientThe pair-OR scheme of a nonnegative symmetric coupling with first marginal μ is obedient.
- is_sender_optimal_schemeq is obedient and maximises the sender's utility among obedient schemes.
- persuasion_receiver_utilityReceiver utility R(q): expected number of correctly guessed coordinates.
- persuasion_receiver_add_sender_leSender–receiver trade-off (Lemma 4.2). R(q) + S(q) ≤ n + ∑_i p_i(μ).
- Used by 4
- persuasion_uniform_two_states_ratio_leFor every finite type ι and every prior μ on ι → Bool that is uniform on 2 distinct states, the maximum receiver utility R_max(μ) is at…
- persuasion_receiver_ratio_optimal_constantThe optimal constant is 3/2. 3/2 is the least c with R_max(μ) ≤ c R_0(μ) for all priors μ (over all finite coordinate sets).
- bit_persuasion_bounded_support_ratio_le_three_halvesFor every natural number m, every finite type ι with [DecidableEq ι], and every prior μ on ι → Bool that is a bit prior supported on at…
- persuasion_uniform_even_ratio_le_three_halvesFor every natural number m, every finite type ι, and every prior μ on ι → Bool that is uniform on 2m distinct states, the maximum receiver…
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/-- Marginals of a prior lie in `[0, 1]`. -/lemma persuasion_marginal_mem_Icc {ι : Type*} [Fintype ι] [DecidableEq ι] (μ : (ι → Bool) → ℝ) (hμ : is_bit_prior μ) (i : ι) : 0 ≤ persuasion_marginal μ i ∧ persuasion_marginal μ i ≤ 1 := by constructor · exact sum_nonneg fun x _ => by split_ifs; exacts [hμ.1 x, le_refl 0] · rw [← hμ.2] exact sum_le_sum fun x _ => by split_ifs; exacts [le_refl _, hμ.1 x]open Finset in/-- Sender utility of the OR scheme: `∑_i (2 p_i - p_i²)`. -/lemma persuasion_or_scheme_sender_utility {ι : Type*} [Fintype ι] [DecidableEq ι] (μ : (ι → Bool) → ℝ) (hμ : is_bit_prior μ) : persuasion_sender_utility (persuasion_pair_or_scheme (fun x y => μ x * μ y)) = ∑ i, (2 * persuasion_marginal μ i - persuasion_marginal μ i ^ 2) := by classical rw [persuasion_pair_or_sender_utility] set p := persuasion_marginal μ let A : ι → (ι → Bool) → ℝ := fun i x => if x i = true then 1 else 0 have hp : ∀ i, ∑ x, μ x * A i x = p i := by intro i; simp only [p, persuasion_marginal, A] apply sum_congr rfl; intro x _; split_ifs <;> simp calc ∑ x, ∑ y, μ x * μ y * ((Finset.univ.filter (fun i => (x i || y i) = true)).card : ℝ) = ∑ x, ∑ y, ∑ i, ((μ x * A i x) * μ y + μ x * (μ y * A i y) - (μ x * A i x) * (μ y * A i y)) := by apply sum_congr rfl; intro x _; apply sum_congr rfl; intro y _ rw [natCast_card_filter, mul_sum]; apply sum_congr rfl; intro i _ simp only [A] cases x i <;> cases y i <;> simp _ = ∑ x, ∑ i, ∑ y, ((μ x * A i x) * μ y + μ x * (μ y * A i y) - (μ x * A i x) * (μ y * A i y)) := sum_congr rfl (fun x _ => sum_comm) _ = ∑ i, ∑ x, ∑ y, ((μ x * A i x) * μ y + μ x * (μ y * A i y) - (μ x * A i x) * (μ y * A i y)) := sum_comm _ = ∑ i, (2 * p i - p i ^ 2) := by apply sum_congr rfl; intro i _ simp only [sum_sub_distrib, sum_add_distrib, ← mul_sum, ← sum_mul] rw [hp i, hμ.2] ringopen Finset in/-- **arXiv:2606.22226, Theorem 4.5 (ratio form).** For every prior, `R_max(μ) ≤ (3/2) R_0(μ)`. -/theorem persuasion_max_receiver_utility_le {ι : Type*} [Fintype ι] [DecidableEq ι] (μ : (ι → Bool) → ℝ) (hμ : is_bit_prior μ) : persuasion_max_receiver_utility μ ≤ 3 / 2 * persuasion_prior_utility μ := by classical have hp := persuasion_marginal_mem_Icc μ hμ set p := persuasion_marginal μ have hobs := persuasion_pair_or_scheme_obedient μ (fun x y => μ x * μ y) (fun x y => mul_nonneg (hμ.1 x) (hμ.1 y)) (fun x y => mul_comm _ _) (fun x => by rw [← mul_sum, hμ.2, mul_one]) have hSor := persuasion_or_scheme_sender_utility μ hμ have hR0 : 0 ≤ persuasion_prior_utility μ := sum_nonneg fun i _ => le_max_of_le_left (hp i).1 have key : ∀ q, is_sender_optimal_scheme μ q → persuasion_receiver_utility q ≤ 3 / 2 * persuasion_prior_utility μ := by rintro q ⟨hq, hopt⟩ have h1 := persuasion_receiver_add_sender_le μ hμ.2 q hq have h2 := hopt _ hobs rw [hSor] at h2 have hc : (Fintype.card ι : ℝ) = ∑ _i : ι, (1 : ℝ) := by simp have h3 : (Fintype.card ι : ℝ) + ∑ i, p i - ∑ i, (2 * p i - p i ^ 2) ≤ 3 / 2 * persuasion_prior_utility μ := by rw [hc, persuasion_prior_utility, mul_sum, ← sum_add_distrib, ← sum_sub_distrib] apply sum_le_sum; intro i _ obtain ⟨h0, h1⟩ := hp i rcases le_total (p i) (1 - p i) with h | h · rw [max_eq_right h]; nlinarith · rw [max_eq_left h]; nlinarith linarith apply Real.sSup_le · rintro r ⟨q, hq, rfl⟩ exact key q hq · positivity