persuasion_receiver_add_sender_le
lemmaverifiedformalization
Sender–receiver trade-off (Lemma 4.2). R(q) + S(q) ≤ n + ∑_i p_i(μ).
Statement
open Finset in lemma persuasion_receiver_add_sender_le {ι : Type*} [Fintype ι] [DecidableEq ι] (μ : (ι → Bool) → ℝ) (hμ : ∑ x, μ x = 1) (q : (ι → Bool) → (ι → Bool) → ℝ) (hq : is_obedient_direct_scheme μ q) : persuasion_receiver_utility q + persuasion_sender_utility q ≤ Fintype.card ι + ∑ i, persuasion_marginal μ i
- Formalizes
- Quantifying Theoretical AI Alignment Guarantees: Receiver-Utility Bounds in Bayesian Persuasion, arXiv:2606.22226 v1, Lemma 4.2 (sender-receiver trade-off); formalized by the operator (Claude), 2026-10-03
- Verified
- 03 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_obedient_direct_schemeAn obedient direct scheme for the prior μ on {0,1}^ι.
- persuasion_receiver_utilityReceiver utility R(q): expected number of correctly guessed coordinates.
- persuasion_sender_utilitySender utility S(q): expected number of coordinates recommended as 1.
- persuasion_marginalThe marginal p_i(μ) = Pr_μ[X_i = 1].
- Used by 3
- 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_max_receiver_utility_learXiv:2606.22226, Theorem 4.5 (ratio form). For every prior, R_max(μ) ≤ (3/2) R_0(μ).
- 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/-- **Sender–receiver trade-off (Lemma 4.2).** `R(q) + S(q) ≤ n + ∑_i p_i(μ)`. -/lemma persuasion_receiver_add_sender_le {ι : Type*} [Fintype ι] [DecidableEq ι] (μ : (ι → Bool) → ℝ) (hμ : ∑ x, μ x = 1) (q : (ι → Bool) → (ι → Bool) → ℝ) (hq : is_obedient_direct_scheme μ q) : persuasion_receiver_utility q + persuasion_sender_utility q ≤ Fintype.card ι + ∑ i, persuasion_marginal μ i := by classical have hc : (Fintype.card ι : ℝ) = ∑ _i : ι, (1 : ℝ) := by simp have pt : ∀ x a : ι → Bool, ((Finset.univ.filter (fun i => a i = x i)).card : ℝ) + ((Finset.univ.filter (fun i => a i = true)).card : ℝ) ≤ Fintype.card ι + ((Finset.univ.filter (fun i => x i = true)).card : ℝ) := by intro x a rw [hc, natCast_card_filter, natCast_card_filter, natCast_card_filter, ← sum_add_distrib, ← sum_add_distrib] apply sum_le_sum intro i _ cases a i <;> cases x i <;> norm_num have h1 : persuasion_receiver_utility q + persuasion_sender_utility q = ∑ x, ∑ a, q x a * (((Finset.univ.filter (fun i => a i = x i)).card : ℝ) + ((Finset.univ.filter (fun i => a i = true)).card : ℝ)) := by unfold persuasion_receiver_utility persuasion_sender_utility rw [← sum_add_distrib] apply sum_congr rfl; intro x _ rw [← sum_add_distrib] apply sum_congr rfl; intro a _ ring have h2 : ∑ x, ∑ a, q x a * (((Finset.univ.filter (fun i => a i = x i)).card : ℝ) + ((Finset.univ.filter (fun i => a i = true)).card : ℝ)) ≤ ∑ x, ∑ a, q x a * ((Fintype.card ι : ℝ) + ((Finset.univ.filter (fun i => x i = true)).card : ℝ)) := sum_le_sum fun x _ => sum_le_sum fun a _ => mul_le_mul_of_nonneg_left (pt x a) (hq.1 x a) have h3 : ∑ x, ∑ a, q x a * ((Fintype.card ι : ℝ) + ((Finset.univ.filter (fun i => x i = true)).card : ℝ)) = ∑ x, μ x * ((Fintype.card ι : ℝ) + ((Finset.univ.filter (fun i => x i = true)).card : ℝ)) := by apply sum_congr rfl; intro x _ rw [← sum_mul, hq.2.1 x] have h4 : ∑ x, μ x * ((Fintype.card ι : ℝ) + ((Finset.univ.filter (fun i => x i = true)).card : ℝ)) = Fintype.card ι + ∑ i, persuasion_marginal μ i := by simp only [mul_add, sum_add_distrib] rw [← sum_mul, hμ, one_mul] congr 1 unfold persuasion_marginal simp only [natCast_card_filter, mul_sum] rw [sum_comm] apply sum_congr rfl; intro i _ apply sum_congr rfl; intro x _ split_ifs <;> simp rw [h1, ← h4, ← h3] exact h2